【数据结构】哈希表、哈希值计算分析

清疚 2022-11-06 05:44 203阅读 0赞

### 哈希表、哈希值计算分析 ###

*  哈希表完整代码
 *  引出哈希表
 *  哈希表（Hash Table）
 *  哈希冲突（Hash Collision）
 *  JDK1.8的哈希冲突解决方案
 *  哈希函数
 *  如何生成 key 的哈希值
 *   *  Integer 的哈希值计算
     *  Float 的哈希值计算
     *  Long 的哈希值计算
     *   *  那么， \`^\` 和 \`>>>\` 的作用是什么呢？
         *  为什么用 ^ 而不用 &、| 呢？
     *  Double 的哈希值计算
     *  String 的哈希值计算
     *  自定义对象 的哈希值
 *  自定义对象作为key
 *   *  重写hashCode方法和equals方法
 *  关于使用%来计算索引
 *  易错点总结

# 哈希表完整代码 #

[哈希表完整代码][Link 1]

# 引出哈希表 #

设计一个写字楼通讯录，存放所有公司的通讯信息

*  座机号码作为 key（假设座机号码最长是 8 位），公司详情（名称、地址等）作为 value
 *  添加、删除、搜索的时间复杂度要求是 O(1)

我们用这种思路，将座机号码作为索引值（数组索引），公司详情作为数据元素值（数组的值）。

由于数组添加、删除、搜索元素的时间复杂度都是 o ( 1 ) o(1) o(1)，可以达到要求。

![在这里插入图片描述][20210308100808597.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]

但是这种做法有缺点。

*  空间复杂度非常大  
    要保证存储所有元素，所以需要开辟一个非常大的空间。
 *  空间使用率极其低，非常浪费内存空间  
    就拿电话号码来说，开辟了100000000大小的空间，但是1~99999999之间有很多数字是索引值是用不到的。

其实 数组companies 就是一个哈希表，典型的 【空间换时间】。

# 哈希表（Hash Table） #

哈希表也叫做散列表（hash有“剁碎”的意思）

哈希表是如何实现高效处理数据的？

put("Jack",666);
    put("Rose",777);
    put("Kate",888);

1.利用哈希函数生成 key 对应的 index【 O ( 1 ) O(1) O(1)】

2.根据 index 操作定位数组元素【 O ( 1 ) O(1) O(1)】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]

*  哈希表添加、搜索、删除的流程都是类似的
 *  哈希表是【空间换时间】的典型应用
 *  哈希函数，也叫做 散列函数
 *  哈希表内部的数组元素，很多地方也叫 Bucket（桶），整个数组叫 Buckets 或者 Bucket Array

# 哈希冲突（Hash Collision） #

哈希冲突 也叫做 哈希碰撞

*  2 个不同的 key，经过哈希函数计算出相同的结果
 *  key1 ≠ key2，hash(key1) = hash(key2)

如下图，“Rose” 不等于 “Kate”，但是经过哈希函数算出来的索引确实相同的，此时就产生了冲突。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]  
解决哈希冲突的常见方法

*  开放定址法（Open Addressing） ✓ 按照一定规则向其他地址探测，直到遇到空桶  
      线性探测：往下 一个一个顺序查找，直到遇到空桶  
      平方探测：往下按照平方数顺序查找，直到遇到空桶
 *  再哈希法（Re-Hashing） ✓ 设计多个哈希函数
 *  链地址法（Separate Chaining） ✓ 比如通过链表将同一index的元素串起来

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

*  默认使用单向链表将元素串起来
 *  在添加元素时，可能会由单向链表转为红黑树来存储元素  
     比如当哈希表容量 ≥ 64 且 单向链表的节点数量大于 8 时
 *  当红黑树节点数量少到一定程度时，又会转为单向链表
 *  JDK1.8 中的哈希表是使用 链表+红黑树 解决哈希冲突  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]

思考：这里为什么使用单链表而不是双向链表？

*  每次都是从头节点开始遍历（依次比较每个元素，若有相同key则替换原本的值，若无相同key，则将新元素添加在链表尾部）
 *  单向链表比双向链表少一个指针，可以节省内存空间

# 哈希函数 #

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

1.  先生成 key 的哈希值（必须是整数）
2.  再让 key 的哈希值 跟 数组的大小 进行相关运算，生成一个索引值  
    ![在这里插入图片描述][20210308112431886.png]

◼ 为了提高效率，可以使用 `&` 位运算取代 `%` 运算【前提：将数组的长度设计为 2 的幂（ 2 n 2^n 2n）】  
![在这里插入图片描述][20210308113735804.png]  
将数组的长度设计为 2 的幂（ 2 n 2^n 2n）是因为  2 n − 1 2^\{n - 1\} 2n−1 的二进制必然为全 1

10 - 1 		= 1			2^1 - 1 = 1
    100 - 1 	= 11		2^2 - 1 = 3
    1000 - 1 	= 111		2^3 - 1 = 7
    10000 - 1 	= 1111		2^4 - 1 = 15
    100000 - 1 	= 11111		2^5 - 1 = 31

哈希值的二进制与一个全为1的二进制 `&`(与)，结果必然小于等于哈希值，如下图。  
![在这里插入图片描述][20210308114253982.png]  
◼ 良好的哈希函数，让哈希值更加均匀分布 → 减少哈希冲突次数 → 提升哈希表的性能

# 如何生成 key 的哈希值 #

key 的常见种类可能有

*  整数、浮点数、字符串、自定义对象
 *  不同种类的 key ，哈希值的生成方式不一样，但目标是一致的  
      尽量让每个 key 的哈希值是唯一的
    
      尽量让 key 的所有信息参与运算（即让key的所有数字、内容参与运算）

在Java中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 `null`

## Integer 的哈希值计算 ##

整数值当做哈希值

比如 10 的哈希值就是 10

Java 中 `Integer.hashCode()` 源码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]

## Float 的哈希值计算 ##

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

Java 中 `Float.hashCode()` 源码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]

## Long 的哈希值计算 ##

`Long.HashCode()` ，Java源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]

### 那么， `^` 和 `>>>` 的作用是什么呢？ ###

*  高32bit 和 低32bit 混合计算出 32bit 的哈希值
 *  充分利用所有信息计算出哈希值

`>>>` 即 无符号右移，代码中的 value >>> 32 即将 value 的值无符号右移 32 位。

`^` 即位运算中的异或，它的作用是：两数异或，不同为1，相同为0。

### 为什么用 ^ 而不用 &、| 呢？ ###

*  `& 与`：结果就是低32位，那高32位相当于没参数运算
 *  `| 或`：如果高32位都是1，那么结果全是1，很容易造成哈希冲突
 *  `^ 异`：最合适的，把高32位 和 低32位，全部参与运算

> `>>>` 无符号右移：无论正负数高位全部补0  
> `>>` 有符号右移：正数高位全部补0，负数高位全部补1

![在这里插入图片描述][20210308140625290.png]  
由上图可知，将 64bit 的二进制数字，无符号右移 32bit 后，左边32位必然全为 0（第二行）， 右边则为左32位的数字，`(value ^ (value >>> 32))` 相当于用自己的右32位 异或 自己的左32位，最后`(int)`强转回了 32bit ，相当于把左边的32位全部去掉。这样可以充分利用了自身所有信息来计算哈希值。

## Double 的哈希值计算 ##

`Double.HashCode()` 的计算和 Long 差不多  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]

## String 的哈希值计算 ##

思考一下：整数 5489 是如何计算出来的？

5 ∗ 1 0 3 + 4 ∗ 1 0 2 + 8 ∗ 1 0 1 + 9 ∗ 1 0 0 5 ∗ 10^3 + 4 ∗ 10^2 + 8 ∗ 10^1 + 9 ∗ 10^0 5∗103\+4∗102\+8∗101\+9∗100

字符串是由若干个字符组成的

*  比如字符串 jack，由 j、a、c、k 四个字符组成（字符的本质就是一个整数）
 *  因此，`jack` 的哈希值可以表示为  j ∗ n 3 + a ∗ n 2 + c ∗ n 2 + k ∗ n 0 j \\ ∗\\ n^3 + a\\ ∗\\ n^2 + c\\ ∗\\ n^2 + k\\ ∗\\ n^0 j∗n3\+a∗n2\+c∗n2\+k∗n0  
    等价于 \[ ( j ∗ n + a ) ∗ n + c \] ∗ n + k \[(j\*n + a) \* n + c \] \* n + k \[(j∗n\+a)∗n\+c\]∗n\+k（这样写效率比上面更高）

`new String().hashCode()` 源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]  
由上图可知，在JDK中，乘数n为31，为什么使用31？

*  JVM 会将 31 \* i 优化成 (i << 5) - i
 *   31 ∗ i = ( 2 5 − 1 ) ∗ i = i ∗ 2 5 − i 31 \* i =(2^5-1) \* i = i \* 2^5 - i 31∗i=(25−1)∗i=i∗25−i
 *  31 不仅仅是符合  2 n − 1 2^n − 1 2n−1 ，它是个奇素数（既是奇数，又是素数，也就是质数）
 *  素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突
 *  最终选择 31 是经过观测分布结果后的选择

因此在Java中，下面两种写法完全等价。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]

## 自定义对象 的哈希值 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]

# 自定义对象作为key #

## 重写hashCode方法和equals方法 ##

自定义对象作为 key，最好同时重写 hashCode 、equals 方法，什么时候调用？

*  `hashCode`：计算索引的时候调用，让索引分布均匀，避免哈希冲突，即插入到数组中的哪个位置的时候；
 *  `equals`：当发生哈希冲突，比较两个对象是否相同的时候调用，即在计算完hashCode的之后

equals 用以判断 2 个key 是否为同一个key。

*  自反性  
    对于任何非 null 的 x  
    `x.equals(x)` 必须返回 true
 *  对称性  
    对于任何非 null 的 x、y  
    如果`y.equals(x)`返回 true  
    `x.equals(y)`必须返回 true
 *  传递性  
    对于任何非 null 的 x、y、z  
    如果`x.equals(y)`、`y.equals(z)`返回 true  
    那么`x.equals(z)`必须返回 true
 *  一致性  
    对于任何非 null 的 x、y  
    只要 equals 的比较操作在对象中所用的信息没有被修改  
    `x.equals(y)`的结果就不会变

hashCode

*  必须保证 equals 为 true 的 2 个 key 的哈希值一样
 *  反过来 hashCode 相等的 key，不一定 equals 为 true

◼ 不重写 hashCode 方法只重写 equals 会有什么后果?

✓ 可能会导致 2 个 equals 为 true 的 key 同时存在哈希表中

**不同类型的数据有可能计算出相同的哈希值**，例如 `String类型`的数据与`Double类型`的数据的哈希值可能相同，此时会产生冲突，Java中解决冲突的方法为单链表与红黑树。

当两个 key 不相等，但是哈希值相等时，我们需要用 `equals 方法`来判断两个 key 是否为同一个key，此时就需要重写 equals。

public class Person {
        
    	private int age;
    	private float height;
    	private String name;
    	
    	public Person(int age, float height, String name) {
        
    		super();
    		this.age = age;
    		this.height = height;
    		this.name = name;
    	}
    	
    	@Override
    	/**
    	 * 比较两个对象是否相等
    	 */
    	public boolean equals(Object obj) {
        
    		if(this == obj) return true;
    		if(obj == null || obj.getClass() != getClass()) return false;
    		
    		Person person = (Person)obj;
    		return person.age == age 
    				&& person.height == height
    				&& person.name==null ? name==null : person.name.equals(name);
    				// 传入name若为空，则当前对象name也必须为空才为 true
    				// 传入name若不为空，则调用equals方法比较即可
    	}
    	
    	@Override
    	public int hashCode() {
        
    		int hashCode = Integer.hashCode(age);
    		hashCode = hashCode * 31 + Float.hashCode(height);
    		hashCode = hashCode * 31 + (name!=null ? name.hashCode() : 0);
    		return hashCode;
    	}
    
    }

验证一下重写了`equals`和`hashCode`的作用：

*  由于`重写 hashCode`，p1、p2 哈希值必然相等，则放入 map 会去比较 key
 *  由于`重写 equals`，p1、p2 为同一 key，则 p1 会覆盖 p2

public static void main(String[] args) {
        
    	Person p1 = new Person(18, 1.75f, "jerry");
    	Person p2 = new Person(18, 1.75f, "jerry");
    	// 由于重写 hashCode(),p1、p2哈希值必然相等
    	
    	Map<Object, Object> map = new HashMap<>();
    	map.put(p1, "abc");
    	map.put("test", "bcd");
    	// 由于 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` 是最稳妥的做法。

