文章目录

需要先知道的内容Hash、哈希表、哈希函数哈希函数的构造方法解决哈希冲突的方法 HashMap源码分析常量设置节点设置构造函数resize()put(K key, V value)get(K key)remove() 补充内容（1） 众所周知HashMap是线程不安全的，为什么HashMap是线程不安全的？（2）HashMap在JDK1.7和JDK1.8的区别？（3）HashMap转化为线程安全的几种方式？

需要先知道的内容

Hash、哈希表、哈希函数

Hash ：散列，通过关于键值(key)的函数，将数据映射到内存存储中一个位置来访问。这个过程叫做Hash，这个映射函数称做哈希函数，存放记录的数组称做散列表(Hash Table),又叫哈希表。JAVA函数hashCode()即请求对象的哈希值。

哈希函数的构造方法

（1）直接取址法

取关键字的某个线性函数作为散列地址，如H(key) = a * key + b

（2）除留余数法

最为常用的一种方法，假设表长为m，p为不大于m的最大素数，则哈希函数为H（key）= key % p;

（3）数字分析法

关键字的位数比较大，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。

（4）平方取中法

取Key平方值的中间几位作为Hash地址。适合于不知道关键字的分布，而位数又不是很大的情况。

（5）分段叠加法

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。 当Key的位数较多的时候数字分布均匀适合采用这种方案.

（6）基数转化法

将Key值看作另一种进制的数，然后在转化为原来进制的数，再选择其中几位作为散列地址。

解决哈希冲突的方法

（1）开放定址法

当冲突发生时，探测其他位置是否有空地址 (按一定的增量逐个的寻找空的地址)，将数据存入。根据探测时使用的增量的取法，分为：线性探测、平方探测、伪随机探测等。Hash_new(Key) = (Hash(Key) + d i )【i = 1，2，3，……】

线性探测：d i = a * i + b;【a,b均为常数】平方探测：d i = a * （ i ^2)【a为常数】伪随机数探测 ： d i = random(Key);

（2）链地址法

将散列到同一位置的所有元素储存在单链表中

（3）再哈希法

有多个不同的Hash函数，当发生冲突时，使用第二个、第三个……等哈希函数计算地址，直到无冲突，这种方法不易发生聚集，但是增加了计算时间。

（4）公共溢出区域法

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

---

HashMap源码分析

常量设置

// 初始容量必须是2的幂（16） static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 通过构造函数指定数组大小原则上必须是小于2^30的 static final int MAXIMUM_CAPACITY = 1 << 30; //构造函数未指定负载因子时，默认为0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //链表转化为树的阙值 static final int TREEIFY_THRESHOLD = 8; //树还原为链表的阙值为6 static final int UNTREEIFY_THRESHOLD = 6; // 哈希表最小树形化容量 static final int MIN_TREEIFY_CAPACITY = 64; //链表数组 transient Node<K,V>[] table; // 缓存的键值对集合 transient Set<Map.Entry<K,V>> entrySet; //键值对的数量 transient int size; //这个HashMap被修改的次数 transient int modCount; // 阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子） // 另外，如果还没有分配表数组，则字段保留初始数组容量，或零表示默认初始容量 int threshold; //哈希表的装载因子 final float loadFactor;

常量的设置意义

节点设置

static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); }

---

构造函数

构造函数（一）

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 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); }

tableSizeFor(initialCapacity)

根据指定容量设置阙值，最终结果为不小于cap的最小的2的指数幂 （为了使用key的hash值计算数组下标时，使用取余运算可以用“&”代替，效率更高）

