第13章. 哈希表

哈希表(Hash Table)

一、引言

TreeMap分析

• 添加、删除、搜索的时间复杂度：O(n)
• 特点：
• key必须具备可比较性
• 元素的分布是有顺序的

但是在实际应用中，很多时候的需求中

1. Map中存储的元素不需要讲究顺序
2. Map中的Key不需要具备可比较性

• 不考虑顺序、不考虑Key的可比较性，Map有更好的实现方案，平均时间复杂度可以达到O(1)
• 那就是采取哈希表来实现Map

二、哈希表(Hash Table)

• 哈希表也叫作散列表
• 哈希表添加、搜索、删除的流程都是类似的
  • 利用哈希函数生成key对应的index，时间复杂度O(1)
  • 根据index操作定位数组元素，时间复杂度O(1)
• 哈希表是空间换时间的典型应用
• 哈希函数，也叫作散列函数
• 哈希表内部的数组元素，很多地方也叫作Bucket(桶)，整个数组叫做Buckets或者Bucket Array

三、哈希冲突

• 哈希冲突也叫做哈希碰撞
  • 指的是两个不同的key，经过哈希函数计算出相同的结果
  • 即key1 ≠ key2，但hash(key1) = hash(key2)的情况

四、解决哈希冲突的常见方法

1. 开放地址法(Open Addressing)

• 按照一定规则向其他地址探测，直到遇到空桶(依靠哈希表中的空位来解决碰撞问题)。

2. 再哈希法(Re-Hashing)

• 设计多个哈希函数

3. 链地址法(Separate Chaining)

• 比如通过链表将同一index的元素串起来

五、JDK1.8的哈希冲突解决方案

• Java官方解决哈希冲突默认使用链地址法。
• 默认使用单向链表将元素串起来
• 在添加元素时，可能会由单向链表转为红黑树来存储元素
  • 比如当哈希表容量 >= 64 且单向链表的节点数量大于8时
• 当红黑树节点数量少到一定程度时，又会转为单向链表
• JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突
• 这里为什么使用单链表而不是双向链表？
  • 每次都是从头节点开始遍历(没必要用双向链表)，并且依次判断新加入的节点其key是否已经存在，如果存在，则将值覆盖；如果不存在，则将值添加至其尾部。
  • 单链表比双向链表少一个指针，可以节省内存空间。

六、哈希函数

• 哈希表中哈希函数的实现步骤大概如下：

1. 先生成key的哈希值(必须是整数)
2. 再让key的哈希值跟数组的大小进行相关计算，生成一个索引值

public int hash(Object key) {
   return hash_code(key) % table.length;
}

• 为了提高效率，可以使用&位运算取代%运算(前提：将数组的长度设计为2的幂)

public int hash(Object key) {
   return hash_code(key) & (table.length - 1);
}

这里返回的结果是：[0 ~ table.length - 1]

• 良好的哈希函数
  • 能让哈希值更加均匀分布—>减少哈希冲突次数—>提升哈希表的性能

七、生成key的哈希值

• key的常见种类可能有：
• 整数、浮点数、字符串、自定义对象
• 不同种类的key，哈希值的生成方式不一样，但目标是一致的
  • 尽量让每个key的哈希值是唯一的
  • 尽量让key的所有信息参与运算
• 在Java中，HashMap的key必须实现hashCode、equals方法，也允许key为null

7.1 整数的哈希值

7.1.1 Integer类型

// JDK1.8源码
public static int hashCode(int value) {
    return value;
}

Integer自身值当做哈希值。

7.1.2 Long类型

// JDK1.8源码
public static int hashCode(long value) {
    // 将64位的数字，其前32位砍掉
    return (int)(value ^ (value >>> 32));
}

• >>>和^的作用是
  • 高32bit和低32bit混合计算出32bit的哈希值
  • 充分利用所有信息计算出哈希值
• 
• 相当于充分利用所有信息算出哈希值

7.2 浮点数的哈希值

