HashMap

1. HashMap简介

HashMap - 顾名思义，就是用哈希表存储键值映射，实现通过关键字查找对应值的功能；哈希表就是一种用于高效查找的数据结构。

2. 哈希表

哈希表（Hash Table），又称为散列表，本质上是一个数组，其作用是能够对大量的无规律数据进行高效的随机存取操作。

2.1 实现思想

哈希表的思想就是在元素的存储位置（实际就是数组的下标）和元素的特征值（这个特征值可以是元素的值，关键字或其他可以标识该元素的属性）之间建立某种直接关系，那么在进行存取时，就无需做比较或只做很少次的比较，按照这种关系就可以直接由特征值找到相应记录的位置；

2.2 为什么要使用哈希表

比如你有大量的字符串，现在要对这些字符串进行任意的随机存取操作，因为要进行随机存取操作，所以适合采用顺序存储法，可以将这些字符串存储到一个数组中；这个时候，如果你要查找某一个字符串，就必须遍历数组，与数组元素进行挨个比对，这十分的低效，同时由于元素是字符串，而折半查找或者构造2叉搜索树等方法，都需要对元素进行排序，而对大量的字符串进行排序操作本身也是非常低效的操作。有什么方法能够对这些字符出进行高效的存取呢？我们可以采用哈希表，用某种计算法将字符串的特征值和数组的下标关联起来，这样在进行查找的时候，通过计算就可以对需要查找的值进行快速定位。

在计算机系统中，对于数据集合的存储方式有两种，一种是顺序存储法（数组，向量，矩阵就是顺序存储法），一种是链式存储法（比如链表，树，图都是链式存储）；

2.3 如何实现哈希表

要实现哈希表，需要考虑三个问题：1. 构造哈希函数；2. 处理哈希冲突；3. 调整装填因子

2.3.1 构造哈希函数

哈希函数就是用来计算元素的哈希地址的方法 index=hash(key，length)，其中 index 就是哈希地址，实际就是数组下标，key 是元素的特征值，length 是哈希表数组的长度，index 的值需要小于 length。
构造哈希函数的方法很多，应根据具体问题构造不同的函数，通常应遵循2个原则，考虑4个因素；

构造哈希函数需要遵循的两个原则：

1. 函数计算要简单，每一个特征值只能有一个哈希地址与其相对应；
2. 计算出的哈希地址的范围必须在数组长度范围内，并且分布应均匀，尽可能的减少冲突；

构造哈希函数时需要考虑下面4个因素：

1. 哈希表的长度（也就是数组的大小）；
2. 元素特征值分布情况；
3. 哈希函数的计算时间；
4. 记录的查找频率；

根据这两个原则和四个因素，我们可以看到，高效的哈希表实现一定具有良好的特征值分布和适当大小的长度以及高效的哈希函数；良好的特征值分布和适当的长度可以使计算出的哈希地址尽量均匀，从而减少冲突；而高效的哈希函数可以快速的计算出哈希地址；

2.3.2 处理哈希冲突

在实际应用中，可以尽量减少哈希冲突，但却不可避免，所以就需要处理哈希冲突，一般处理哈希冲突的方法有两种：

• 开放地址法；基本思路就是把元素都存储到哈希表的数组中，当发生哈希冲突时，就在冲突地址的基础上选择合适的计算方法（比如线性探测法、二次探测法、伪随机探测法）重新计算新的地址，直到不发生冲突为止；
• 链地址法；基本思路就是把具有相同哈希地址的元素保存在同一个单链表中，而将单链表的头部元素存放到哈希表的数组中；当发生哈希冲突时，只需要把发生冲突的元素插入到对应哈希地址的链表的尾部即可；

而在实际应用中，由于开放地址法可能发生二次聚集现象（线性探测法）以及不能保证一定找到不发生冲突的地址（二次探测法和伪随机探测法）等问题，所以一般都采用链地址法；而链地址法并不局限于只采用单链表来保存发生冲突的元素，我们知道，单链表进行随机查找的效率是很低的，需要进行遍历比对，所以当某一个地址冲突的元素很多，链表很长，并且查找频率又比较高时，这时查找的效率就会很低，此时再采用单链表就不是很好，可以转化成为其他数据结构以提高查询效率。

2.3.3 调整装填因子

影响到哈希表性能的第三个因素就是装填因子，装填因子定义为 α = 记录数 / 表长度；装填因子 α 表示哈希表的装满程序，根据哈希表的实现思想我们可以看到，哈希冲突的可能性和装填因子成正比，α 越大，表示表中的记录越多，再加入新元素时，发生冲突的概率就越大，查找时，需要进行链表比对的次数也就越多；但是，过低的装填因子虽然有好的查找效率，但是却浪费了存储空间，因此在实现哈希表时，需要确定将装填因子的上限保持在某个水平，如何确定装填因子的上限呢？我们看下表：其中 α 表示装填因子

用几种不同方法处理冲突时哈希表的平均查找长度 - 表选自《数据结构》（严蔚敏）第二版
我们看到哈希表的平均查找长度与装填因子直接相关，可以根据上表按照具体的需要的查找效率来计算装填因子的上限，从而调整哈希表的大小，保证存储空间充分利用的同时，哈希冲突能够保持在一个合理的程度。

3. JDK中HashMap的实现

上一章我们讨论了要实现一个高效的哈希表需要考虑的三个问题，本章我们看看JDK在实现 HashMap 的过程中，是如何解决这三个问题的。

3.1 HashMap的哈希函数

