参考

美团技术团队-Java 8系列之重新认识HashMap

一些Map的比较

HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

HashMap概览

HashMap 底层的数据结构主要是：数组 + 链表 + 红黑树（JDK1.8增加了红黑树部分）。其中当链表的长度大于等于 8 时，链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表，整体的数据结构如下：图中左边竖着的是 HashMap 的数组结构，数组的元素可能是单个 Node，也可能是个链表，也可能是个红黑树，比如数组下标索引为 2 的位置就是一个链表，下标索引为 9 的位置对应的就是红黑树。HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

变量概念

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ：初始容量为 16，它一定是2static final int MAXIMUM_CAPACITY = 1 << 30 ：最大容量 为2一样也一定是2static final float DEFAULT_LOAD_FACTOR = 0.75f ：负载因子默认值为0.75 static final int TREEIFY_THRESHOLD = 8; 桶上的链表长度大于等于8时，链表转化成红黑树 static final int UNTREEIFY_THRESHOLD = 6; 桶上的红黑树大小小于等于6时，红黑树转化成链表 static final int MIN_TREEIFY_CAPACITY = 64; 当数组容量大于 64 时，链表才会转化成红黑树 transient int modCount ：结构版本号，强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。transient int size; HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化) int threshold; // 扩容的门槛，有两种情况 // 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。 // 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75 static class Node<K,V> implements Map.Entry<K,V> {} 链表的节点static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {} 红黑树的节点

类介绍（注释）

类注释大致内容如下：

允许 key为null、value 为null ，实现了Map接口的所有方法。它是hash table的Map接口实现版本，除了它是非线程安全的，其他与_Hashtable一致。_它不保证元素顺序get、put操作，时间复杂度是O(1)load factor（影响因子） 默认值是 0.75， 是均衡了时间和空间损耗的值，较高的值会减少空间开销（扩容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长），不扩容的条件：数组容量 > 需要的数组大小 /load factor；如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小（尽量减少rehash的操作次数），这样可以防止在其过程中不断的扩容，影响性能；在迭代过程中，如果 HashMap 的结构被修改（put、delete），会快速失败。HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过 Collections#synchronizedMap 来创建HashMap实现线程安全，Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁； # 常用方法源码 ### 哈希桶数组索引位置（hash） 用来计算key的hashcode，这里的Hash算法本质上就是三步：**取key的hashCode值、高位运算、取模运算**。 static final int hash(Object key) { int h; return (key == null) ? 0 : // key.hashCode()取hashCode值 // h ^ (h >>> 16) 高位参与运算 (h = key.hashCode()) ^ (h >>> 16); } //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的 static int indexFor(int h, int length) { return h & (length-1); //第三步 取模运算 }

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

添加（put，jdk1.8）

public V put(K key, V value) { // 对key进行hash操作后，调用putVal方法 return putVal(hash(key), key, value, false, true); } // 入参 hash：通过 hash 算法计算出来的值。 // 入参 hash：通过 hash 算法计算出来的值。 // 入参 onlyIfAbsent默认为 false // false 表示 key 存在时，会用新值覆盖原来的值， // 为true时，表示只有在key 不存在时，才会被放入map final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // n 表示数组的长度，i 为数组索引，p 为 i 下标位置的 Node 值 Node<K,V>[] tab; Node<K,V> p; int n, i; // 1.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③； if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 3.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 4.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是，则直接在树中插入键值对，否则转向⑤； else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 5.可以确定，该表为链表。遍历table[i]， // 在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； else { for (int binCount = 0; ; ++binCount) { // e = p.next 表示从头开始，遍历链表 // p.next == null 表明 p 是链表的尾节点 if ((e = p.next) == null) { // 在尾部添加 p.next = newNode(hash, key, value, null); // 判断链表长度是否大于8，大于8的话把链表转换为红黑树， if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 找到相同的，不为null的key，结束遍历 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; // 当 onlyIfAbsent 为 false 时，才会覆盖值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // 返回旧值 return oldValue; } } // 变更 HashMap 的结构版本号 ++modCount; // 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

从以上源码中，我们可以了解到，在当链表长度 >= 8 时，此时的链表就会转化成红黑树，转化的方法是：treeifyBin，此方法有一个判断，当链表长度>= 8，并且整个数组大小> 64 时，才会转成红黑树，当数组大小<64 时，只会触发扩容，不会转化成红黑树。那么，这个转为红黑树的阈值（MIN_TREEIFY_CAPACITY）为什么是8呢？在HashMap源码的143~198行，解释了这个“8”的由来。中文翻译过来大概的意思是：链表查询的时间复杂度是 O (n)，红黑树的查询复杂度是 O (log (n))。在链表数据不多的时候，使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树，但红黑树需要的占用空间是链表的 2 倍，考虑到转化时间和空间损耗，所以我们需要定义出转化的边界值。在考虑设计 8 这个值的时候，我们参考了泊松分布概率函数，由泊松分布中得出结论，链表各个长度的命中概率为：泊松分布-wiki

* 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million

意思是，链表的长度为 8 的概率是 0.00000006，不到千万分之一，所以说正常情况下，链表的长度不可能到达 8 ，而一旦到达 8 时，肯定是 hash 算法出了问题，所以在这种情况下，为了让 HashMap 仍然有较高的查询性能，所以让链表转化成红黑树，我们正常写代码，使用 HashMap 时，几乎不会碰到链表转化成红黑树的情况，毕竟概率只有千万分之一。其实想要hash的更加彻底还有很多神奇的算法，比如redis的murmurHash或者DJB HASH算法，但是因为性能差不多最后还是用了效率最高的^（异或 XOR）来解决问题

扩容（resize）

本方法分析参照美团技术团队-Java 8系列之重新认识HashMap，可以直接查看原帖，原帖还讲述了JDK1.8对扩容操作的优化、性能分析。扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

JDK1.8的resize方法，由于加入了红黑树的原因，较为复杂，这里先选取JDK1.7的resize方法。

void resize(int newCapacity) { //传入新的容量 Entry[] oldTable = table; //引用扩容前的Entry数组 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了 return; } Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组 transfer(newTable); //！！将数据转移到新的Entry数组里 table = newTable; //HashMap的table属性引用新的Entry数组 threshold = (int)(newCapacity * loadFactor);//更新扩容阈值 }

resize方法中，复制数据时，调用了transfer方法：

void transfer(Entry[] newTable) { Entry[] src = table; //src引用了旧的Entry数组 int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组 Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素 if (e != null) { src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象） do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置 // 先更新next 的指向；也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置； // 这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话） e.next = newTable[i]; newTable[i] = e; //将元素放在数组上 e = next; //访问下一个Entry链上的元素 } while (e != null); } } }

这里在重新计算每个元素在数组中的位置时，与JDK1.8不同。

HashMap的线程安全

HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。原因：在并发的场景中使用HashMap可能造成死循环（环形链表）。