BloomFilterをjavaとpythonで書いてみた。

Javaほんとに面倒くさい。
慣れていないからなのか？

BloomFilterを両方で書いてみた。

python

# -*- coding:utf-8 -*-
from bitarray import bitarray
import hashlib
import sys

class BloomFilter(object):
    def __init__(self,bitLength):
        self.bitarr = bitarray(bitLength) # ビット配列
        self.bitarr.setall(False)
        self.bitLength = bitLength # ビット配列の長さ
        self.salt = ['137','69','545']

    def hashing(self,word):
        '''ハッシュ関数に関しては、saltを変えることによって
        複数のハッシュ関数にしました。
        '''
        hashes = []
        for x in self.salt:
            m = hashlib.md5()
            m.update(x+word)
            hashes.append(m.digest()[0])
        return [ord(x) % self.bitLength for x in hashes]

    def append(self,word):
        '''入力をハッシュに変えて、ビット配列に突っ込む'''
        hashes = self.hashing(word)
        for x in hashes:
            self.bitarr[x] = 1

    def checkFilter(self,word):
        '''各ハッシュ関数を通したハッシュの値が、
        ビット配列で立っているかチェック'''
        hashes = self.hashing(word)
        return all(self.bitarr[x]==1
                   for x in hashes)

if __name__ =='__main__':
    bf = BloomFilter(10000)
    bf.append("foo")
    bf.append("bar")
    bf.append("baz")
    print bf.checkFilter("foo")
    print bf.checkFilter("bal")

java

• BloomFilter.java

/*
BloomFilter
*/
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

public class BloomFilter{
    private int bitLength;
    private String[] salt;
    private BitSet bitset = new BitSet(bitLength);

    public BloomFilter(int bitLength, String[] salt){
        this.bitLength = bitLength;
        this.salt = salt;
    }

    void append(String str){
        Encrypter enc = new Encrypter();
        for(int i = 0; i< salt.length;i++){
            str += salt[i];
            String hash = Encrypter.getHash(str, Encrypter.ALG_SHA1);
            int bitIndex = (int) hash.toCharArray()[0];
            bitset.set(bitIndex);
        }
    }
    boolean checkFilter(String str){
        for(int i=0; i < salt.length; i++){
            str += salt[i];
            String hash = Encrypter.getHash(str, Encrypter.ALG_SHA1);
            int bitIndex = (int) hash.toCharArray()[0];
            if(!bitset.get(bitIndex)) return false;
        }
        return true;
    }
}

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

/**
 * ハッシュ値生成機能を提供
 * @auther Mahny
 */
public class Encrypter{
    
    /**
     * メッセージダイジェスト：MD5
     */
    public static final String ALG_MD5= "MD5";
        
    /**
     * メッセージダイジェスト：SHA-1
     */
    public static final String ALG_SHA1= "SHA-1";
        
    /**
     * メッセージダイジェスト：SHA-256
     */
    public static final String ALG_SHA256= "SHA-256";
        
    /**
     * メッセージダイジェスト：SHA-384
     */
    public static final String ALG_SHA384= "SHA-384";
        
    /**
     * メッセージダイジェスト：SHA-512
     */
    public static final String ALG_SHA512= "SHA-512";
    
    /**
     * ハッシュ値を返す
     * @param org 計算元文字列
     * @param algorithm ハッシュアルゴリズム名(Encrypter.ALG_xxxで取得できる)
     * @return ハッシュ値
     */
    public static String getHash(String org, String algorithm){
        // 引数・アルゴリズム指定が無い場合は計算しない
        if ((org== null)||(algorithm== null)){
            return null;
        }
        
        // 初期化
        MessageDigest md= null;
        try{
            md= MessageDigest.getInstance(algorithm);
        }
        catch(NoSuchAlgorithmException e){
            return null;
        }
        
        md.reset();
        md.update(org.getBytes());
        byte[] hash= md.digest();
        
        // ハッシュを16進数文字列に変換
        StringBuffer sb= new StringBuffer();
        int cnt= hash.length;
        for(int i= 0; i< cnt; i++){
            sb.append(Integer.toHexString( (hash[i]>> 4) & 0x0F ) );
            sb.append(Integer.toHexString( hash[i] & 0x0F ) );
        }
        return sb.toString();
    }
}

• BloomFilterTest.java

class BloomFilterTest{

    public static void main(String[] args){
        String[] salt = {"137","69","545"};
        BloomFilter bf = new BloomFilter(10000,salt);
        bf.append("foo");
        bf.append("bar");
        bf.append("baz");
        System.out.println(bf.checkFilter("foo"));
        System.out.println(bf.checkFilter("bal"));
    }
}

ハッシュ関数を作成するところは一陣の神風が舞う JAVAのハッシュ関数を簡略化するを使わせて頂きました。

Javaって、オブジェクト指向だなーってことを実感している今日このごろ。