将存储的二进制格式转为整数值

7.2.1 Float类型

// JDK1.8源码
public static int hashCode(float value) {
    return floatToIntBits(value);
}

7.2.2 Double类型

// JDK1.8源码
public static int hashCode(double value) {
    long bits = doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

因为Double是64位的，所以doubleToLongBits也是64位的。

7.3 字符串的哈希值

String s = "jack";
int hashCode = 0;
int len = s.length();
for (int i = 0; i < len; i ++) {
    char c = s.charAt(i);
    hashCode = 31 * hashCode + c;
}

String s = "jack";
int hashCode = 0;
int len = s.length();
for (int i = 0; i < len; i ++) {
    char c = s.charAt(i);
    hashCode = （(hashCode << 5) - hashCode) + c;
}

7.4 自定义对象的哈希值(重要)

• 自定义对象作为key，最好同时重写hashCode、equals方法
• equals：用以判断哈希值相同的2个key是否为同一个key(判断是否内容相同)。【在哈希冲突的时候调用】

• hashCode：必须保证equals为true的2个key的哈希值一样。【在计算哈希值的时候调用】

  • 反过来hashCode相等的key，不一定equals为true

• 不同类型的数据有可能计算出相同的哈希值例如 String 类型的数据与Double类型的数据的哈希值可能相同，此时会产生冲突。当两个key不相等，但是哈希值相等时，我们需要用equals方法来判断两个key是否为同一个key，此时就需要重写equals。

• hashCode一样才会有冲突，之后还要用equals比较是否为同一个key；如果为同一个key则覆盖，如果不为同一个key则添加。

  • public static void main(String[] args) {
    	Person p1 = new Person(18, 1.75f, "jerry");
    	Person p2 = new Person(18, 1.75f, "jerry");
    	Map<Object, Object> map = new HashMap<>();
    	              	map.put(p1, "abc");
    	map.put("test", "bcd");
    	// 由于重写 hashCode()，则p1 与 p2 哈希值相等
    	// 会比较 p1 与 p2 是否为同一key
    	// 由于又重写了equals(), 综上p1、p1为同一key
    	map.put(p2, "ccc"); // 同一个key则覆盖,map里的元素数量不增加
      
    	System.out.println(map.size()); // 2
                  }
    

  • 若只重写 hashCode
    由于重写 hashCode，p1、p2 哈希值必然相等，则放入 map 会去比较 key
    但是 equals 默认比较地址，p1、p2地址不同，不为同一 key，因此 map.size() 为3

  • 若只重写 equals
    由于没有重写 hashCode，p1、p2 哈希值大概率不相等(有极小可能相等)
    一般情况下，p1、p2哈希值不相等，map.size()值应当为3
    若是真遇到了哈希值相等的情况，由于重写了 equals，map.size()值为2

  • 结论就是：重写hashCode与equals是最稳妥的做法。

• 哈希值相等，根据哈希函数求的索引必然相等

• 哈希值不相等，根据哈希函数求的索引有可能相等

• HashMap的key必须实现hashCode、equals方法，也允许key为null

7. 5 关于31的探讨

• 任何数乘以31都等于把这个数左移五位再减去这个数
• 31 * i = (i << 5) - i
• 31不仅仅是符合2ⁿ-1，它是个奇素数(既是奇数，又是素数，也就是质数)
• 素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突
• 最终选择31是经过观测分布结果后的选择

八、哈希值的进一步处理:扰动计算

private int hash(K key) {
    if (key == null) return 0;
    int h = key.hashCode();
    return (h ^ (h >>> 16))) & (table.lenght - 1);
}

九、装填因子

• 装填因子(Load Factor)：节点总数量 / 哈希表桶数组长度，也叫做负载因子。
• 在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍。

十、TreeMap VS HashMap

• 何时选择TreeMap？
  • 元素具备可比较性且要求升序遍历(默认是按照元素从小到大，也可以指定比较规则)
• 何时选择HashMap？
  • 无序遍历