哈？还在聊HashMap？老知识点了！liyuanbo1997的博客-哈?还在聊hashmap?老知识点了!

HashMap为什么经常被面试官问到，但是经常被面试官问趴下怎么办？

哈，原理我不知道？笑话！

不就是一个hash加一个map嘛，多简单啊？
答：利用key的hashCode重新hash计算出当前对象的元素在数组中的下标，存储到数组里面就行了，底层就是数组嘛！
然后面试官说了句：好的，我知道了，回去听消息吧！

这种答复并不是面试官想要看到的，想要听到程序员有自己的理解和分析优化！
今天就来给你们一探究竟，深挖HashMap！让你吊打面试官！

客官，来，1.7源码！

/** *继承AbstractMap，并重写Map接口 **/ public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 位运算，1左移4位=16 static final int MAXIMUM_CAPACITY = 1 << 30;//位运算，左移30位=1073741824 static final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子0.75 transient Entry<K,V>[] table;//entry数组 entry又是个单链表结构 transient int size;//hashmap长度 int threshold;//capacity * load factor 阈值比如16*0.75 = 12 void resize(int newCapacity)；//扩容方法 static int indexFor(int h, int length) { return h & (length-1);//计算index方法 } void createEntry(int hash, K key, V value, int bucketIndex) {     Entry<K,V> e = table[bucketIndex];     table[bucketIndex] = new Entry<>(hash, key, value, e);//头插法解决hash冲突     size++; }

通过源码可以知道，HashMap的默认初始化长度为1 << 4=16，最大容量为1<<30=1073741824.
可以看出1.7是采用数组加单链表的结构，Entry是一个继承Map.Entry的单链表结构。size就是hashmap的长度，threshold就是插入扩容的阈值。
从reSize方法可以看出，1.7是先进行扩容再插入数据的。

别着急，1.7是怎么进行扩容再插入的嘛！

容量初始值为16，当插入数据数量大于阈值（capacity * load factor=12）并发生hash冲突时就进行扩容。每次扩容都是2的n次幂，这样好处就是利于位运算，并且length-1的二进制最后一位为1，减少了hash碰撞。且插入时是通过int i = indexFor(e.hash, newCapacity);重新计算的，即hash & （length-1），并重新设置阈值（newCapacity * loadFactor）。

