总所周知，HashMap和ConcurrentHashMap是面试中经常会被问到的考点。UP最近在找实习的时候也会经常被问到相关的问题。那么OK今天我们就来做一个总结。由于篇幅有限，今天先来说一下HashMap。

HashMap简介

HashMap采用Key/Value存储结构，每个Key对应唯一的一个Value。

1. HashMap实现了Cloneable，可以被克隆。
2. HashMap实现了Serializable，可以被序列化。
3. HashMap继承了AbstractMap，实现了Map接口，具有Map的所有功能。
   
   

HashMap内部属性：

1. DEFAULT_INITIAL_CAPACITY=1<<4；数组的默认的初始容量为16。
2. MAXIMUM_CAPACITY =1<<30；数组的最大容量为2的30次方。
3. DEFAULT_LOAD_FACTOR =0.75f默认的装载因子为0.75。
4. TREEIFY_THRESHOLD =8当一个桶中的元素大于等于8的时候树化。
5. UNTREEIFY_THRESHOLD =6当一个桶中的元素小于等于6时反树化为链表。
6. MIN_TREEIFY_CAPACITY =64当桶的个数大于64的时候且一个桶中的元素大于等于8时，才会进行树化，否则桶会进行扩容。
7. Node<K,V>[] table数组又称为桶。
8. int size元素的数量。
9. int modCount表示支持fail-fast。
10. int threshold; 表示当桶中的容量达到多少时会进行扩容。
    threshold等于桶容量乘以装载因子。
