类介绍
类定位
HashMap是一个使用哈希方法存储元素实例的Map。在大多数情况下，HashMap有着比TreeMap更加优秀的效率，所以在我们的编程中，如果要用到Map，Map<XX,XX> temp = new HashMap<>()几乎是下意识的代码。这篇文章主要介绍HashMap的工作原理，由于HashMap的原理较复杂，源码介绍无法一个方法一个方法的来，我们这次主要介绍HashMap的实现思想和类的架构，并对关键代码进行粘贴和注释。
类继承关系分析
1.png
可见，和TreeMap不同的是，HashMap没有实现SortedMap、NabvigateMap的一些方法，而是专心的实现Map中预定义的方法。还有就是一些通用的东西：
- 实现了
Serialable，可以进行序列化和反序列化 - 实现了
Cloneable，可以进行浅拷贝
注意事项
在Java8 的HashMap源码中依然使用了红黑树的算法和思想，我们接下来会介绍。红黑树的要求和之前的TreeMap是一样的，只是实现略有不同，这里就不再详细解释了，如果想看可以去刷一下HashMap的TreeNode源码。
算法介绍
本节主要通过流程图和结构图的方法对HashMap的工作原理进行介绍，以期读者能对HashMap的工作原理和演进有大概的理解。方便接下来对源码的理解。
哈希算法分析
散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。
优秀hash算法的特点
一个优秀的 hash 算法，将能实现：
- 正向快速：给定明文和 hash 算法，在有限时间和有限资源内能计算出 hash 值。
- 逆向困难：给定（若干） hash 值，在有限时间内很难（基本不可能）逆推出明文。
- 输入敏感：原始输入信息修改一点信息，产生的 hash 值看起来应该都有很大不同。
- 冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。即对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。
常见的简单hash方法思路
哈希值计算方法，常见的方法有：
- 加法hash
- 所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果
- 【此处可以参考
Collection系列类的哈希值，他就是把每个元素的哈希值加起来】
- 位运算hash
- 这类型Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素
- 【
HashMap使用的是位运算的方法计算哈希值，用数学的话描述是除数组长度取余】
- 乘法hash
- 这样的类型的哈希函数利用了乘法的不相关性.乘法哈希里最有名的就是adler32，reactJS的checksum校验就是使用的adler32的改良版。
- 除法hash
- 和乘法一样用了不相关性，但性能不好。
- 查表hash
- 混合hash
- 混合Hash算法利用了以上各种方式。
流行的hash算法
MD5,SHA 等算法
HahsMap实现结构及演进分析
我们以HashMap的插入为引入介绍哈希算法：
2.png
从流程图上容易看出：一个是哈希值计算方法、一个是解决位置冲突问题的方法。对HashMap的实现有着较大的影响。哈希值计算方法我们上面已经介绍过了。
解决位置冲突的方法，常见的方法有：
开放定址法【从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。】
- 线性探查法【从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止】
平方探查法【平方探查法即是发生冲突时，用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²...直到找到空闲单元】
- 双散列函数探查法【这种方法使用一个双散列函数，有兴趣自己去搜】
拉链法【链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。】【java7 就使用此方法，java8在7的基础上进行了改造】
再哈希法【就是同时构造多个不同的哈希函数，当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。】
建立公共溢出区【将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区】
java7的HashMap
话不多说，先上图：
3.png
注意：图只是示例图，不要纠结阈值还有扩充数组长度的问题，这个我们后面会专门介绍。
java7 获得初始位置的方法
java7计算hash值的方法是元素hash值除以数组长度取余，也就是说假设数组长度是y，新来元素的hash值是x，则计算出的初始位置是X%Y。在源码中是使用位运算实现的：
4.png
通过图片我们对比可知，X%Y十进制取余和二进制效果一样。
java7 解决冲突的方法
通过图片我们可以看出，java 7的HashMap解决冲突的方法是拉链法。
java7 其他要注意的地方
在扩展数组空间后，同一个位置的链可能会有一部分被分到新的位置，java7的算法源码如下：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新的数组
Entry[] newTable = new Entry[newCapacity];
// 将原来数组中的值迁移到新的更大的数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable){
Entry[] src=table;
int newCapacity=newTable.length;
for(int j=0;j<src.length;j++){
Entry<K, V> e=src[j];
if(e!=null){
src[j]=null;
do{
Entry<K, V> next=e.next;//保存下一次循环的Entry
//在新的table 中求得适合插入的位置
int i=indexFor(e.hash, newCapacity);
e.next=newTable[i];// 如果I位置原来没有值，则直接插入；有值，采用链头插入法
newTable[i]=e;
//轮替，下一次循环
e=next;
}while(e!=null);
}
}
}
由于transfer是头插，所以插入后会出现元素顺序相反的情况：比如原来的链表中A在B前面，移动到新位置后A到B后面了。这种结构会有极端情况发生：
当多线程对
HashMap进行操作时【当然这是不对的】，有可能会出现死循环而不是fail-fast机制抛出的异常。【具体分析自行搜索，java7的HashMap不是重点，不再做分析】
java8的HashMap
先上图：
5.png
java8中的HashMap主要对java7中的HashMap做了一些算法上的优化。优化点罗列如下：
-
极端情况下，所有的元素都挤到一个位置，查找的效率会从O(1)下降至O(n)，所以java8在链较短时仍然使用链表，在链表较长时使用红黑树实现
-
java7在拆分链表进行扩容时存在新链表元素逆序的情况，所以java8所有新生成的链表要求元素仍然保持原链表中的顺序
-
java7在扩容时要重新计算元素的新位置，实现思路是仍然调用根据hash求下标的方法，java8找到其中的规律，简化了计算
由于每次数组扩容都是变为二倍，元素要不是在原位置，要不是增加一个原数组的长度Y，我们依然从二进制的角度来介绍这个情况：
6.png
可见，数组扩容后其实就是（Y-1）的二进制位多了一个1，联想到网络的子网掩码也就是掩码长度多了1，所以决定元素在扩容后数组的位置是原长度的最高位对应的hash位是0还是1
-
java8修改了根据hash求初始位置的方法，支持了
Object作为key，同时修改了位运算的方法：
java8认为如果只看低n位会增加碰撞，所以引入高16位对低16位的影响
// JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
// 1. 取hashCode值： h = key.hashCode()
// 2. 高位参与低位的运算：h ^ (h >>> 16)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
// a. 当key = null时，hash值 = 0，所以HashMap的key 可为null
// 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
// b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
}
增
7.png
删
8.png
改
其实对HashMap来说，添加操作就是put()，它的意思是如果你传入的key已经有了，就是覆盖它，然后返回原值；如果你传入的key在Map中不存在或者对应的value是null，就新建节点或者覆盖null，并返回null。
当然也有putIfAbsent()，只有在没有该节点不存在时才添加，不覆盖。
查
数据结构都知道了，没啥说的，无非是hash查找、树查找、链表遍历结合起来而已。
源码介绍
源码介绍主要分成两种，一种是HashMap独有的主要的功能实现方法，包括某些内部类和增删方法；一种是常用的套路方法，包括惯有的一堆Iterator,Set,Collection之类的内部类，还有一些常见的get(),put()方法。
我们对第二种方法直接忽略，主要看HashMap的实现。同时，第一种中的红黑树相关的算法确实是有点复杂，因为这里的红黑树不仅要维持红黑树的相关性质，还要维持链表的next链接顺序，不能随意旋转。所以，我们不做过多介绍，毕竟红黑树掌握原理即可，不专门研究没必要全弄通。
内部类介绍
TreeNode
继承关系
9.png
至于这个奇妙的依赖关系，我也是醉了，这个应该是最开始设计时就有的问题:
- 父类的实现依赖子类中的内部类，这不符合java编程中的单向依赖的规范。
- 经查验，
LinkedHashMap.Entry只增加了两个变量，方便双向查找；HashMap.TreeNode也用到了这个特点来方便进行树调整。LinkedHashMap.Entry代码及其简单，而且没有明显体现出LinkedHashMap的特点，将其调整至HashMap也并无大错，毕竟HashMap也依赖链表数据结构。
以上为个人观点，仅记录于此。
功能及角色
TreeNode中实现了红黑树的基本方法，包括红黑树的增、删、改、查、HashMap扩容时的分裂、链表改树、树改链表等操作。
代码太多太杂，这里不做粘贴解释。
增/改
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 数组为空，先新建数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算出的地址可用，直接放这里即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 计算出的地址已经元素，且此元素的key是和传入key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 此位置的元素是一个树的，进行树的增/改
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 此位置的元素是一个链表的头
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 遍历到达表尾，做节点插入操作
p.next = newNode(hash, key, value, null);
// 看看链表是否够长，够长则转化成红黑树以增加查找效率
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 在链表中找到了key和传入key相同的元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 在HashMap中查到了相同key，根据入参判断是否覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 没有相同key，HashMap中新增了元素，修改Count++，同时判断是否需要扩容
++modCount;
if (++size > threshold)
resize();
// 可以理解为预留的插入完成的钩子，用户可以根据自己的需求进行复写，
// 比如插入后要打印一条日志啥的，就在这个函数里编码实现
afterNodeInsertion(evict);
return null;
}
删
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 兴许有的删
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 找到了要删的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 从树里面找要删的元素
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 从链表里面找要删的元素
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 找到了要删的元素
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 在树里就用树的方法删
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 数组中hash计算出来的那个就是要删的元素
else if (node == p)
tab[index] = node.next;
// 从链表中找到了要删的元素
else
p.next = node.next;
// 删完做相应的善后
++modCount;
--size;
// 和增/删的那个一样，也是个钩子
afterNodeRemoval(node);
return node;
}
}
// 没得删
return null;
}
查
不说了，太简单。
扩容
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 现在的数组已经是最大的了，直接把阈值调整到MAX，以后不会再触发阈值，也不会再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 数组大小合法，可以扩充，扩充数组和阈值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 旧数组为空，但是阈值有初始化，用预设阈值为新数组长度进行初始化
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 啥都没设，用默认的数组、阈值初始化
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 旧数组为空，但是阈值有初始化；旧数组太小或者新数组太大
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 接下来进行空间申请和数据迁移
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 旧位置置空
oldTab[j] = null;
// 单元素，直接转到新数组中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 是树，用树的方法进行拆分和转移
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 是链表，根据每个元素的hash在保证链表元素顺序的前提下进行数据迁移
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
常量分析
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
- 默认初始化数组长度：
DEFAULT_INITIAL_CAPACITY - 最大数组长度：
MAXIMUM_CAPACITY - 默认阈值占比：
DEFAULT_LOAD_FACTOR - 链表转树长度：
TREEIFY_THRESHOLD - 树降级成链表长度：
UNTREEIFY_THRESHOLD - 链表转树前置条件。数组长度限制
MIN_TREEIFY_CAPACITY
使HashMap工作效率更高效化的几个建议
-
合理的设置初始化空间和阈值比例
- 初始化空间太大浪费内存、太小刚开始就得扩充
Map - 阈值比例太大，
HashMap碰撞严重，会影响搜索效率；阈值太小不仅会造成存储的浪费，频繁的扩容导致HashMap不停搬运数据，会占用很多的资源
- 初始化空间太大浪费内存、太小刚开始就得扩充
-
如有需要，可以自己扩展
HashMap，自己复写常用的钩子来进行定制化操作
参考文献
- https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8
- https://blog.csdn.net/carson_ho/article/details/79373026
- https://blog.csdn.net/yangyingbofx/article/details/51347477
- https://blog.csdn.net/q291611265/article/details/46797557
- http://www.importnew.com/20386.html
- https://www.jianshu.com/p/bf1d7eee28d0
网友评论