转载请注明出处 http://www.cnblogs.com/qm-article/p/8973978.html
一、HashMap介绍
这个类，我相信诸位绝对使用过，并且在面试当中，遇到的也绝对不少，如，你能说下hashmap的原理吗？它里面的负载因子是什么？它有什么线程安全问题吗，它的长度为什么一定要选择2的指数倍？相对于jdk1.7,版本，1.8做了什么改变等等。对于这些问题，如果你仅仅停留在会用hashmap的基础上，这绝对会一个难题。首先呢，对于hashmap的结构，它是一个数组+链表,在1.8中，也有可能是数组+红黑树结构，又或者是两者混合体，至于为什么是这样的结构，在后面会分析出来，本文主要是针对jdk1.8版本进行分析的。
下面主要会围绕这几个方面展开
1、 hashmap的构造函数
2、hashmap的node内部类
3、 hashmap的put方法实现
4、 hashmap的扩容实现
5、 hashmap的get方法实现
6、 对于1.7做了哪些改变。
二、HashMap的函数
在看构造函数之前，先来了解下，这个类的一些变量，如下
1 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16，HashMap的默认大小 2 3 static final int MAXIMUM_CAPACITY = 1 << 30; HashMap的最大容量，即数组长度 4 5 static final float DEFAULT_LOAD_FACTOR = 0.75f; HashMap的负载因子， 6 7 static final int TREEIFY_THRESHOLD = 8; 链表转为红黑树的阈值 8 9 transient Node<K,V>[] table; 内部存储元素的数组(HashMap的核心) 10 int threshold; 若使用默认构造函数，则该值为12，即16*0.75f,若不是默认构造函数，则该值由函数tableSizeFor计算而来，在第一次插入元素后，又会被重新计算，意义在于若map里元素个数超过这个值，则扩容 11 transient int size; HashMap的元素个数，即HashMap的大小
HashMap一共有三个构造函数
1 //指定HashMap的初始化大小和指定负载因子 2 public HashMap(int initialCapacity, float loadFactor) { 3 if (initialCapacity < 0) 4 throw new IllegalArgumentException("Illegal initial capacity: " + 5 initialCapacity); 6 if (initialCapacity > MAXIMUM_CAPACITY) 7 initialCapacity = MAXIMUM_CAPACITY; 8 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 9 throw new IllegalArgumentException("Illegal load factor: " + 10 loadFactor); 11 this.loadFactor = loadFactor; 12 this.threshold = tableSizeFor(initialCapacity); 13 } 14 15 //只传入初始化HashMap的大小，默认负载因子0.75f 16 public HashMap(int initialCapacity) { 17 this(initialCapacity, DEFAULT_LOAD_FACTOR); 18 } 19 20 //使用的最多的一个构造函数，默认大小为16，负载因子为0,75f 21 public HashMap() { 22 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 23 }
三、HashMap的Node内部类
1 static class Node<K,V> implements Map.Entry<K,V> { 2 final int hash; 3 final K key; 4 V value; 5 Node<K,V> next; 6 7 Node(int hash, K key, V value, Node<K,V> next) { 8 this.hash = hash; 9 this.key = key; 10 this.value = value; 11 this.next = next; 12 } 13 14 public final K getKey() { return key; } 15 public final V getValue() { return value; } 16 public final String toString() { return key + "=" + value; } 17 18 public final int hashCode() { 19 return Objects.hashCode(key) ^ Objects.hashCode(value); 20 } 21 22 public final V setValue(V newValue) { 23 V oldValue = value; 24 value = newValue; 25 return oldValue; 26 } 27 28 public final boolean equals(Object o) { 29 if (o == this) 30 return true; 31 if (o instanceof Map.Entry) { 32 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 33 if (Objects.equals(key, e.getKey()) && 34 Objects.equals(value, e.getValue())) 35 return true; 36 } 37 return false; 38 } 39 }
类的结构比较简单，实现了Map.Entry接口，里面有hash、key、value、next四个变量。
HashMap的table数组也就是一个Node数组，每个Node后面又跟着一个个Node节点，由每个Node的next变量去连接。
结构如下图(来源于百度)
四、HashMap的put方法实现
1 public V put(K key, V value) { 2 return putVal(hash(key), key, value, false, true); 3 } 4 //参数解释：hash：为Key的hash值，onlyIfAbsent，该值若为true时，则若有重复key插入，则不改变旧值，evict目前只知道该值留个一个子类去实现的空方法参数 5 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 6 boolean evict) { 7 Node<K,V>[] tab; Node<K,V> p; int n, i; 8 if ((tab = table) == null || (n = tab.length) == 0)//若第一次插入元素，则此时table数组为Null或者长度为0，此时则进行使用resize进行初始化 9 n = (tab = resize()).length; 10 if ((p = tab[i = (n - 1) & hash]) == null)//使用key与数组长度-1进行定位数组坐标，若该坐标下的元素为null，则直接new一个元素进行插入 11 tab[i] = newNode(hash, key, value, null); 12 else { //此时代表数组下标已经有其他元素插入了，就意味着要插入的话，只能插入坐标下元素的后面 13 Node<K,V> e; K k; 14 if (p.hash == hash && //此步是为了判断插入的key是否和定位下的坐标元素相等，若相等，则表明插入的是同一个key 15 ((k = p.key) == key || (key != null && key.equals(k)))) 16 e = p; //e用来临时存储 17 else if (p instanceof TreeNode)//这个表明该位置的元素链表已经被转为了红黑树结构，接下来要用到红黑树结构来插入元素。 18 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 19 else {//若以上两个条件都不满足，则进行此步。 20 for (int binCount = 0; ; ++binCount) {//这个变量的作用是用来计算链表的长度，顺便遍历链表 21 if ((e = p.next) == null) {//若是链表最后一个，则在末尾处插入Node节点 22 p.next = newNode(hash, key, value, null); 23 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st，若变量长度超过阈值，这将该链表转为红黑树结构 24 treeifyBin(tab, hash); 25 break; 26 } 27 if (e.hash == hash &&//同样用来判断插入的key是否相等 28 ((k = e.key) == key || (key != null && key.equals(k)))) 29 break; 30 p = e; 31 } 32 } 33 if (e != null) { // existing mapping for key 34 V oldValue = e.value; 35 if (!onlyIfAbsent || oldValue == null)//若onlyIfAbsent为true，则对旧值不进行覆盖 36 e.value = value; 37 afterNodeAccess(e);//提供给子类去实现的 38 return oldValue;//返回旧值 39 } 40 } 41 ++modCount;//若进行到此步操作，则表明，插入的元素key没有和之前存在的重复。 42 if (++size > threshold)//判断size和threshold的大小，若前者大，则进行扩容。 43 resize(); 44 afterNodeInsertion(evict); 45 return null; 46 }
对于以上插入操作，也可细分为这几步。
1、判断table数组有没有初始化，若没有则初始化，有则跳过。
2、使用key与数组的长度-1进行&运算，得出数组下标，若该下标没有元素则插入，有则跳过。
3、判断插入的key是否和该下标的元素key是否相等，若相等，则用e临时存储该下标位置元素，没有则跳过
4、判断该下标后的元素是否是红黑树结构，若是，择用红黑树结构插入元素，否则跳过
5、进行遍历链表，在遍历过程中，有两步操作，1，遍历过程中是否有相同key，2.遍历过程中，是否到了转为红黑树结构的阈值点。若前两步都不满足，则在链表末尾处插入元素。
6、若插入元素和HahsMap中存在相同key，则此步操作不进行，若不存在，否则对modCount进行+1，还有看size和threshold的大小，满足条件则进行扩容。
以上六个步骤就是插入元素的介绍。
或许细心的人会发现，在判断相同key的时候。都用到了equals方法，所以要值得注意的是，在用某个类充当key的时候，最好一定要重写equals方法，否则可能得不到自己想要的结果，而要重写equals方法，必然要重写hashCode方法，所以综上，充当key的类，最好要重写hashCode和equals方法。来保证自己想要的结果。
五、HashMap的扩容实现
由HashMap的插入操作，很容易得知，在进行初始化操作和元素个数达到一定阈值，都会触发HashMap的扩容操作。下面就来看下它的扩容是怎么实现的。
1 final Node<K,V>[] resize() { 2 Node<K,V>[] oldTab = table;//一般为了不直接操作原数据都会赋值给一个临时变量 3 int oldCap = (oldTab == null) ? 0 : oldTab.length;//计算旧table数组的长度 4 int oldThr = threshold; //当table数组还没初始化且使用了默认构造函数，该值默认为0， 5 int newCap, newThr = 0; 6 if (oldCap > 0) {//表明table数组已经初始化了 7 if (oldCap >= MAXIMUM_CAPACITY) {//若旧table数组长度大于MAX_CAPACITY,则不扩容，并设置threshold，返回旧数组 8 threshold = Integer.MAX_VALUE; 9 return oldTab; 10 } 11 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&//新数组长度为旧数组长度*2,至于为什么*2,不用急接下来会解释。 12 oldCap >= DEFAULT_INITIAL_CAPACITY) 13 newThr = oldThr << 1; // double threshold，同样新的threshold为旧的两倍，即double 14 } 15 else if (oldThr > 0) // initial capacity was placed in threshold，此种情况为数组还未初始化，但threshold已经被初始化了，表明初始化hashmap实例不是用了默认构造函数 16 newCap = oldThr;//若table数组初始化执行了该步操作，则必定会重新计算threshold，计算方式看23行。 17 else { // zero initial threshold signifies using defaults，表明使用了默认构造函数，且是table数组的初始化。 18 newCap = DEFAULT_INITIAL_CAPACITY;//使用默认长度16， 19 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//初始化操作，threshold值为 0.75f*length。 20 } 21 if (newThr == 0) {//重新计算threshold值 22 float ft = (float)newCap * loadFactor; 23 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 24 (int)ft : Integer.MAX_VALUE); 25 } 26 threshold = newThr; 27 @SuppressWarnings({"rawtypes","unchecked"}) 28 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//建立一个新的长度的Node数组 29 table = newTab; 30 if (oldTab != null) {//此种情况表明是空间不足，引起的扩容，而不是初始化引起的扩容 31 for (int j = 0; j < oldCap; ++j) {//将旧的数组元素赋给新数组，并且对key重新进行hash 32 Node<K,V> e; 33 if ((e = oldTab[j]) != null) { 34 oldTab[j] = null;//为了更好的配合垃圾回收 35 if (e.next == null)//该下标元素为null，直接插入 36 newTab[e.hash & (newCap - 1)] = e; 37 else if (e instanceof TreeNode)//红黑树结构另做处理 38 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 39 else { // preserve order 40 Node<K,V> loHead = null, loTail = null; 41 Node<K,V> hiHead = null, hiTail = null; 42 Node<K,V> next; 43 do {//值得注意的是，赋值分了两步操作，该步循环是为了先连接好链表，即不用从数组下标开始一个一个的进行连接，先把链表串起来 44 next = e.next; 45 if ((e.hash & oldCap) == 0) {//第一步，表明key的hash值与旧数组长度化为二进制最高为不相同(如。10011和100000)，这两个值&运算值为0 46 if (loTail == null) 47 loHead = e; 48 else 49 loTail.next = e; 50 loTail = e; 51 } 52 else {//第二步，与第一步相反，如果觉得难理解的话，可以将第一步理解为hash值小于旧数组长度，第二步hash值大于旧数组长度(说明：这种理解只是帮助理解，不是一定正确) 53 if (hiTail == null) 54 hiHead = e; 55 else 56 hiTail.next = e; 57 hiTail = e; 58 } 59 } while ((e = next) != null); 60 if (loTail != null) {//和数组串起来 61 loTail.next = null; 62 newTab[j] = loHead; 63 } 64 if (hiTail != null) {//和数组串起来 65 hiTail.next = null; 66 newTab[j + oldCap] = hiHead; 67 } 68 } 69 } 70 } 71 } 72 return newTab;//返回新的数组 73 }
以上就是整个扩容操作，具体可分为这几步
1、先判断是初始化操作，还是真的空间不够去扩容。
2、扩容的最大长度为MAXIMUM_CAPACITY。
3、重新计算threshold和数组长度的值。
4、若是真的要扩容，则进行数据迁移。
上面也有说道为什么数组长度一定是2的指数倍，下面来分析一下。
我们都知道2的指数倍化成二进制，则最高位为1，其余位为0，若其减一，则退一位，且其余位都为1，若有任何一个数组和它进行&运算，则结果一定小于2的指数倍，
此为其一，是为了key的hash值能落在数组范围内。
这种结果和求余运算的结果一样，可以使插入进来的元素相对于其它的计算可以更均匀的分布在数组中，不造成某个坐标元素众多，某个坐标没有的结果。
六、HashMap的get实现
1 public V get(Object key) { 2 Node<K,V> e; 3 return (e = getNode(hash(key), key)) == null ? null : e.value; 4 } 5 //最终调用的是这个方法 6 final Node<K,V> getNode(int hash, Object key) { 7 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 8 if ((tab = table) != null && (n = tab.length) > 0 && 9 (first = tab[(n - 1) & hash]) != null) {//首先是先时判断数组有没有被初始化和数组长度是否大于0，再求Key的hash值对应的数组下标，若此下标为Null，则直接返回null 10 if (first.hash == hash && // always check first node 如同这个注释一样，总是先检查这个数组下标对应的元素是否和锁=所要获取的key相等，若相等，则直接返回 11 ((k = first.key) == key || (key != null && key.equals(k)))) 12 return first; 13 if ((e = first.next) != null) {//若对应的坐标里的元素后面又元素，则进入， 14 if (first instanceof TreeNode) //依然判断是否是红黑树结构，若是，则另做处理 15 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 16 do { //这个do while循环是开始遍历链表，直到找到或者遍历完链表 17 if (e.hash == hash && 18 ((k = e.key) == key || (key != null && key.equals(k)))) 19 return e; 20 } while ((e = e.next) != null); 21 } 22 } 23 return null; 24 }
以上就是根据Key从HashMap中获取value的过程，大致可以分为下面几步
1、判断table数组有没有初始化，判断key的hash值对应的下标有没有元素，若没有，则直接返回null。
2、若对应的下标位置有元素，看其是否是我们要找的，使用key的hash值和对应的equals方法去判断。
3、看对应下标的下一个Node节点是否为红黑树结构，若是，则做相应的处理。
4、做链表遍历，找到就返回，没找到就返回null。
七、对比jdk1.7版本做了哪些改变
熟悉过jdk1.7版本的都清楚，该版本在进行扩容的时候，如果是高并发环境，会出现环链，如图
就会出现这样的，A指向B，B也执行A，一旦进行查找的时候，可能查到A不是，又查B，也不是，接着又查A，如此循环，就陷入了死循环，
关于为什么会陷入死循环，大家可自行搜索其他博客，这里就不过多叙述。
当然，在jdk1.8版本，这个死循环问题被解决了。
如果非要在高并发环境使用HashMap，可以采用以下几种办法
1、HashTable，不过不建议，效率有点低
2、Collections工具类，这个也一样，每个方法都加入了synchronized同步关键词，效率有点低
3、ConcurrentHashMap，建议使用这个。
当然除了这些，jdk1.8还做了红黑树结构，这样当链表过长时，查找的效率可以得到保证。
———————————————————————————————————-华丽的分界线—————————————————————————————————————————————————————-
以上就是我对HashMap的一些理解。若有不足与错误之处，还望指正，不胜感激
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/12341.html