11. float loadFactor装载因子，默认0.75。
12. Set<Map.Entry<K,V>> entrySet作为entrySet()的缓存。

  static class Node<K,V>implements Map.Entry<K,V>         {             final int hash;//key所对应的的hash值，final修饰不可变             final K key;//key值，final修饰不可变             V value;//value值             Node<K,V>next;//next         } Node是一个单链表节点，hash用来存储key计算得来的hash值。 

 static final class TreeNode<K,V> extends     LinkedHashMap.Entry<K,V> {         TreeNode<K,V> parent;  // red-black tree links         TreeNode<K,V> left;         TreeNode<K,V> right;         TreeNode<K,V> prev;    // needed to unlink next upon deletion         boolean red;         } 

 TreeNode是一个树型节点,在链表树化的时候使用。 

HashMap的构造方法

HashMap（）

public HashMap() {         this.loadFactor = DEFAULT_LOAD_FACTOR; //将装载因子设置为默认值     } 

HashMap(int initialCapacity)

public HashMap(int initialCapacity) {         this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用HashMap(int initialCapacity, float loadFactor)方法  

HashMap(int initialCapacity, float loadFactor)

public HashMap(int initialCapacity, float loadFactor) {         if (initialCapacity < 0)///如果传入容量小于0，抛出异常             throw new IllegalArgumentException("Illegal initial capacity: " +                                                initialCapacity);         if (initialCapacity > MAXIMUM_CAPACITY)//如果大于最大容量，则使用最大的容量             initialCapacity = MAXIMUM_CAPACITY;         if (loadFactor <= 0 || Float.isNaN(loadFactor))//检查装载因子是否合法             throw new IllegalArgumentException("Illegal load factor: " +                                                loadFactor);         this.loadFactor = loadFactor;         this.threshold = tableSizeFor(initialCapacity);//计算扩容门槛     }     static final int tableSizeFor(int cap) {     ///往上取最近的2的n次方         int n = cap - 1;         n |= n >>> 1;         n |= n >>> 2;         n |= n >>> 4;         n |= n >>> 8;         n |= n >>> 16;         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;     } 

HashMap的各种操作

put（K key ，V value）

 public V put(K key, V value) {         return putVal(hash(key), key, value, false, true);     }  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;             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;                     }                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         break;                     p = e;                 }             }             if (e != null) { // existing mapping for key                 V oldValue = e.value;                 if (!onlyIfAbsent || oldValue == null)                     e.value = value;                 afterNodeAccess(e);                 return oldValue;             }         }         ++modCount;         if (++size > threshold)             resize();         afterNodeInsertion(evict);         return null;     } 

1. 计算key的hash值；

 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 

如果key为null，则hash值为0，否则调用key的hashCode()方法让高16位与整个hash异或。为的是让计算出的hash值更加分散一些。
2. 如果桶（数组）数量为0，则调用resize()方法初始化桶；
resize（）方法比较复杂，我们来解释一下。

   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) {          //如果旧的容量大于最大的容量是，不在进行扩容，直接返回             if (oldCap >= MAXIMUM_CAPACITY) {                 threshold = Integer.MAX_VALUE;                 return oldTab;             }             //如果旧的容量的2倍小于最大的容量，oldCap<<1为扩大两倍。             //且旧的容量大于默认容量也就是16。新容量扩大为两倍，扩容门槛扩大两倍。             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                      oldCap >= DEFAULT_INITIAL_CAPACITY)                 newThr = oldThr << 1; // double threshold         }         //这里当你调用HashMap(int initialCapacity)进行创建时，第一次插入数据会走到这里。         //也就是oldcap=0，oldThr>0;那么将新容量设置为旧的扩容门槛。         else if (oldThr > 0) // initial capacity was placed in threshold             newCap = oldThr;         else {                        //调用new HashMap（）创建时，第一次插入数据走到这。         //新容量为默认值16，新的扩容门槛为16*0.75。             newCap = DEFAULT_INITIAL_CAPACITY;             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);         }         //如果新的扩容门槛等于0，会进行计算。         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;       //如果旧的桶不为null，说明之前存在元素，那么需要搬移元素。         if (oldTab != null) {         //遍历旧的数组进行元素的搬移。             for (int j = 0; j < oldCap; ++j) {                 Node<K,V> e;                 //如果旧桶中第一个元素不为空                 if ((e = oldTab[j]) != null) {                   //将旧桶中第一个元素设置为null，方便进行GC回收                     oldTab[j] = null;                     //如果next==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);                     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;                             //如果当前key的hash值与桶的旧容量与操作等于0                             //将当前节点放入地位链表中                             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;     } 

3. 如果key所在的桶没有元素，则新建一个节点放入桶中的第一个位置。
4. 否则判断如果桶中第一个元素的key与插入元素的key相同，则更改key所对应的value。
5. 否则如果桶中第一个元素是树节点，则调用树节点插入方法寻找元素或插入树节点。
6. 否则按照链表的方式，查找key是否在链表中。如果找到key，则更新value值并返回旧值。否则新建一个节点插入到链表的末尾，插入之后需要判断是否需要进行树化。
7. 如果没有找到key（如果旧桶中当前位置原本没有元素，那么在当前位置插入第一个元素的时候会走到这），size++，modcount++并判断数组是否需要扩容（size是否大于threshold）。

get(Object key)

  public V get(Object key) {         Node<K,V> e;         return (e = getNode(hash(key), key)) == null ? null : e.value;     }      final Node<K,V> getNode(int hash, Object key) {         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;         //如果table不为空，且table的长度大于0且桶中第一个元素不为空         if ((tab = table) != null && (n = tab.length) > 0 &&             (first = tab[(n - 1) & hash]) != null) {             //如果桶中第一个节点是我们要找的节点，直接返回             if (first.hash == hash && // always check first node                 ((k = first.key) == key || (key != null && key.equals(k))))                 return first;                 //如果头结点的下一个节点不为空             if ((e = first.next) != null) {             //如果头结点是树节点，按照红黑树的查找方式进行查找                 if (first instanceof TreeNode)                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);                 do {                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         return e;                 } while ((e = e.next) != null);//循环遍历链表进行查询。             }         }         //表示查找失败，查找节点不存在返回null         return null;     } 

1. 计算key所对应的hash值。定位到指定的桶中。
2. 如果桶中第一个元素等于所查找的元素，直接返回。
3. 如果头结点是树节点，按照红黑树的查找方式进行查找。
4. 否则按照链表的查找方式进行查找。

remove（Object key）

public V remove(Object key) {         Node<K,V> e;         return (e = removeNode(hash(key), key, null, false, true)) == null ?             null : e.value;     }  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;         //如果桶不为空，且桶的长度大于0，且桶的第一个元素不为空         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;             //如果桶中第一个元素就是所要删除的元素，将p赋值给node             if (p.hash == hash &&                 ((k = p.key) == key || (key != null && key.equals(k))))                 node = p;                 //如果p.next!=null,继续进行查找             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);                     //如果头结点是所需要删除的元素，将头结点的下一个节点移动到一一个位置                 else if (node == p)                     tab[index] = node.next;                     //按照链表的方式进行删除                 else                     p.next = node.next;                 ++modCount;                 --size;                 afterNodeRemoval(node);                 return node;             }         }         return null;     } 

1. 查找元素所在的节点。
2. 如果找到的节点是树节点，则按照红黑树的方式进行删除。
3. 如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置。
4. 否则按链表删除节点处理。
5. size–，modcount++。

HashMap总结

1. HashMap采用数组 + 链表 + 红黑树的存储结构进行存储。
2. HashMap的默认初始容量为16，默认装载因子为0.75f，每次扩容为之前的两倍（要注意一点HashMap容量一定是2的n次方）。
3. 当桶的数量大于64且某个桶中的元素数量大于8时，进行树化，小于等于6时进行反树化。
4. 要注意HashMap是非线程安全的。