java--HashMap数据结构( 三 ) _数组

功能实现-方法
的内部功能实现很多，本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入展开讲解。
1. 确定哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过的数据结构是数组和链表的结合，所以我们当然希望这个里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。定位数组索引位置，直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):
这里的Hash算法本质上就是三步：取key的值、高位运算、取模运算。
对于任意给定的对象，只要它的()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。
这个方法非常巧妙，它通过h & (table. -1)来得到该对象的保存位，而底层数组的长度总是2的n次方，这是在速度上的优化。当总是2的n次方时， h& (-1)运算等价于对取模，也就是h% ，但是&比%具有更高的效率。
在JDK1.8的实现中，优化了高位运算的算法，通过()的高16位异或低16位实现的：(h = k.()) ^ (h >>> 16) ，主要是从速度、功效、质量来考虑的，这么做可以在数组table的比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
下面举例说明下， n为table的长度。
2. 分析的put方法
的put方法执行过程可以通过下图来理解，自己有兴趣可以去对比源码更清楚地研究学习。
①.判断键值对数组table[i]是否为空或为null ，否则执行()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i ，如果table[i]==null ，直接新建节点添加，转向⑥ ，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value ，否则转向④ ，这里的相同指的是以及；
④.判断table[i] 是否为，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i] ，判断链表长度是否大于8 ，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量，如果超过，进行扩容。
JDK1.的put方法源码如下:
3. 扩容机制
扩容()就是重新计算容量，向对象里不停的添加元素，而对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。