HashSetは便利です。
しかし、javaのラッパークラスしか使えないという制限が、HashSetに1万件を登録したら、1万個のLongインスタンスができるということ。
自前のハッシュ配列
まずsize=2^(bit)の固定長の配列を用意する。下位マスクlmask = size - 1と上位マスクhmask =~ lmaskを用意する。
HashSetも用意し、固定長配列に収まらない場合に、標準ライブラリに逃がす。
boolean contains(long key)に対して、key & lmaskを配列のインデックスにする。
配列の値の最下位ビットが0ならば空き、1ならば使用中。
空きならばfalseを返す。1ならば、kval = (key & hmask) | (retry << 1) | 1の値を比較し、一致したらtrueを返す。
一致しない場合、retryを加算し、上限rcntまでインデックスを移動しながら、リトライする。
retryのビットがないと、hmaskが同じで、lmaskが異なる2つの値の区別がつかなくなる。
下の例ではv2がary[1]に入るが、0x101で入れると、v3との区別がつかないので、v3もary[1]に入る。
// bit=8の場合
v1 = 0;
v2 = 0 | (1 << bit); // 0x100
v3 = 1 | (1 << bit); // 0x101
add(v1) // ary[0]=1
add(v2) // ary[1]=0x103
add(v3) // ary[2]=0x103
計測
最初に1000件乱数を発生し、1000件の配列に保存する。
(総数-1000)件は、50%が乱数、50%が1000件の配列から同じ値を使う。1
HashSetのみ使った場合、200万件中100万件登録した場合344ミリ秒、10倍の1000万件弱登録した場合4326ミリ秒。2
ただし、GCのコストは考慮していない。
344ms
s=1000447 cnt=2000000
4326ms
s=9998896 cnt=20000000
自前のハッシュ配列を1次にして、扱えない場合HashSetを2次にしたとき。
bitはビット数、rcntはリトライ最大数、bufsizeはバッファ要素数、s1は自前ハッシュ登録数、s2はHashSet登録数、sはs1+s2、cntはテストデータ数、use%はs1/bufsize、err%はs2/(s1+s2)。
100万件ならば、20ビット1M×long(8B)=8MBがベスト。半分と2倍を計測した。
retry=0（衝突したらすぐ諦める）はよくなく、増やせばいいがretry=3まで行くと、HashSetに任せた方がよさげ。
bit=20,rcnt=2が143ミリ秒（適用前344ミリ秒）とわざわざ作る効果がありそう。
273ms
bit=19 rcnt=0 bufsize=524288 s1=446431 s2=554016 s=1000447 cnt=2000000 use%=85.15 err%=55.38
209ms
bit=20 rcnt=0 bufsize=1048576 s1=644780 s2=355667 s=1000447 cnt=2000000 use%=61.49 err%=35.55
195ms
bit=21 rcnt=0 bufsize=2097152 s1=795789 s2=204658 s=1000447 cnt=2000000 use%=37.95 err%=20.46
207ms
bit=19 rcnt=1 bufsize=524288 s1=497088 s2=503359 s=1000447 cnt=2000000 use%=94.81 err%=50.31
153ms
bit=20 rcnt=1 bufsize=1048576 s1=760919 s2=239528 s=1000447 cnt=2000000 use%=72.57 err%=23.94
163ms
bit=21 rcnt=1 bufsize=2097152 s1=916468 s2=83979 s=1000447 cnt=2000000 use%=43.70 err%=8.39
181ms
bit=19 rcnt=2 bufsize=524288 s1=512290 s2=488157 s=1000447 cnt=2000000 use%=97.71 err%=48.79
143ms
bit=20 rcnt=2 bufsize=1048576 s1=812073 s2=188374 s=1000447 cnt=2000000 use%=77.45 err%=18.83
168ms
bit=21 rcnt=2 bufsize=2097152 s1=958134 s2=42313 s=1000447 cnt=2000000 use%=45.69 err%=4.23
197ms
bit=19 rcnt=3 bufsize=524288 s1=518551 s2=481896 s=1000447 cnt=2000000 use%=98.91 err%=48.17
148ms
bit=20 rcnt=3 bufsize=1048576 s1=842391 s2=158056 s=1000447 cnt=2000000 use%=80.34 err%=15.80
136ms
bit=21 rcnt=3 bufsize=2097152 s1=976948 s2=23499 s=1000447 cnt=2000000 use%=46.58 err%=2.35
1000万件ならば、24ビット16M×long(8B)=128MiBが1.6倍の余裕があり、半分と2倍を計測した。
bit=24,rcnt=2が1893ミリ秒（適用前4326ms）が良さげだが、メモリ128MiBが取りすぎならば、半分のbit=23,rcnt=2が2215ミリ秒でも十分効果がありそう。
2686ms
bit=23 rcnt=0 bufsize=8388608 s1=5842492 s2=4156404 s=9998896 cnt=20000000 use%=69.65 err%=41.57
2300ms
bit=24 rcnt=0 bufsize=16777216 s1=7532735 s2=2466161 s=9998896 cnt=20000000 use%=44.90 err%=24.66
2097ms
bit=25 rcnt=0 bufsize=33554432 s1=8646997 s2=1351899 s=9998896 cnt=20000000 use%=25.77 err%=13.52
2414ms
bit=23 rcnt=1 bufsize=8388608 s1=6838069 s2=3160827 s=9998896 cnt=20000000 use%=81.52 err%=31.61
1925ms
bit=24 rcnt=1 bufsize=16777216 s1=8796902 s2=1201994 s=9998896 cnt=20000000 use%=52.43 err%=12.02
1863ms
bit=25 rcnt=1 bufsize=33554432 s1=9631075 s2=367821 s=9998896 cnt=20000000 use%=28.70 err%=3.68
2215ms
bit=23 rcnt=2 bufsize=8388608 s1=7266359 s2=2732537 s=9998896 cnt=20000000 use%=86.62 err%=27.33
1893ms
bit=24 rcnt=2 bufsize=16777216 s1=9287365 s2=711531 s=9998896 cnt=20000000 use%=55.36 err%=7.12
1731ms
bit=25 rcnt=2 bufsize=33554432 s1=9872152 s2=126744 s=9998896 cnt=20000000 use%=29.42 err%=1.27
2235ms
bit=23 rcnt=3 bufsize=8388608 s1=7511569 s2=2487327 s=9998896 cnt=20000000 use%=89.54 err%=24.88
1852ms
bit=24 rcnt=3 bufsize=16777216 s1=9535596 s2=463300 s=9998896 cnt=20000000 use%=56.84 err%=4.63
1697ms
bit=25 rcnt=3 bufsize=33554432 s1=9949643 s2=49253 s=9998896 cnt=20000000 use%=29.65 err%=0.49
ソース
衝突したら+1インデックスにしている。
上位ビットを使うとか、そもそも2次元配列にして制限付きのチェイン法にしたらお隣さんを邪魔しない方がよいのか。
もし削除を作るのなら、lmaskをそのまま入れるのが適当で、containsはそのままでもretryが一致しないからスキップし、addは空を探す(val & 1) == 0のときにval == lmaskも一緒に空と見なす。
制限はrcntがすべてのビットが立つ-1までで、(1 << (bit-1))-1-1かな。bit=20のときrcnt=524,286回もお隣を探すなよ。
public class LongHash {
HashSet<Long> set=new HashSet<>();
int bit;
int rcnt;
int size;
long[] ary;
long lmask;
long hmask;
LongHash(int bit, int rcnt) {
this.bit = bit;
this.rcnt = rcnt;
size = 1 << bit;
ary=new long[size];
lmask = size - 1;
hmask =~ lmask;
}
boolean contains(long key) {
int kidx = (int)(key & lmask);
for (int retry = 0; retry <= rcnt; retry++) {
long val = ary[kidx];
if ((val & 1) == 0) return false;
long kval = (key & hmask) | (retry << 1) | 1;
if (val == kval) return true;
//隣を探す
kidx = (int)((kidx + 1) & lmask);
}
return false;
}
boolean add(long key) {
int kidx = (int)(key & lmask);
int retry;
for (retry = 0; retry <= rcnt; retry++) {
long val = ary[kidx];
if ((val & 1) == 0) break;
long kval = (key & hmask) | (retry << 1) | 1;
if (val == kval) break;
//隣を探す
kidx = (int)((kidx + 1) & lmask);
}
if (retry <= rcnt) {
long kval = (key & hmask) | (retry << 1) | 1;
ary[kidx] = kval;
return true;
}
return false;
}
int size() {
int cnt=0;
for (int i=0; i<ary.length; i++) {
if ((ary[i] & 1) == 1) cnt++;
}
return cnt;
}
long[] same=new long[1000];
int sameidx=0;
long nextLong(Random rand) {
if (sameidx<same.length) {
long v=rand.nextLong();
same[sameidx++]=v;
return v;
}
if (rand.nextBoolean()) {
int idx=rand.nextInt(same.length);
long v=same[idx];
return v;
}
long v=rand.nextLong();
return v;
}
void test(int cnt) {
Random rand=new Random(0);
long st=System.currentTimeMillis();
for (int i=0; i<cnt; i++) {
long v=nextLong(rand);
if (!contains(v)) {
if (!add(v)) set.add(v);
}
}
long ed=System.currentTimeMillis();
System.out.println((ed-st)+"ms");
int s1=size();
int s2=set.size();
System.out.println("bit="+bit+" rcnt="+rcnt+" bufsize="+size+" s1="+s1+" s2="+s2+" s="+(s1+s2)+" cnt="+cnt
+" use%="+(100.0*s1/size)
+" err%="+(100.0*s2/(s1+s2)));
}
void test0(int cnt) {
Random rand=new Random(0);
long st=System.currentTimeMillis();
for (int i=0; i<cnt; i++) {
long v=nextLong(rand);
if (!set.contains(v)) set.add(v);
}
long ed=System.currentTimeMillis();
System.out.println((ed-st)+"ms");
int s=set.size();
System.out.println("s="+s+" cnt="+cnt);
}
public static void main(String[] args) {
int bit;
int cnt=2*1000*1000;
int rcnt;
bit=20;
for (rcnt = 0; rcnt <= 3; rcnt++) {
new LongHash(bit-1, rcnt).test(cnt);
new LongHash(bit, rcnt).test(cnt);
new LongHash(bit+1, rcnt).test(cnt);
}
new LongHash(bit, rcnt).test0(cnt);
bit=24;
cnt=20*1000*1000;
for (rcnt = 0; rcnt <= 3; rcnt++) {
new LongHash(bit-1, rcnt).test(cnt);
new LongHash(bit, rcnt).test(cnt);
new LongHash(bit+1, rcnt).test(cnt);
}
new LongHash(bit, rcnt).test0(cnt);
}
}
元ネタ
もともとAIチャットが評価値をHashMapで持たせると重いので、long[] idxとdouble[] valの固定長配列を用意したものを提案してきて、それを元に作ってみた。
0を空としているので、tagが0なら1にしているが、もともと1だったときの区別は。
そもそも128ビットを64ビットにして衝突しても上書きするつもりなのか。
このときキーはlong型でなくlong2個分のダブルハッシュだった。
→という突っ込みをしたら、別に使用中フラグ配列を用意するというのだから、下位ビットをクリアしてフラグとカウントを持たせたらどうよと言えば、それは良いアイデアと言われたので、きっと良いだろう。Robin Hood Hashing や Hopscotch Hashingって何だろう。
class TranspositionTable {
private final int size; // 2のべき乗（例: 1 << 22）
private final int mask;
private final long[] keys; // 128bitハッシュを1つのlongに圧縮するか、2つの配列に分ける
private final double[] vals;
public TranspositionTable(int power) {
this.size = 1 << power;
this.mask = size - 1;
this.keys = new long[size];
this.vals = new double[size];
}
public void put(long h1, long h2, double score) {
long tag = h1 ^ h2; // 識別用タグ（0は「空」として予約）
if (tag == 0) tag = 1;
int idx = (int)(h1 & mask);
while (keys[idx] != 0 && keys[idx] != tag) {
idx = (idx + 1) & mask; // 線形探索（隣を探す）
}
keys[idx] = tag;
vals[idx] = score;
}
}