JDK1.8 HashMap 总结
- JDK1.8 HashMap源码解析 目录
概论
- HashMap 是无论在工作还是面试中都非常常见常考的数据结构。比如 Leetcode 第一题 Two Sum 的某种变种的最优解就是需要用到 HashMap 的，高频考题 LRU Cache 是需要用到 LinkedHashMap 的。
- 随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。
- HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。
- HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
- HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
Hasmap 的继承关系
Hashmap 的原理
1、对于 HashMap 中的每个 key，首先通过 hash function 计算出一个 hash 值,这个hash值经过取模运算就代表了在 buckets 里的编号 buckets 实际上是用数组来实现的，所以把这个hash值模上数组的长度得到它在数组的 index，就这样把它放在了数组里。
2、如果果不同的元素算出了相同的哈希值，那么这就是哈希碰撞，即多个 key 对应了同一个桶。这个时候就是解决hash冲突。
3、随着插入的元素越来越多，发生碰撞的概率就越大，某个桶中的链表就会越来越长，直到达到一个阈值，HashMap就受不了了，为了提升性能，会将超过阈值的链表转换形态，转换成红黑树的结构，这个阈值是 8 。也就是单个桶内的链表节点数大于 8 ，就会将链表有可能变身为红黑树。（树化的条件是：桶中链表的长度达到了8,并且数组的长度大于等于64。）
解决Hash冲突的方法
开放定址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H(key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
Hi=（H（key）+di）% m i=1，2，…，n
其中H(key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有三种 线性探测再散列，二次探测再散列，伪随机探测再散列.
再哈希法
这种方法是同时构造多个不同的哈希函数
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间.
链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。
链地址法适用于经常进行插入和删除的情况。
建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
Hashmap 最终的形态
HashMap主体上就是一个数组结构，每一个索引位置英文叫做一个 bin，我们这里先管它叫做桶，比如你定义一个长度为 8 的 HashMap，那就可以说这是一个由 8 个桶组成的数组。
当我们像数组中插入数据的时候，大多数时候存的都是一个一个 Node 类型的元素，Node 是 HashMap中定义的静态内部类。
在集合初始化时，指定集合初始值大小。
见《阿里编程规范》第一章 1.5集合处理章节第9条。
- 在需要存储的数据个数确定的情况下，指定集合初始值大小。
- initialCapacity = （需要存储的元素个数 / 负载因子） + 1.
对红黑树的理解
- 1、每个节点非红即黑
- 2、根节点总是黑色的
- 3、如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
- 4、每个叶子节点都是黑色的空节点（NIL节点）
- 5、从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置。
重新调整HashMap大小存在什么问题吗？
- 当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。(多线程的环境下不使用HashMap）
- 为什么多线程会导致死循环，它是怎么发生的？
- HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时候，HashMap需要扩展它的长度，也就是进行Resize。
- 1.扩容：创建一个新的Entry空数组，长度是原数组的2倍。
- 2.ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。
- HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时候，HashMap需要扩展它的长度，也就是进行Resize。
链表法导致的链表过深问题为什么不用二叉查找树代替
之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。
而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。
JDK8中对HashMap做了哪些改变?
在 JDK1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。（桶的数量必须大于64，小于64的时候只会扩容）
发生hash碰撞时，JDK 1.7 会在链表的头部插入，而 JDK1.8会在链表的尾部插入
在 JDK1.8中，Entry被Node替代
Hashmap 的容量大小为什么要求是2^n?
前提
元素在数组中的位置的计算方式是: tab[i = (n - 1) & hash] 。也就是通过对数组大小求模得到的，因为我们知道hash 的计算方式是 hashCode() 的高 16 位异或低 16 位实现的，32 位值只要有一位发生改变，整个 hash() 返回值就会改变，也就是说我们的hash 值发生冲突的概率是比较小的，也就是说hash 值是比较随机的。
冲突发生时
更多的冲突是发生在取模的时候，所以这个时候只要保证了我们的取模运算 (n - 1) & hash，尽量能保证hash 值的特性也就是随机性。因为我们知道与运算的特点是,两位同时为“1”，结果才为“1”，否则为0。
这个时候我们只要 (n - 1) 让的二进制表示都是一串1，例如"011111" 就可以了，因为安位与1 结果是不变的，也就是可以延续hash 值的散列性。
2n次方的二进制表示
2的6次方，就是从右向左 6 个 0，然后第 7 位是 1。
why?
只有数组的长度是2的次方了，n-1 的二进制才能尽可能多的是1 !
你觉得Hashmap 还有什么可以改进的地方吗，欢迎讨论
虽然java 源代码的山很高，如果你想跨越，至少你得有登山的勇气，这里我给出自己的一点点愚见，希望各位不吝指教
