Java数据结构_哈希表_基本概念

本文目标

哈希表的基本概念,哈希冲突,哈希函数

什么是哈希表

哈希表也叫做散列表(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;
}