HashMap的添加元素过程以及其put方法

元素过程以及其put方法"/>

HashMap的添加元素过程以及其put方法

HashMap是双列集合中的一种，也是我们平时开发过程中常用的一种集合。本篇文章主要以源码的角度讲其添加过程以及put方法中的细节

HashMap扩容机制

Hashmap在jdk1.7以前所采用的数据结构为数组+链表的形式，而在jdk1.8以后引进了数组+链表+红黑树的结构，在同时满足数组长度大于64，链表长度大于8的时候，就会转成红黑树结构。

1.在实例化一个HashMap的时候，此时不会分配内存空间。

2.在第一次添加值的时候，HashMap的底层会创建一个初始长度为16的数组（这个量在与HashMap源码中有定义）

3.添加数据的时候，根据所存储的键的hash值计算出应存入数据的下标来确定数据所处位置，当这个位置原本没有数据的时候，则会直接将数据存入，如果原位置有值，且此时数据与原数据的hash值相等，且原本key的值本身与将要添加的key值相等，则对原值进行覆盖，并且此时的put方法返回值由null变为被此时元素的value。源码中是用这样一个表达式进行判断的

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

4.如果不满足这个式子，则会将此时要添加的数据“挂在”原数据的下面变成一个链表的结构，原数据的next属性将会记录此时所添加数据的地址。

5.还需要注意的一点是HashMap中有一个值来确定什么数组时候扩容，如果在构造时没有赋予该值，则会使用默认值：0.75。即当数组容量达到长度的百分之75的时候，会扩容为原来的2倍（数组刚分配空间是长度为16，当容量达到12时，会抛弃原数组，然后生成一个新的长度为32的数组，并且将原数组元素一一复制，而此时容量达到24时会继续进行扩容）。

6.而当在同时满足数组长度大于64，链表长度大于8的时候，此时链表就会转成红黑树结构。

put方法细节：

put方法就是HashMap在添加元素的时候用到的方法，也是面试中常常考察到的一点，先给大家以八股文的角度回答一下关于put方法的面试问题，这样有助于大家理解后面的源码

1.put方法在存入键值对的过程中，首先会对调用key的hashCode方法计算出key的hash值，但是这个值并不会直接存入到HashMap中，而是在put方法里调用了一个方法进行了一个这样的运算：hash=hash^(>>>16)后再存入

2.然后判断HashMap是不是刚刚初始化的，如果是，则会先为其分配内存空间，初始容量为16，扩容因子为0.75（这是jdk1.8以后的操作，jdk1.7之前在创建以后会直接分配内存）

3.接下来用此时所计算出来的hash的值来判断所存储数组的下标位置，如果该位置此时没有元素，直接添加。如果该位置此时有元素则会用key的hash值、equals、双等号判断两个结点是否相同，如果相同则覆盖，如果遍历到最后一个结点任然不相同，则将该结点放到链表的最后一个位置。

4.每次添加都会对链表长度进行判断，如果链表长度大于8，则对数组进行判断，如果此时数组长度大于64，则会将链表转换为红黑树

下面是put方法相关的源码以及解析：

// put方法解密：public V put(K key, V value) {// 直接返回putVal方法return putVal(hash(key), key, value, false, true);}// hash方法解密static final int hash(Object key) {int h;// 注意这里hash的值不是由hashCode直接计算得来的return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}// putVal方法解密final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;// 如果此时HashMap刚刚创建，数组容量和加载因子都为初始化，添加第一个元素的时候才会对其进行初始化if ((tab = table) == null || (n = tab.length) == 0)// resize方法是扩容方法，下面会讲到n = (tab = resize()).length;// 如果此时这个位置没有元素，则直接进行添加，在这里可以看到index的计算方式if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 如果有元素，则进入下面的代码块else {HashMap.Node<K,V> e; K k;// 判断原结点与添加结点是否相同，如果相同，新增结点的value会覆盖掉原结点的valueif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 判断数据结构是否为红黑树，如果新增结点是TreeNode类型的话，即数组长度大于64，链表长度大于8，则向树中添加元素else if (p instanceof HashMap.TreeNode)e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 如果原结点与新增节点不同，则进行下面的代码块else {// 对链表进行遍历for (int binCount = 0; ; ++binCount) {// 如果此时结点为最后一个，即p.next==null，则将新增结点加入到原上一个结点的后面。if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 此时在这里对链表长度进行判断，如果大于8，则进入treeifBin方法内对数组长度进行判断if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 进去之后如果数组长度大于64，则将链表转化为红黑树// 下面会对这个方法进行解释treeifyBin(tab, hash);break;}// 如果在遍历过程中，有结点与新增结点相同，则对其value进行覆盖if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 覆盖valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 当代码执行到这一步之后，则说明新增结点以成功加入链表且无覆盖++modCount;// threshold的值在resize方法中进行了初始化，为现在数组容量×扩容因子// 将添加过以后的数组长度与该值进行比较，若前者大，则需要扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}// resize方法解密final HashMap.Node<K,V>[] resize() {// oldTab oldCap oldThr分别为原数组，原数组长度，原数组阈值HashMap.Node<K,V>[] oldTab = table;// 判断HashMap是否为第一次添加元素，如果是，则进行初始化int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;// newCap newThr为新数组长度，新数组阈值int newCap, newThr = 0;// 如果原数组长度大于零，即已被初始化，则if (oldCap > 0) {// 如果旧数组长度大于HashMap最大数组容量即64时if (oldCap >= MAXIMUM_CAPACITY) {// 让阈值等于Int类型的最大容量// 这是为下面做一个伏笔，后面会对oldTab进行判断//也是链表长度>8且数组长度>64之后，链表->红黑树threshold = Integer.MAX_VALUE;return oldTab;}// 扩容后的新容量，如果新容量小于HashMap的的最大容量，并且旧容量大于等于初始化容量// 这里可以看到HashMap的扩容方式，即newCap = oldCap << 1else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 这里也可以看到，扩容后的新阈值是旧阈值的2倍newThr = oldThr << 1; // double threshold}//else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = 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"})HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];table = newTab;// 如果oldTab不为null，也就是上面链表长度大于64的情况下，会返回一个oldTab// 接下来进行链表 -> 红黑树的操作if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {HashMap.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 HashMap.TreeNode)((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderHashMap.Node<K,V> loHead = null, loTail = null;HashMap.Node<K,V> hiHead = null, hiTail = null;HashMap.Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}// treeifyBin方法解密// 就是在putVal方法中，当链表长度大于8的情况下会进入这个方法内对链表长度进行判断final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {int n, index; HashMap.Node<K,V> e;// 如果链表长度也大于于8，则调用resize方法，也就是上面的oldTab，上面resize()方法中对是否需要转换为红黑树的一个标志// 即oldTab不为null，那么需要进行链表->红黑树if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)// oldTab为null，则扩容就行resize();// 链表->红黑树else if ((e = tab[index = (n - 1) & hash]) != null) {HashMap.TreeNode<K,V> hd = null, tl = null;do {HashMap.TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}

大家可以看看上面的代码块，里面有put以及相关方法的详细解释，如有错误，欢迎指正