1.HashMap简介
HashMap类图
HashMap核心是维护一张哈希表，这张哈希表是用一个Entry数组实现的。
哈希表访问时，只需要通过函数映射即可以找到对应元素位置，一般来说时间复杂为O（1）。
HashMap是一个用来存储Key和Value的一种数据结构。
HashMap继承AbstractMap，AbstractMap实现Map接口，实现相关的增删改查等操作。
HashMap实现了Cloneable和Serializable，能够克隆和序列化。
2.HashMap数据结构
HashMap底层维护者一个Entry数组，Entry是一个静态内部类，这个Entry数组也就类似于一个哈希表。
静态内部类Entry
从这个Entry的源码中可以发现，他存储了Key和Value，指向下一个Entry的引用，缓存了Hash值，HashMap在JDK1.7中是以拉链法来解决冲突的。
数据结构图大概如下图所示：
数据结构
3.HashMap的内部类
HashMap中定义了一个抽象的静态内部类HashIterator，这个类实现了Iterator，HashIterator的子类ValueIterator、KeyIterator、EntryIterator为HashMap提供了用迭代器访问的支持。
Iterator
HashMap还有一个静态内部类EntrySet，相当于是HashMap的一个视图，但是这个EntrySet不是实际存在，相关的操作实际上还是从HashMap上进行操作，所以对EntrySet的改变会影响HashMap。
EntrySet
4.从put操作分析HashMap
put操作
上图是HashMap的put操作，我们分析其中几个关键的地方。
首先是inflateTable（），这个方法为Entry数组分配实际的内存空间。
inflateTable
其中roundUpToPowerOf2()方法，调用了Integer.highestOneBit((number - 1) << 1) ,这个方法的实现是通过位运算实现的：
highestOneBit
通过这个方法，可以取到二进制位最高位，将(number - 1) << 1取最高位，即是最小的大于等于toSize的数,切是2的N次方。
为什么number要减一呢？因为是要大于等于，防止出现恰好相等的情况。
然后我们分析一下indexFor（），用来计算Key在HashMap中的位置。
indexFor
这也是一个用位运算来计算的。这里也是源码作者为什么要用size=2^n的原因之一。我们进行计算位置的时候，一般都是通过hash%size，但是取模这种运算效率不高。我们可以发现，一个数X对一个2的N次方的数Y取模，得到的结果值也就是X值的低N-1位，如果对一个2的N次方的数Y减一，得到的数二进制位都为1，和一个数X进行与运算，得到的值也是X值的低N-1位。所以源码作者用位运算来提高HashMap的效率。
然后我们分析一下addEntry()：
addEntry
在这个方法中，如果size是否达到扩容阀值，并且发生了哈希冲突，我们就进行扩容操作(从这我们发现，HashMap如果达到扩容阀值是不一定会进行扩容的，还要发生哈希冲突才会)，扩容操作其实很简单，计算新的容量（oldSize*2），然后判断是否等于最大容量，如果等于就不进行扩容了。如果小于，new一个新的Entry数组，将原来Entry数组中的元素，根据新的size重新计算位置，转移到新的Entry数组中去。扩容完成后，然后在对应位置的链表表头插入Entry就完成了put（）操作。
5.HashMap相关的一些问题
1.负载因子是做什么用的？为什么是0.75？
在JDK1.8源码中才找到一段话：
负载因子
大概意思是，使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素的个数和概率的对照表。
从上表可以看出当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为负载因子，每个碰撞位置的链表长度超过8个是几乎不可能的。（上面的是网上找到的）
如果我们负载因子太小，HashMap扩容频繁，浪费空间，负载因子太大，HashMap冲突频繁，浪费时间。所以折中取了0.75。
2.HashMap的死链是如何发生的，在代码什么位置会导致此问题？
经过分析，HashMap死链的生成是在扩容时，进行transfer()时候产生的。
transfer
假设有两个线程在对一个HashMap进行扩容操作：线程一运行transfer（） 05行的时候挂起：
状态一
线程二完成所有的扩容操作，此时状态如下图：
状态二
然后线程一继续执行，执行完成后，就形成死循环了：
状态三
网友评论