# 关于使用%来计算索引 #

◼ 如果使用%来计算索引

*  建议把哈希表的长度设计为素数（质数）
 *  可以大大减小哈希冲突

10%8 = 2     10%7 = 3  
20%8 = 4     20%7 = 6  
30%8 = 6     30%7 = 2  
40%8 = 0     40%7 = 5  
50%8 = 2     50%7 = 1  
60%8 = 4     60%7 = 4  
70%8 = 6     70%7 = 0

◼ 下表格列出了不同数据规模对应的最佳素数，特点如下

*  每个素数 略小于 前一个素数的 2倍
 *  每个素数尽可能接近2的幂（ 2 n 2^n 2n）  
    ![在这里插入图片描述][20210309091718163.png]

# 易错点总结 #

*  哈希值相等，根据哈希函数求的索引必然相等
 *  哈希值不相等，根据哈希函数求的索引有可能相等  
    原因是`hash_code(key) & (table.length - 1)`取模运算可能会遇到相等的情况  
    可以理解为 2 % 3 = 2，5 % 3 = 2，2 和 3 不相等，%3 的结果却相等
 *  HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为null

[Link 1]: https://blog.csdn.net/qq_32727095/article/details/114537712
[20210308100808597.png]: /images/20221023/0ac69f0453cf4f0ea4dacb2d57cd878e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221023/b3db648ff82146f6a03e3b98c593efd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221023/f8d56718b22c40f785424bae6e186cf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: /images/20221023/76e9e2a3323148408713553744a6b2a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: /images/20221023/e5953dd750794a0caa5e8755999d122d.png
[20210308112431886.png]: /images/20221023/e71744c14aab48898243701378a2f6b1.png
[20210308113735804.png]: /images/20221023/e8f6a84f64754b2da2e96e873bd838ea.png
[20210308114253982.png]: /images/20221023/7dfee7c30e00453e987b9ed83e77e1da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]: /images/20221023/24a7fd1379e84cdcb97ef7daaf7e337b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]: /images/20221023/141e8256fd044d3589ad1f4a3a4d1898.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]: /images/20221023/e3f0e01dbd7a4cf9b9f762576fd7f5ec.png
[20210308140625290.png]: /images/20221023/1209c11d43784901af640edbec96b101.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]: /images/20221023/85e2b6d9a64a409a865e452b5109f43f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]: /images/20221023/f72b70bb5d474a249b663c4e061f1092.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]: /images/20221023/1599dff9c5dc42d4ba521e76fab2a46b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]: /images/20221023/f50c194402db42cb9eb922e52a14202b.png
[20210309091718163.png]: /images/20221023/db763d1859224cc8831ca5d8c97b468f.png