HashMap 通过 key 的 hashCode 经过扰动函数 (h = key.hashCode()) ^ (h >>> 16) 处理过后得到 hash 值，然后通过 (n - 1) & hash（这里的 n 指的是数组的长度）计算key 的哈希地址（数组下标）；我们可以看到HashMap使用扰动过的hashCode作为key的特征值来计算哈希地址，这是因为hashCode默认是由对象的内存地址转化而来，而对象存储在内存的哪一个位置是完全随机的，并且符合均匀分布，但是因为Object的hashCode的方法可以被子类重写，因此为了防止那些由重写的hashCode方法生成的hash码的分布情况不够均匀，因此加入了扰动函数。
从 HashMap 的哈希函数的源码我们可以看到，HashMap 默认选择由元素的内存地址转化的 hashCode 作为元素特征值来计算哈希地址，这样的特征值符合均匀分布，使计算出的哈希地址尽量均匀，使哈希冲突发生的概率尽可能小；同时 HashMap 使用了1次移位，2次逻辑运算就能够计算出哈希地址，简单高效。

(h = key.hashCode()) ^ (h >>> 16) 表示：将 key 的 hashCode 的低16位与高16位进行异或。

3.2 HashMap的冲突处理机制

HashMap 采用链地址法来解决哈希冲突；HashMap 将哈希地址冲突的元素保存在一个单链表中，哈希地址对应的数组位置保存该单链表的头节点；当单链表的长度大于阈值（默认为8），此时如果哈希表的长度大于等于64，单链表就会转化成为一颗红黑树，以加快查找速度，否则就要进行扩容resize操作。
HashMap 这种冲突处理机制，不会出现二次聚集，可能无法找到无冲突地址的问题，并且查找效率高，插入移除元素易于实现，而且因为节点是动态生成的，特别适合哈希表的长度需要经常变化的情况。

3.3 HashMap的装填因子

HashMap 默认的装填因子临界值是0.75，为了保证哈希表的查询效率，HashMap 会动态调整哈希表的大小，就是进行 resize 操作，来保持装填因子不大于0.75。
HashMap 每次进行 resize 操作，首先分配一个长度是旧表2倍的新表，然后遍历旧表中的所有元素，重新计算每一个元素在新表中的哈希地址，让后将元素插入到新表中，这个过程称为rehash，再哈希过程中，如果发生碰撞，还需要重新构建链表。
动态扩容机制可以使HashMap的装填因子始终不超过临界值，保证了查找效率，同时又提高了存储空间的使用效率。但是由于动态扩容操作需要进行 rehash 操作，尤其是当使用HashMap保存大量键值对的时候，rehash 会非常耗时，从而引起程序响应性问题。

3.4 HashMap小结

通过上一章的讲解我们可以总结出 JDK 在实现 HashMap 时采用了以下方法和机制：

1. 默认使用对象内存地址转化而来的hashCode作为特征值来计算哈希地址，因为默认的hashCode符合均匀分布，可以将哈希碰撞的可能性降低到最小；
2. 使用移位和逻辑运算计算哈希地址，因为在计算机系统中，移位运算和逻辑运算比数学运算要快的多，所以使用移位和逻辑运算计算哈希地址，简单高效；
3. 使用拉链法来解决哈希冲突，当单链表的长度大于阈值（默认为8），哈希表长度大于64时，单链表会转化成为红黑树，保证哈希查找的效率；
4. 采用动态扩容机制保证装填因子始终不超过临界值，保证了查找效率，同时又提高了存储空间的使用效率。

4. 使用优化

虽然JDK中的 HashMap 是一种高效的哈希表实现，但我们在使用过程中仍然需要注意以下问题：

1. 因为 Object 的hashCode方法可以被子类重写，虽然 HashMap 使用了扰动函数，但是如果重写的hashCode 方法返回的值的分布状态非常不均匀，那么即使在装填因子很低的时候，仍然会发生大量的哈希碰撞，导致查询效率变低。因此如果需要重写键对象的 hashCode 方法，那么应当确保重写后的hashCode 方法返回的哈希码要符合随机的均匀分布。
2. 因为动态扩容机制虽然使HashMap的装填因子始终不超过临界值，保证了查找效率，提高了存储空间利用率，但是动态扩容导致的 rehash 是一项很耗时的操作，尤其当 HashMap 很大时，需要在使用时尽量避免动态扩容（resize）操作。这就需要在使用时根据应用场景，事先规划 HashMap 的容量大小和装填因子，在创建时就指定表长度和装填因子。当然在实际应用中，无法一开始就确定 HashMap 的合适大小，可以先对需要优化使用的HashMap 进行监控，收集其每次动态扩容时元素的数量，集合的大小，以及耗时等指标信息，然后再进行评估优化。

5. HashSet

java.util.HashSet<T> 是 Set 的实现类，是一种集合，集合的最主要特性就是互异性（就是集合中任何两个元素都认为是不相同的，即每个元素只能出现一次）；HashSet 是使用装饰器模式利用 HashMap 实现的集合类，底层就是一个 HashMap，插入 HashSet 的元素作为键值和一个默认作为值的对象 PRESENT 组成键值对存储在HashMap 中，HashSet 利用 Map 键值的不可重复特性来保证 Set 元素的不可重复特性，HashSet 是采用哈希表来保存元素的的集合类，可以对元素进行排重，同时又能够对这些数据进行高效的查询。

HashSet 类的主要属性：

private transient HashMap<E,Object> map; //用于存储元素的HashMap
private static final Object PRESENT = new Object(); //一个静态的全局对象PRESENT，作为元素的value