Map接口虽然也属于集合框架的一部分，但是其独特的数据结构使其与Collection分离开来，独成一派。 其实在其他语言中，这种结构被称为Dictionary，即字典。比如Python。 然后你会发现，Java里面真的有Dictionary这个类，而且的确和Map想要指定的意思一模一样。它在JDK1.0的时候就有了，在1.2的时候Map出现废除了Dictionary这个类，因为它是抽象类不是接口。 不管Dictionary还是Map，其实都要表达一个意思，就是：这个接口代表一种映射关系，从key到value，用户可以根据key很方便地取到value 其实我们的List也是有映射关系的，就是对象的index和对象之间的映射关系，知道index，就能从List中拿到对象。 但是这里有局限性，那就是我们这里的key必须要是对象存放在内部数据结构中的相对位置index，而不是别的什么东西。index也只能用int来表示，扩展性太差，适用场景有限。 因此，Map诞生出来就是允许用户去通过其他的东西当做key，照样能够方便地存取value。 ### 内部结构 废话不多说，先给出方法图： {% asset_img map_inner.png %} 解析如下： - 既然同是集合框架的一员，那还是有一些共通的地方的，比如clear，empty，remove，size，get，这几个方法，几乎是你有我有全都有的通用方法。 - compute系列是1.8新增加的，使用到了函数式的思想，将value通过function重新计算新值并更新到Map中 - entrySet，keySet，values，三个方法都是返回Map的视图，只不过从不同的维度，第一个是返回键值对，第二个是返回所有的键，第三个是返回所有的值。注意，既然是视图就是说修改了它们，原始的Map也会收到影响 - 和List的add方法不同，Map插入元素用的是put方法，变更元素是用replace方法，不过很少用到这个方法，原因是JDK1.8才有这个方法，而且put方法也有同样的功效，它直接替换掉key对应的value，不管原先的值是什么，存在不存在。 - Map接口定义比较简单，但是文档里提到一些限制条件： 1. Map用作key值的对象最好不要是可变对象，如果是可变对象而且它的变化会影响equals方法的结果，那Map的行为就是不确定的 2. Map绝对不能把它自己当做Key，禁止这样做。当然了，接口定义和编译器都不能阻止你这么做，你完全可以这么写，于是我不信邪，就写了下面这个： java public static void main(String[] args) { Map<Map, Integer> map = new HashMap<>(); map.put(map, 1); Integer result = map.get(map); System.out.println(result); } 事实证明，的确不可以这么做，因为在get方法往出拿的时候，会计算hash值，但是由于循环引用，这个hash值永远都算不出来，最终程序抛出了java.lang.StackOverflowError。 3. Map接口支持key和value都为null，但是有些底层实现是可以做额外限制的，比如不支持value为null，不支持key为null等。 4. Map里面还定义了一个成员接口Entry，这个接口代表Map内部存储的键值对
秉持每一个接口都要有个骨架实现的好习惯，JDK为我们提供了AbstractMap。 几乎所有的方法都帮我们实现好了，如果你想要实现一个不可变的Map，继承这个类，然后实现entrySet方法，返回一个继承了AbstractSet的类，而且这个类也不能实现add,remove这些方法，它的迭代器也不能实现remove方法，这样就可以得到不可变Map了。 如果想要可变的Map，继承这个类，然后实现put方法和entrySet方法，这次entrySet返回的类可以实现修改相关的方法，迭代器也是，这样你就有可变的Map实现了。 其他一系列方法你都不用管，都帮你实现好了，但是如果你去看源码，会发现JDK总是在实现类里去覆盖抽象类已经实现好的方法，主要是因为抽象类不能提前获知你最终实现类用的哪种底层数据结构，所以它给出的默认实现方法都是比较笨的方法。具体的实现类，根据底层数据结构的不同，可能有一些算法能显著提升方法性能，这时候实现类就会覆盖掉抽象类的方法。 ## HashMap（实现层） 要说Map体系最出名的是谁？当属HashMap。 要说整个集合框架最出名的是谁？HashMap绝对是有力竞争者。 HashMap出名不是没有来由的，它在绝大多数JAVA项目里，使用频率非常之高。我想，应该仅次于ArrayList。 HashMap名字的由来，是因为它使用了哈希表来实现Map这种数据结构。有趣的是，和Dictionary一样，早在1.0版本，就有一个叫HashTable的类实现和HashMap一样的功能，然而这个类用了synchronized来做线程安全，性能很差，在1.2版本中，被HashMap替代掉了。 哈希表的使用允许HashMap在增删改查这些操作上拥有常数时间的时间复杂度，即O(1)的时间复杂度。当然这是最理想的情况，在发生哈希碰撞的时候，时间复杂度会退化，在1.8之前的版本最差的时间复杂度是O(N)，在1.8版本使用了红黑树之后，最差的时间复杂度是O(logN)。 ### 内部结构 HashMap继承了AbstractMap骨架实现，不过绝大多数已经被骨架实现完成的方法它都覆盖并且重新写了自己的版本。 HashMap实现了Map，Cloneable，Serializable三个接口。 它的内部方法图如下： {% asset_img hashmap_inner_1.png %} 其中，前面有+号的是公有方法，-号的是私有方法，~是受保护的方法。 可以看到HashMap的公有方法基本上与Map接口定义的一致。下面是一些需要特别注意的： - HashMap不是线程安全的 - HashMap允许kay、value为Null，而我们上面提到的HashTable类不允许。 - HashMap的遍历一般使用entrySet视图的迭代器，也可以在只需要key的时候使用keySet视图。 - 使用put方法将一对key-value存入HashMap，使用get方法将key对应的value从HashMap中取出。注意，只能使用key去获取value，不能使用value去获取key，用value去获取key是比较麻烦的，也不是Map结构目标服务的情况。
可以看到，HashMap通过实现Map接口，为用户提供了一系列简单又方便的操作方法，但是，其底层的实现结构一点儿也不简单，只不过这些技术细节都被屏蔽了。 ### 底层结构 HashMap的底层结构实际上是一个自动扩容的数组，也就是方法图中的table字段。 数组中的每个位置又被称为哈希桶，每个哈希桶都可能存放一对key-value组合，一对key-value组合在Map体系中被称为Entry。因此也可以说每个位置都可能存放着一个Entry。 在实际使用的过程中，不管是取出数据还是放入数据，数据在table中的位置都是由key这个对象的hashCode()方法返回的数值决定的。如果返回4，那么就在table这个数组index为4的哈希桶中去存取数据。 #### 什么是哈希碰撞（哈希冲突）？ 由于我们的数组长度是有限的，但是key这个对象的hash值返回的数字有可能是超出数组长度的，比如，table数组的长度为16，而我们的Key对象算出来的hash值为30，那么不可能去index为30的地方去寻找哈希桶去存放数据，也不能就为了这么一个独立的数据，就将数组扩容到30以上，如果hash值算出来是一万，难道就要扩容到一万不成？因此，JDK作者会使用特殊的方法，将超出的部分，从头算起，直到找到一个table数组长度范围之内的位置，比如上面30这个例子，可能算出来是（30-16=14），就在14这个位置的哈希桶去做事情了。 但是问题来了，如果又有一个Key对象，算出来Hash值是14怎么办？两个Entry都想要放在同一个哈希桶里，这个时候就称发生了哈希碰撞或者叫哈希冲突。 #### 链表哈希桶和红黑树哈希桶结构解决哈希碰撞 JDK在1.8之前，一直使用的解决哈希碰撞的办法就是使用链表，将两个或者多个冲突的Entry都放在同一个哈希桶里，然后用链表这种结构把它们串起来。 示意图如下： {% asset_img hashmap_linkbin.png %} 可以看到： - 我们的key-value对是随机地存放在table中的，没有顺序保证，而使用entrySet视图的迭代器遍历的时候，可是从table数组的0位开始往后遍历的。遍历出来的Entry顺序完全没有保障。 - 当发生哈希碰撞的时候，哈希桶里存放的是一个key-value对，同时它们是链表的头节点，根据它们可以找到后续的节点，所有这些节点的key计算出来的hash值都是一样的，因此在get方法获取其中一个节点的时候，先通过hash值找到对应的哈希桶，然后遍历链表，再通过==和equals方法来判断所要获取的节点是哪一个。由于有遍历操作，而且如果哈希碰撞的情况很严重，那么链表可能很长，这就导致get方法的时间复杂度退化成了O(N)
在使用链表的HashMap中，每个Entry都是由一个叫做Node的结构来代表的，它的源代码如下：
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
可以知道，每个节点除了key，value以外，还会缓存hash值免得每次使用的时候都重算一遍，然后next就是链表的一部分了，代表下一个节点。我们从这个结构也可以知道，HashMap用来解决哈希碰撞的链表是个单向链表 在JDK1.8版本中，HashMap的结构有了变化，当一个哈希桶中的节点数量超过了TREEIFY_THRESHOLD这个常量(默认是8)时，会把链表结构转化成红黑树结构。 如下图： {% asset_img hashmap_treebin.png %} 红黑树是一个二叉平衡树，在最坏的情况下，插入删除查询节点的操作时间复杂度均在O(logN)，因此用它来替换链表可以在哈希桶里面节点太多的时候，显著提高性能。 不过这增加了内部实现的复杂度，害我研究很久才把这个结构看懂。有关红黑树的详细讲解，我们放到TreeMap这个实现类的介绍处，因为TreeMap也是基于红黑树来实现的，而且它的代码更加清晰一些。 还有一个常量UNTREEIFY_THRESHOLD，默认值是6，定义的是当节点少于这个值时，就把红黑树结构变回链表结构。 #### 初始化table数组 关于初始化table数组也有很多值得关注的地方。 首先我们知道有两个值，一个叫做initialCapacity，另一个叫做loadFactor。 initialCapacity定义了最初HashMap内部的table数组初始化的大小，如果用户不传，默认就是DEFAULT_INITIAL_CAPACITY，即16。 而loadFactor，翻译过来叫做负载因子的，则定义了当数组的容量用到百分之多少时，开始对数组进行扩容操作。这个值是一个float，单精度浮点数值。如果用户不传，默认就是DEFAULT_LOAD_FACTOR，即0.75f。 如果一开始initialCapacity取的很大，显然，我们数组一直就是够用的，扩容操作发生的可能性就小的多，但是这样就会浪费空间。如果我们的loadFactor取得很小，那么扩容操作就会很频繁，性能就会很差，但是如果取得太大，数组迟迟不扩容，就可能导致某些哈希桶里塞很多节点，性能同样好不到哪儿去。 所以，我们在初始化HashMap的时候，这两个数值都要取合适的值，一般容量要取预期会存入的Entry数量的1.2倍到1.5倍比较好。而loadFactor则保持默认不变。
这里我们要特别注意的是，无论你传入的initialCapacity是多少，最终HashMap内部的table数组，其大小都必须是2的指数幂。如果你传入的是31，那么大小可能会被变成32，传入50，会被变成64等等。 不相信的话，可以看下面两段代码：
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); }static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
从上面的方法我们可以知道： - 你传入的容量不能超过MAXIMUM_CAPACITY，这个值并不是数组大小的最大值，我们在前面介绍过，数组大小最大值是Integer.MAX_VALUE - 8，而此处的最大值却是：1<<30， 也即2的30次方。和Ieteger.Max_VALUE的2的31次方-1比起来，小的多。 - tableSizeFor方法会先将你传入的数字减一，然后不断地与向右移位的值做或运算，这样做下来的结果再加1就会得到某个2的指数幂。这其实也很好理解，在之前的章节中，双端队列的实现类ArrayDeque已经使用过相似的技巧。为什么要这样做，在ArrayDeque处也解释过，这样做是为了通过-1来方便地生成掩码，从而处理越界的情况。在这里，我们的HashMap前面提起过，也存在类似的越界问题，当hash值算出来比数组的大小大的时候，要想办法把这个值最终转化成数组大小范围内的值，而这个办法就是通过掩码来实现的。可见后面的详细介绍。 - 注意，整个初始化方法结束，都没有见到table数组真的被new出来，这和其他的比如ArrayList这类结构是一样的，底层结构并不是在构造函数执行之后就new的，而是在用户第一次使用诸如put、add这种方法的时候，才初始化底层结构的。 - 传入的容量最好不要太大，遍历操作为了能够找到所有有内容的哈希桶，可是会将你初始化的数组全部遍历一遍的，即使只放了2,3个值进去，如果你初始化容量是一万，并且恰好有个值放在第一万个哈希桶中，那么遍历操作可能就是一万次循环才结束。
扩容数组主要是一个叫做resize的方法在做，实际上，该方法还负责真正地把table数组给new出来。下面是它的源代码，并附上中文注释：
final Node<K, V>[] resize() { Node<K, V>[] oldTab = table;//获取旧table int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧table可能还没初始化，那么旧容量就是0 int oldThr = threshold;//threshold在没初始化前代表用户指定的容量，初始化后代表用户指定的容量*loadFactor int newCap, newThr = 0; if (oldCap > 0) {//大于零，说明table已经初始化过了 if (oldCap >= MAXIMUM_CAPACITY) {//已经无法再扩容了 threshold = Integer.MAX_VALUE; return oldTab;//直接返回旧的 } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//新容量等于旧容量的2倍。如果新容量不大于最大容量，旧容量不小于默认初始化容量，就吧threshold也变两倍 newThr = oldThr << 1; // double threshold } else if (oldThr > 0) //还没初始化过且老的threshold大于零，说明用户指定了初始化容量，就把新容量设为用户指定的 newCap = oldThr; else {//还没初始化过且用户没指定容量，就用默认的 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) {//上面if条件句的3种情况，只有第二种才有可能是newThr等于零，即用户指定了初始化容量的情况， // 这种情况下要计算一下threshold，其中loadFactor可能用的用户指定的值。 // 不对，我刚才发现，如果上面第一种情况里面的else if条件句不满足的话，也会在这里计算newThr float ft = (float) newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } threshold = newThr;//无论哪种情况，将算好的值回填回threshold域值中 @SuppressWarnings({"rawtypes", "unchecked"}) Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];//此处真正初始化了！如果是扩容，也是直接初始化了扩容后大小的数组 table = newTab;//回填回table域 if (oldTab != null) {//不等于null说明不是初始化，有旧的table存在，要想办法把旧的table的节点都复制过来，由于容量现在大了，可能以前会碰撞的节点现在也许碰撞不上了，要rehash将他们分配到新的哈希桶里去 for (int j = 0; j < oldCap; ++j) {//遍历旧的table，因此扩容操作的时间复杂度至少有O(N) Node<K, V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null;//把旧的table中有东西的位置清空，可以帮助垃圾处理器更快地回收垃圾 if (e.next == null)//next为空说明这个哈希桶里装的既不是链表也不是树，就是一个普通的节点而已 newTab[e.hash & (newCap - 1)] = e;//将该节点放到新的table数组中，newCap-1就是防止数组越界的掩码，这个下面会详细讲解。【难点一】 else if (e instanceof TreeNode)//next不为空，那就要看看是不是个树节点了 ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);//是树节点，使用树节点的方法来将整个树里的节点们rehash else {//只剩下一种可能了，就是哈希桶里是链表 Node<K, V> loHead = null, loTail = null; Node<K, V> hiHead = null, hiTail = null; Node<K, V> next; do {//遍历链表，时间复杂度上升到O(N*M),M为链表长度 next = e.next; if ((e.hash & oldCap) == 0) {//与运算，为0说明不需要把这个节点放到其他哈希桶中【难点二】 if (loTail == null)//第一次进这个if条件的时候loTail还没值 loHead = e;//头指针指向第一个节点 else loTail.next = e;//尾指针即最后一个节点的下一个指向e，即把e挂在链表最后 loTail = e;//尾指针指向当前遍历的节点 } else {//说明这个节点要放到另一个哈希桶中 if (hiTail == null)//第一次进if时，这个hiTail还没值 hiHead = e;//头指针指向第一个节点 else hiTail.next = e;//尾指针的下一个是e，也就是把e挂在链表末尾 hiTail = e;//尾指针指向当前遍历的节点 } } while ((e = next) != null);//往下一个遍历，其实这里可以浓缩成((e=e.next)!=null),不需要提前赋值next。 if (loTail != null) {//不等于null，说明我们有一些节点不需要放到其他哈希桶中，它们要留在原地 loTail.next = null; newTab[j] = loHead;//留在原地，把链表头设给数组 } if (hiTail != null) {//说明我们有一些节点需要放到其他哈希桶中，它们已经不适合呆在这里了 hiTail.next = null; newTab[j + oldCap] = hiHead;//加上了oldCap，这是因为新table扩容了一倍，为什么会跑到加oldCap的哈希桶里去，见【难点二】 } } } } } return newTab; }
可以看到，这个方法又臭又长，这主要是因为它又想要初始化内部的table，又想要承担扩容的工作。在《简洁代码之道》这本书里曾经写到过，我们要遵循单一职责的设计原则，一个方法尽量只做一件事。 不要以为JDK就有很漂亮的代码，此处的代码笔者认为写的非常糟糕，可读性很差。当然，虽然可读性很差，它却逻辑完美地处理了各种各样的情况，而且处理这些情况的代码还交织在一起，真是让人又爱又恨啊。
首先第一个需要说明的点就是threshold这个域。它居然承担了两种含义，在初始化前，它用来保存用户传入的initialCapacity，在初始化后，它用来保存计算好的initialCapacity*loadFactor，这个值是下一次执行resize方法的信号，当size大于这个值时，就执行rezise。 我们在平时写代码的时候，可不要这么复用，虽然JDK作者这么复用，可以少一个域出来，对于这种底层被调用很多的类而言，少一个域的确能减少很多空间，但是我们不是JDK的作者，我们是上层应用，不需要牺牲可读性来做这种事。
其余的代码中文注释都很详细了，可能唯一需要解释的就是标注难点一和难点二的地方。 【难点一】 难点一就是之前讲到过的作者如何解决hash值超出了数组大小的问题。在讲这个问题之前，要先说一个方法：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
别看这个方法短小，但是在所有计算hash值的地方，作者都用到了这个方法。 我们可以知道：作者并没有简单地使用Key对象hashCode()方法返回的哈希值。作者将返回的哈希值的低16位和高16位做了异或运算。将运算后的结果返回了。 这是为什么呢？ 这就要说到我们难点一处标记的代码了，在利用hash值去寻找哈希桶的时候，我们作者使用了这个语法：e.hash & (newCap - 1) 我们已经知道，newCap肯定是2的指数幂。因此它的二进制数肯定是1后面跟着一堆0，类似10、100、1000、10000这样的数。 然后看下图你就明白为什么这样做了： {% asset_img hashmap_resize.png %} 可以看到，我们的hash值是123，远远超过了数组容量16，因此作者利用数组容量-1得到掩码，即15。这个掩码有个特性，就是它去和其他数字做与运算的时候，会把其他数字的一些位数抹除成0。 我们例子里的容量是16，那么就希望最终算出来的数字小于16，也即二进制数的1只出现在最后四位上，怎么达到这一效果呢？就是用15这个掩码去做与运算，抹除掉后四位以外其他位上的1。 这样不管你的hash值有多大，最终得到的只是后4位形成的数字而已，而后四位即使全是1也才15，无论如何也不会超过16，自然也就不会数组越界了。 到这里恐怕聪明的人立刻就会有这样的问题：如果在计算位置的时候，只用到了hash值的低4位，没有充分地将hash值的全部位数使用起来，这样很容易发生碰撞呀！ 没错，在数组容量小的时候，很多对象的hash值，其低4位可能都是相同的，这样太容易发生碰撞了，怎么办？于是就有了上面的hash那个方法，作者把高16位与低16位做了异或运算，将高16位的作用叠加在低16位上，想要以此来降低数组容量比较低时，哈希碰撞的概率。 另外，我们前面提到过，HashMap内部数组的最大值也才2的30次方，掩码的话，最大也才29位。而我们的hash值可是有32位呢。总不能丢弃高4位不用吧，这里的异或运算也可以解决这个问题。 【难点二】 难点二在讲如何判断旧的table中的某个节点，应该被移到新的哈希桶中。此处作者用到的语法是(e.hash & oldCap) == 0。讲真这个我也是看了别人的分析才懂。 首先我们要知道一个前提：HashMap扩容的话，一定是2倍，这样才能保证扩容后，容量仍然是2的指数幂。 如果原来是10000，那么扩容后是多少？ 答案是100000，就比原来多了一位。 这样的话，我想就很好理解了，新容量比旧容量多了一位哦！那么新容量的掩码就比旧容量多了一位！原来只有低4位起作用的话，现在第5位也要起作用！ 以此推断，如果我们原来这个节点的hash值，第5位是个0，那么它和新的容量掩码做了与运算，结果和原容量掩码做与运算，是一样的。如果第5位是个1，结果就不一样了！就要放到新的哈希桶中。 见下图，此图我们假设新的容量是32，而旧容量是16： {% asset_img hashmap_resize2.png %} 然后你再看作者使用的语法，就会发现，作者把oldCap当做掩码来用了，oldCap的1刚好就处在新增加的那个位上，所以用oldCap去和hash值做与运算，就只会留下那个位上的值，其他位数都被清0了。如此以来，如果等于0，就说明hash值相应位数上本来就是个0，新增加的位数没有对节点属于哪个哈希桶产生影响。