static final int tableSizeFor(int cap) { int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

构造函数（二）【拷贝构造函数】

//构造一个映射关系与指定 Map 相同的新 HashMap。 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

putMapEntries(m, false) 此方法会被HashMap的拷贝构造函数public HashMap(Map<? extends K, ? extends V> m)或者Map接口的putAll函数（被HashMap给实现了）调用到。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) {//传入的map大小不为0 if (table == null) { //说明是拷贝构造函数调用或者构造之后的HashMap中没有放入任何元素 /*算出来恰好不超过阙值的容量，由于会计算出小数， 在后面的代码中需要取整，为了保证容量足够， 需要向上取整，所以这里要加1*/ float ft = ((float)s / loadFactor) + 1.0F; //判断计算出来的容量与规定最大容量的大小，此处要取整 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); /*如果大于当前暂存容量大小（容量可能会暂时放在阙值上） 则用t重新计算出容量值，暂时放在阙值上。 */ if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) /*说明此时HashMap已经进行了初始化，这里进行的是预先扩大容量， 不需要判断s+this.size>threshold，因为 如果s>threshold，是肯定需要立即扩容的，如果s<threshold,可以在 遍历插入时进行扩容。*/ resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { //对Map进行遍历赋值 K key = e.getKey(); V value = e.getValue(); //存放数据时可能会扩容。 putVal(hash(key), key, value, false, evict); } } } hash（Object key） static final int hash(Object key) { int h; //当Key为null时，索引为0 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

---

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) {//原来的HashMap中存放了数据 //已经到达了容量的最大值无法扩容，直接返回原来的大小 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //新容量为原来的2倍小于最大容量值，并且原来的容量不小于默认值初始值 //则新的容量扩大为原来的2倍，新的阙值扩大为原来的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } //旧数组为空，新数组的容量设置为旧数组的阙值 else if (oldThr > 0) newCap = oldThr; //创建HashMap为空的构造函数创建时，则全部设置为默认值 else { newCap = 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; /*对于上面的情况进行总结： （1）使用空构造函数进行创建时，会使用系统的默认值 （2）使用带有自定义初始容量大小的构造参数时，首先在构造函数中将 不小于初始容量大小的2的幂设置为阙值，然后在resize()中设置为初始容量大小 并将阙值设置为newCap * loadFactor（新容量大小 * 负载因子） （3）当数组中含有数据时，未达到最大值，则将容量值和阙值扩大为原来的2倍， 否则为最大值。 */ @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) { oldTab[j] = null; //如果桶中只有一个元素，则根据新容量计算新的索引值。 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果链表已经转化为红黑树，则计算新的hash值放在新的地方 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //还是链表形式 else { Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //按照特定bit位转移链表的位置 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); //如果特定bit位为0，则存放在原来的数组索引位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //如果为1，则新的索引值为原来索引值+oldCap if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

put(K key, V value)

大概思路： （1）如果没有进行初始化，首先进行resize（） （2）判断数组中相对应的索引处是否有元素，没有的话，将创建的节点存放在数组中，有的话继续向下执行 （3）判断与首个节点是否Key值相同，相同的话将节点值赋值给e （4）将节点插入到链表的最末尾，如果长度到了树形化的阙值，则转化为红黑树，如果链表节点中存在Key值相同的节点，则赋值给e （5）如果e不为null，证明哈希表中存在key相同的键值对，则将新的value放进去，并返回旧的value值 （6）如果size的值大于了阙值，则进行扩容。 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) //当哈希表没有进行初始化时，第一次进行扩容，得到默认值16 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; //存放的节点Key值和数组中的节点Key值相同则给e赋值 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; } //如果有重复的Key，则用e记录节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //将节点值的value替换为新的，并返回旧的value值 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //修改次数加1 ++modCount; //键值对的个数超过阙值，扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

键值对超过阙值的疑问解答

---

get(K key)

大概思路： （1）匹配查找桶中的第一个节点，命中直接返回，未命中继续向下执行 （2）如果为树，在树中查找，时间复杂度为o(logn) 如果为链表，则在链表中查找，时间复杂度为o（n） 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; //保证桶中有元素的前提 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); } } return null; }

---

remove()

与上面get()流程相似，多了删除节点的操作，这里不赘述了。 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); } } //传入参数时设置matchValue = false //node即为要删除节点， //如果要删除的节点位于数组中的第一个节点，p为数组中存放的第一个节点 //如果是链表中的节点，则p为删除节点的前一个节点 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; //修改次数加1 ++modCount; //键值对总数减1 --size; afterNodeRemoval(node); return node; } } return null; }

---

补充内容

（1） 众所周知HashMap是线程不安全的，为什么HashMap是线程不安全的？

HashMap在并发时可能出现的问题主要是两方面,首先如果多个线程同时使用put方法添加元素，而且假设正好存在两个put的key发生了碰撞(hash值一样)，那么根据HashMap的实现，这两个key会添加到数组的同一个位置，这样最终就会发生其中一个线程的put的数据被覆盖。第二就是如果多个线程同时检测到元素个数超过数组大小*loadFactor，这样就会发生多个线程同时对Node数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给table，也就是说其他线程的都会丢失，并且各自线程put的数据也丢失。

（2）HashMap在JDK1.7和JDK1.8的区别？

（1）1.7是数组+链表，1.8则是数组+链表+红黑树结构; （2）. 插入键值对的put方法的区别，1.8中会将节点插入到链表尾部，而1.7中是采用头插； （3） jdk1.7中的hash函数对哈希值的计算直接使用key的hashCode值，而1.8中则是采用key的hashCode异或上key的hashCode进行无符号右移16位的结果，避免了只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀； （4） 扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序；而且1.8是在元素插入后检测是否需要扩容，1.7则是在元素插入前； （5）jdk1.8是扩容时通过hash&cap==0将链表分散，无需改变hash值，而1.7是通过更新hashSeed来修改hash值达到分散的目的； （6）扩容策略：1.7中是只要不小于阈值就直接扩容2倍；而1.8的扩容策略会更优化，当数组容量未达到64时，以2倍进行扩容，超过64之后若桶中元素个数不小于7就将链表转换为红黑树，但如果红黑树中的元素个数小于6就会还原为链表，当红黑树中元素不小于32的时候才会再次扩容。

（3）HashMap转化为线程安全的几种方式？

（1）使用HashTable

底层在put方法和get方法之前加上了synchronized

（2）使用ConcurrentHashMap

（3）使用Synchronized Map

而在SynchronizedMap类中使用了synchronized同步关键字来保证对Map的操作是线程安全的。