交做网贷的网站,wordpress动画效果,用网站做数据库,开发软件需要什么软件根据容量计算大于容量的最小的哈希表的大小(table的length)#xff0c;这里的length需要满足length2^n#xff0c;也就是我们需要根据容量算出最小的n的值
static final int tableSizeFor(int cap) {int n cap - 1;n | n 1;n | n 2;n | n 这里的length需要满足length2^n也就是我们需要根据容量算出最小的n的值
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;
}
int n cap - 1;这里是为了确定在二进制表示的情况下最高位的1的位置这里分两种情况来讲
1.cap!2^n,cap不是2的n次方
这种情况其实减1之后最高位的1的位置不变例如随便找两个数
69
00000000 00000000 00000000 01000101
69-1
00000000 00000000 00000000 01000100
16196
00000000 00000000 00100000 01000100
16196-1
00000000 00000000 00100000 01000011
4210496
00000000 00100000 00100000 01000000
4210496-1
00000000 00100000 00100000 00111111这几个数字减 1 以后最高位的1的位置不变2.cap2^n,cap是2的n次方
这种情况其实减1之后最高位的1的位置会向右移动一位16
00000000 00000000 00000000 00010000
16-1
00000000 00000000 00000000 00001111
4096
00000000 00000000 00010000 00000000
4096-1
00000000 00000000 00001111 11111111这几个数字减1之后最高位的1的位置会向右移动一位n | n 1; 这一步是让从最高位的1开始往右的前2位变为1
例如
n 100000
n 1 就是 10000
n | n 1 的意思就是 n n | n 1 100000 | 10000 110000n | n 2; 这一步是让从最高位的1开始往右的前4位变为1
n 110000
n 2 就是 1100
n | n 2 的意思就是 n n | n 2 110000 | 1100 111100n | n 4; 这一步是让从最高位的1开始往右的前8位变为1
n 111100
n 4 就是 11
n | n 4 的意思就是 n n | n 4 111100 | 11 111111这里再举一个比较大的例子n10000000000000000000000000000000
n 1 就是 1000000000000000000000000000000
n | n 1 就是 n n | n 1 10000000000000000000000000000000| 1000000000000000000000000000000 11000000000000000000000000000000n 11000000000000000000000000000000
n 2 就是 110000000000000000000000000000
n | n 2 就是 n n | n 2 11000000000000000000000000000000 | 110000000000000000000000000000 11110000000000000000000000000000n 11110000000000000000000000000000
n 4 就是 1111000000000000000000000000
n | n 4 就是 n n | n 4 11110000000000000000000000000000 | 1111000000000000000000000000 11111111000000000000000000000000n 11111111000000000000000000000000
n 8 就是 111111110000000000000000
n | n 8 就是 n n | n 8 11111111000000000000000000000000 | 111111110000000000000000 11111111111111110000000000000000n 11111111111111110000000000000000
n 16 就是 1111111111111111
n | n 16 就是 n n | n 16 11111111111111110000000000000000 | 1111111111111111 11111111111111111111111111111111return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
这里表示如果正常的话返回的值应该是 n 1
根据我们的经验如果一个数的二进制表示所有的1都在最右边那么这个数加 1 以后就是 2^n 计算一个key值的hash值这里的key的类型是 Object。计算出来的hash值用来参与计算当前键值对在hash表中的位置
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))
以上是put方法的部分代码我们可以摘取出其中的关键代码
int n , i;
(n tab.length) 0 这里执行完那么 n tab.length(p tab[i (n - 1) hash]) null 这里执行完,那么 i (n - 1) hash
hash的值就是通过上面的hash()方法计算出的值tab[i] newNode(hash, key, value, null);
这里可以看出 i 是用来寻找新节点的位置的看来节点在table中的位置为:
(tab.length - 1) hash
根据 tableSizeFor() 的实现可以看出tab.length为2^k , tab.length - 1的值用二进制表示
低位都为1二进制高位都是0
那么 (tab.length - 1) hash 就相当于只取hash的二进制表示的最低的那几位。
如果两个不同的hash值如果高位不同低位相同那么算出来的值是相同的就会增加hash冲突的概率导致性能受影响。接下来讨论hash()方法的这段代码的巧妙之处(h key.hashCode()) ^ (h 16)
h key.hashCode() 是key的hashCode值
h 16 表示 h 向右移动16位原来高位的16位移到低位了(h key.hashCode()) ^ (h 16) 就相当于将 h 的高16位和低16位进行异或运算
这样h的二进制表示如果高位不同低位相同那么最终结果的低位是不同的
前面put方法分析了寻找键值对在table中的位置时只取hash值的低位来决定键值对的位置
这样就可以减少hash碰撞的概率