void resize(int newCapacity) {//扩容方法：resize(2 * table.length)，当容量不足时（容量 > 阈值），则扩容（扩到2倍）     Entry[] oldTable = table;//复制旧的哈希表 int oldCapacity = oldTable.length;//旧的容量 if (oldCapacity == MAXIMUM_CAPACITY) //容量如果等于最大值，则不再扩容         threshold = Integer.MAX_VALUE; return; }      Entry[] newTable = new Entry[newCapacity]; boolean oldAltHashing = useAltHashing;     useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing; transfer(newTable, rehash);//转移数据到新哈希表里     table = newTable;//完成扩容     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//重新设置阈值 } void transfer(Entry[] newTable, boolean rehash) {//将旧哈希表的数据移到新的哈希表里 //过程：按旧链表的正序遍历链表、在新链表的头部依次插入 int newCapacity = newTable.length; for (Entry<K,V> e : table) {//遍历哈希表 while(null != e) {             Entry<K,V> next = e.next; if (rehash) {                 e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity);//重新计算index值             e.next = newTable[i];             newTable[i] = e;//头部插入             e = next; } } }

还有1.8吗，太难了。挺住，坚持坚持就看完了！

客官，还有1.8呢

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; //Bins are converted to trees when adding an element to a bin with at least this many nodes. static final int TREEIFY_THRESHOLD = 8;//当桶的节点数量大于该阈值时转换为红黑树 static final int UNTREEIFY_THRESHOLD = 6;//当桶的节点数小于该阈值时会转换成链表，前提是当前是红黑树结构 static final int MIN_TREEIFY_CAPACITY = 64;//桶的节点数大于该容量时也会转换成红黑树 static class Node<K,V> implements Map.Entry<K,V> ;//换成节点了 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>;//树节点 transient Node<K,V>[] table;//数组加单链表，后期会转红黑树 transient Set<Map.Entry<K,V>> entrySet;//数据的另一种存储方式，主要用于迭代功能 transient int size;//hashmap元素数量 transient int modCount;//该map的修改次数

从源码可以看出，初始容量还是16，负载因子还是0.75，只是多了关于红黑树的知识点。1.8采用数组加单链表加红黑树的数据结构，扩容还是扩2的n次幂。

hash方法：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

通过判断key值是否为空，如果空就为0，不为空就异或运算。

存值方法put

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; //获取长度并进行扩容，使用的是懒加载，table一开始是没有加载的，等put后才开始加载 if ((tab = table) == null || (n = tab.length) == 0)         n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)//(length-1)&hash计算出索引值，判断当前哈希桶是否为空         tab[i] = newNode(hash, key, value, null);//空就赋值给当前桶 else {//该哈希桶不为空，会发生hash冲突，以下为发生hash冲突几种情况         Node<K,V> e; K k; //第一种情况，当前的hash值相同，且key值也相同，e = p表示首节点。 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);//节点数大于等于7，则转换红黑树结构（从0开始到7） break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;//插入节点与next节点重复，跳出循环                 p = e; } } if (e != null) { //在节点中存在重复的值，直接覆盖旧值             V oldValue = e.value; if (!onlyIfAbsent || oldValue == null)                 e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount;//修改次数加一 if (++size > threshold) resize();//容量增一，判断是否需要扩容 afterNodeInsertion(evict);//添加成功 return null; }

总的来说就是put的时候会进行判断当前桶是否为空，空就直接赋值。不为空且hash相同，则存在冲突，此时需要处理冲突的三种情况：
①当前桶不为空，且key值相同，则直接覆盖。
②当前桶不为空，则桶节点不为首节点，且为红黑树节点，则在红黑树中添加。（节点数>=TREEIFY_THRESHOLD）
③当前桶为不为空，不为首节点，不为红黑树节点，则为链表节点。(节点数<TREEIFY_THRESHOLD）添加时如果大于等于7（从0到7），则需要转为红黑树节点。

插入值过后就需要判断容量问题，此时就需要reSize()方法,从上述的源码中if (++size > threshold)就知道JDK1.8是先插入再进行判断扩容的。当链表深度大于8时，会自动扩容为红黑树结构，时间复杂度从O（n）转到O（logn）

final Node<K,V>[] resize() {//扩容方法     Node<K,V>[] oldTab = table;//之前旧的哈希表 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold;//old的表的阈值 int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) {//容量大于最大值             threshold = Integer.MAX_VALUE;//此时阈值为整数最大值 return oldTab;//最大限度 不能扩容了 }//左移一位，新的哈希表扩容两倍，且要小于最大容量；且旧容量要比默认初始容量大 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                  oldCap >= DEFAULT_INITIAL_CAPACITY)             newThr = oldThr << 1; // double threshold 阈值也要扩大两倍 } else if (oldThr > 0) // initial capacity was placed in threshold         newCap = oldThr;//初始化的阈值 else { //容量为0，阈值就为容量*负载因子         newCap = DEFAULT_INITIAL_CAPACITY;//默认初始容量16         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//阈值16*0.75=12 } if (newThr == 0) {//如果初始化容量小于16时，没有阈值。因为构造函数可以自己设初始容量 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;//扩容后将旧的哈希表赋值到新的哈希表中 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) {             Node<K,V> e; if ((e = oldTab[j]) != null) {//当前哈希桶节点为e                 oldTab[j] = null; if (e.next == null)//没有下个节点                     newTab[e.hash & (newCap - 1)] = e;//重新计算index，放入新的哈希表中 else if (e instanceof TreeNode)//有next节点，且为树节点，将此树转移到新的cap中 ((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;//下一个节点 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;//返回新的哈希表 } 

总的来讲，插入数据后扩容过程分为以下几个步骤：

①当前容量是否超过最大容量，超过则不扩容，直接返回。且阈值（threshold）为整数的最大值
②当前容量小于最大容量且大于初始容量。容量扩大两倍，阈值也扩大两倍

扩容后就将旧的表数据转移到新的表，利用hash&length-1计算index值，判断当前桶节点属于链表节点还是红黑树节点，再依次移入。

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; 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; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))             node = p;//获取当前的节点 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//链表节点，修改next值                 p.next = node.next; ++modCount;//修改次数加一 --size;//元素减一 afterNodeRemoval(node); return node; } } return null;//表示没有该节点，没找到 }

区别加总结

相同点：
计算index都是hash&length-1
不同点：
①JDK1.7时采用的是数组加单链表的数据结构，JDK1.8采用的是数组加单链表加红黑树的数据结构
②1.7是先扩容再插入，1.8是先插入再扩容
③解决冲突时，1.7是头插法的纵向延伸，但会容易逆序环形链表死循环问题；1.8是加入了红黑树，采用尾插法，能够避免出现逆序死循环的问题。

HashMap有哪些不足，怎么解决和优化

hashmap具有键-值（key-value）都允许为空、线程不安全、不保证有序、存储位置随时间变化的特性，即

为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

HashMap 中的 key若 Object类型， 则需实现哪些方法？

部分内容借鉴网址：https://www.jianshu.com/p/8324a34577a0?utm_source=oschina-app
确实写的好，佩服！

Hashmap确实还有很多可以深挖的知识点，这也是我第一次认真的写一篇文章，在我这么写了几千字的面子上就点个小心心呗，以后我会隔几天写一篇技术栈的文章并且同步到github上！有什么写的不好的地方和不足，欢迎大家指出！

隔壁写的实在是太好了，导致我有点力不从心，就这样吧！