本文目标
哈希表的基本概念,哈希冲突,哈希函数
什么是哈希表
哈希表也叫做散列表(hash有剁碎的意思)
哈希表是空间换时间的典型应用
哈希表内部的数组元素,很多地方也叫做Bucket(桶),整个数组叫Buckets或者 Bucket Array
哈希冲突
哈希冲突也叫做哈希碰撞
2个不同的key,经过哈希函数计算得到相同的结果
JDK1.8的哈希冲突解决方案
默认采用采用单向链表将元素穿起来
在添加元素的时候也可以能由单向链表转成红黑树,比如当哈希表容量≥64 且单向链表的节点数量>8
当红黑树节点数量少到一定程度时候,又会转为单向链表
为什么使用单链表?
1.每次都是从头结点开始遍历
2.单向链表比双向链表少一个指针,节省内存空间
哈希函数
哈希表中哈希函数的实现步骤大概如下
1.先生成key的哈希值(必须是整数)
2.在让key的哈希值和数组的大小进行相关运算,生成一个索引值
public int hash(Object key) {
return hashCode(key) % table.length;
}
为了提高效率,可以使用&位运算取代%运算【前提:将数组的长度设计为2的幂(2^n)】
public int hash(Object key) {
return hashCode(key) & (table.length-1);
}
为什么可以使用&位运算取代%运算
二进制 2^n
10 2^1
100 2^2
1000 2^3
10000 2^4
二进制 2^n - 1
01 2^1-1
011 2^2-1
0111 2^3-1
01111 2^4-1
不难发现,都是2^n - 1 转成二进制都是一排1(最前面的0可以忽略)
假如说现在hash_code(key)为10101,然后与数组长度为(2^3 - 1)做&运算
10101 哈希值
& 00111 数组的长度
---------------
00101 索引值
得出来的结果 00101必然是小于00111的(数组的长度2^3 - 1)
良好的哈希函数
让哈希值更加均匀分布->减少哈希冲突此时->提升哈希表的性能
如何生成key的哈希值
key的常见种类可能有
1.整数,浮点数,字符串,自定义对象
2.不同种类的key,哈希值的生成方式不一样,但目标是一致的
尽量让每个key的哈希值是唯一的
进来让key的所有信息参与运算
1.整数的哈希值
把整数值当做哈希值
比如10的哈希值就是10
public static int hashCode(int value) {
return value;
}
2.浮点数的哈希值
将存储的二进制个数转为整数值
public static int hashCode(float value) {
return Float.floatToIntBits(value);
}
3.Long的哈希值
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
4.Doble的哈希值
public static int hashCode(double value) {
//long类型的64位的二进制数据
long bits = Double.doubleToLongBits(value);
//进行低32位和高32位的 异或运算(相同为0,不同为1),算出哈希值
return (int)(bits ^ (bits >>> 32));
}
>>> 和 ^ 的作用是?
1.高32bit和低32bit混合计算出32bit的哈希值
2.充分利用所有信息计算出哈希值
上图,value 和 value>>>32 (右移32位) 做异或^运算
此时,是value的低32位和高32位做异或^运算
|或运算,有一个为1就为1
所以不能用或运算,只能用异或
异或运算,相同为0,不同为1
5.字符串的哈希值
整数5489是如何计算出来的?
5 * 10^3 + 4 * 10^2 + 8 * 10^1 + 9 * 10^0
字符串是由若干个字符组成的
1.比如字符串jack,由j,a,c,k四个字符组成(字符的本质就是一个整数)
2.因此,jack的哈希值可以表示为
j * n^3 + a * n^2 + c * n^1 + k * n^0
等价于
[(j * n + a) * n + c] * n + k
3.在JDK中,乘数n为31,为什么使用31?
31是一个奇素数,JVM会将31 * i 优化成 (i<<5) -1
public static int hashCode(String value) {
int hashCode = 0;
int len = value.length();
for(int i=0;i<len;i++) {
char c = value.charAt(i);
hashCode = 31 * hashCode +c;
}
return hashCode;
}
