JavaでのHashMapについて
1容量は常に2乗
2ハッシュ関数の設計はhashcodeの高位と低位特性を同時に使用する
3 index位置a%b=a&(b-1)を検索
4競合解決方法は、チェーンテーブル法です.同じリストの要素の数が8より大きく、赤と黒のツリーを使用します.
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
2ハッシュ関数の設計はhashcodeの高位と低位特性を同時に使用する
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) ;
}
3 index位置a%b=a&(b-1)を検索
int index = hash(key) &(capacity-1)
4競合解決方法は、チェーンテーブル法です.同じリストの要素の数が8より大きく、赤と黒のツリーを使用します.