今天会是有Offer的一天么：面试时不要再问我HashMap了

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

HashMap简介

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

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

HashMap内部属性： DEFAULT_INITIAL_CAPACITY=1<<4；数组的默认的初始容量为16。 MAXIMUM_CAPACITY =1<<30；数组的最大容量为2的30次方。 DEFAULT_LOAD_FACTOR =0.75f默认的装载因子为0.75。 TREEIFY_THRESHOLD =8当一个桶中的元素大于等于8的时候树化。 UNTREEIFY_THRESHOLD =6当一个桶中的元素小于等于6时反树化为链表。 MIN_TREEIFY_CAPACITY =64当桶的个数大于64的时候且一个桶中的元素大于等于8时，才会进行树化，否则桶会进行扩容。 Node[] table数组又称为桶。 int size元素的数量。 int modCount表示支持fail-fast。 int threshold; 表示当桶中的容量达到多少时会进行扩容。
threshold等于桶容量乘以装载因子。 float loadFactor装载因子，默认0.75。 Set<Map.Entry> entrySet作为entrySet()的缓存。 static class Nodeimplements Map.Entry { final int hash;//key所对应的的hash值，final修饰不可变 final K key;//key值，final修饰不可变 V value;//value值 Nodenext;//next } Node是一个单链表节点，hash用来存储key计算得来的hash值。 static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode 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 MAXIMUM_CAPACITY)//如果大于最大容量，则使用最大的容量 initialCapacity = MAXIMUM_CAPACITY; if (loadFactor >> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (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[] tab; Node 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 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)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; } 计算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[] resize() { //旧数组 Node[] 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) = DEFAULT_INITIAL_CAPACITY) newThr = 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[] newTab = (Node[])new Node[newCap]; //将新数组赋值给桶 table = newTab; //如果旧的桶不为null，说明之前存在元素，那么需要搬移元素。 if (oldTab != null) { //遍历旧的数组进行元素的搬移。 for (int j = 0; j < oldCap; ++j) { Node 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)e).split(this, newTab, j, oldCap); else { // preserve order //否则按照链表的方式进行遍历 //建立两个链表，一个是低位链表，另一个是高危链表 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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; } 如果key所在的桶没有元素，则新建一个节点放入桶中的第一个位置。 否则判断如果桶中第一个元素的key与插入元素的key相同，则更改key所对应的value。 否则如果桶中第一个元素是树节点，则调用树节点插入方法寻找元素或插入树节点。 否则按照链表的方式，查找key是否在链表中。如果找到key，则更新value值并返回旧值。否则新建一个节点插入到链表的末尾，插入之后需要判断是否需要进行树化。 如果没有找到key（如果旧桶中当前位置原本没有元素，那么在当前位置插入第一个元素的时候会走到这），size++，modcount++并判断数组是否需要扩容（size是否大于threshold）。 get(Object key) public V get(Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node getNode(int hash, Object key) { Node[] tab; Node 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)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; } 计算key所对应的hash值。定位到指定的桶中。 如果桶中第一个元素等于所查找的元素，直接返回。 如果头结点是树节点，按照红黑树的查找方式进行查找。 否则按照链表的查找方式进行查找。 remove（Object key） public V remove(Object key) { Node e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node[] tab; Node p; int n, index; //如果桶不为空，且桶的长度大于0，且桶的第一个元素不为空 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node 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)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)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; } 查找元素所在的节点。 如果找到的节点是树节点，则按照红黑树的方式进行删除。 如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置。 否则按链表删除节点处理。 size–，modcount++。 HashMap总结 HashMap采用数组 + 链表 + 红黑树的存储结构进行存储。 HashMap的默认初始容量为16，默认装载因子为0.75f，每次扩容为之前的两倍（要注意一点HashMap容量一定是2的n次方）。 当桶的数量大于64且某个桶中的元素数量大于8时，进行树化，小于等于6时进行反树化。 要注意HashMap是非线程安全的。
作者：今天会是有offfer的一天么

面试 offer hashmap