摘要：extends V> m)\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E该构造函数意在构造一个与指定 Map 具有相同映射的 HashMap，其 初始容量不小于 16 (具体依赖于指定Map的大小)，负载因子是 0.75，是 Java Collection Framework 规范推荐提供的，其源码如下：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F\u002F Constructs a new HashMap with the same mappings as the specified Map. \u003Cbr\u003E \u002F\u002F The HashMap is created with default load factor (0.75) and an initial capacity\u003Cbr\u003E \u002F\u002F sufficient to hold the mappings in the specified Map.\u003Cbr\u003E public HashMap(Map"\u003Cdiv\u003E\u003Ch1\u003E\u003Cstrong\u003E写在前面\u003C\u002Fstrong\u003E\u003C\u002Fh1\u003E\u003Cp\u003EHashMap是Map族中最为常用的一种，也是 Java Collection Framework 的重要成员。本文首先给出了 HashMap 的实质并概述了其与 Map、HashSet 的关系，紧接着给出了 HashMap 在 JDK 中的定义，并结合源码分析了其四种构造方式。最后，通过对 HashMap 的数据结构、实现原理、源码实现三个方面的剖析，深入到它底层 Hash 存储机制，解释了其底层数组长度总是 2 的 n 次方的原因，也揭示了其快速存取、扩容及扩容后的重哈希的原理与实现。\u003C\u002Fp\u003E\u003Cdiv class=\"pgc-img\"\u003E\u003Cimg src=\"http:\u002F\u002Fp3.pstatp.com\u002Flarge\u002Fpgc-image\u002Fce4d4b5650c34515a772546786679ef1\" img_width=\"533\" img_height=\"300\" alt=\"300000年薪架构技术（HashMap）身为程序员的你还没掌握吗？\" inline=\"0\"\u003E\u003Cp class=\"pgc-img-caption\"\u003E\u003C\u002Fp\u003E\u003C\u002Fdiv\u003E\u003Cp\u003E本文所有关于HashMap的源码都是基于\u003Cstrong\u003EJDK 1.6\u003C\u002Fstrong\u003E的，不同 JDK 版本之间也许会有些许差异，但不影响我们对 HashMap 的数据结构、原理等整体的把握和了解。\u003C\u002Fp\u003E\u003Ch1\u003E\u003Cstrong\u003EHashMap 概述\u003C\u002Fstrong\u003E\u003C\u002Fh1\u003E\u003Cp\u003EMap 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。HashMap 是 Java Collection Framework 的重要成员，也是Map族(如下图所示)中我们最为常用的一种。简单地说，HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形式存在，即存储的对象是 Entry (同时包含了 Key 和 Value) 。在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地，\u003Cstrong\u003EHashMap最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null\u003C\u002Fstrong\u003E。此外，HashMap 是 Map 的一个非同步的实现。\u003C\u002Fp\u003E\u003Cdiv class=\"pgc-img\"\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002F0e8ff8170afd44c6b158f4eb60892ab9\" img_width=\"640\" img_height=\"400\" alt=\"300000年薪架构技术（HashMap）身为程序员的你还没掌握吗？\" inline=\"0\"\u003E\u003Cp class=\"pgc-img-caption\"\u003E\u003C\u002Fp\u003E\u003C\u002Fdiv\u003E\u003Cp\u003E\u003Cstrong\u003E虽然 HashMap 和 HashSet 实现的接口规范不同，但是它们底层的 Hash 存储机制完全相同。实际上，HashSet 本身就是在 HashMap 的基础上实现的\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Ch1\u003E\u003Cstrong\u003EHashMap 在 JDK 中的定义\u003C\u002Fstrong\u003E\u003C\u002Fh1\u003E\u003Cp\u003EHashMap实现了Map接口，并继承 AbstractMap 抽象类，其中 Map 接口定义了键值映射规则。和 AbstractCollection抽象类在 Collection 族的作用类似， AbstractMap 抽象类提供了 Map 接口的骨干实现，以最大限度地减少实现Map接口所需的工作。HashMap 在JDK中的定义为：\u003C\u002Fp\u003E\u003Cpre\u003Epublic class HashMap<K, V> extends AbstractMap<K, V>\u003Cbr\u003Eimplements Map<K, V>, Cloneable, Serializable {\u003Cbr\u003E ...\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Ch1\u003E\u003Cstrong\u003EHashMap 的构造函数\u003C\u002Fstrong\u003E\u003C\u002Fh1\u003E\u003Cp\u003EHashMap 一共提供了四个构造函数，其中 默认无参的构造函数 和 参数为Map的构造函数 为 Java Collection Framework 规范的推荐实现，其余两个构造函数则是 HashMap 专门提供的。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003E1、HashMap()\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E该构造函数意在构造一个具有> 默认初始容量 (16) 和 默认负载因子(0.75) 的空 HashMap，是 Java Collection Framework 规范推荐提供的，其源码如下：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E * Constructs an empty HashMap with the default initial capacity\u003Cbr\u003E * (16) and the default load factor (0.75).\u003Cbr\u003E *\u002F\u003Cbr\u003E public HashMap() {\u003Cbr\u003E \u002F\u002F负载因子:用于衡量的是一个散列表的空间的使用程度\u003Cbr\u003E this.loadFactor = DEFAULT_LOAD_FACTOR; \u003Cbr\u003E \u002F\u002FHashMap进行扩容的阈值，它的值等于 HashMap 的容量乘以负载因子\u003Cbr\u003E threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);\u003Cbr\u003E \u002F\u002F HashMap的底层实现仍是数组，只是数组的每一项都是一条链\u003Cbr\u003E table = new Entry[DEFAULT_INITIAL_CAPACITY];\u003Cbr\u003E init();\u003Cbr\u003E }\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E2、HashMap(int initialCapacity, float loadFactor)\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E该构造函数意在构造一个 指定初始容量 和 指定负载因子的空 HashMap，其源码如下：\u003C\u002Fp\u003E\u003Cpre\u003E \u002F**\u003Cbr\u003E * Constructs an empty HashMap with the specified initial capacity and load factor.\u003Cbr\u003E *\u002F\u003Cbr\u003E public HashMap(int initialCapacity, float loadFactor) {\u003Cbr\u003E \u002F\u002F初始容量不能小于 0\u003Cbr\u003E if (initialCapacity < 0)\u003Cbr\u003E throw new IllegalArgumentException(\"Illegal initial capacity: \" + initialCapacity);\u003Cbr\u003E \u002F\u002F初始容量不能超过 2^30\u003Cbr\u003E if (initialCapacity > MAXIMUM_CAPACITY)\u003Cbr\u003E initialCapacity = MAXIMUM_CAPACITY;\u003Cbr\u003E \u002F\u002F负载因子不能小于 0 \u003Cbr\u003E if (loadFactor <= 0 || Float.isNaN(loadFactor))\u003Cbr\u003E throw new IllegalArgumentException(\"Illegal load factor: \" +\u003Cbr\u003E loadFactor);\u003Cbr\u003E \u002F\u002F HashMap 的容量必须是2的幂次方，超过 initialCapacity 的最小 2^n \u003Cbr\u003E int capacity = 1;\u003Cbr\u003E while (capacity < initialCapacity)\u003Cbr\u003E capacity <<= 1; \u003Cbr\u003E \u002F\u002F负载因子\u003Cbr\u003E this.loadFactor = loadFactor;\u003Cbr\u003E \u002F\u002F设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行自动扩容操作\u003Cbr\u003E threshold = (int)(capacity * loadFactor);\u003Cbr\u003E \u002F\u002F HashMap的底层实现仍是数组，只是数组的每一项都是一条链\u003Cbr\u003E table = new Entry[capacity];\u003Cbr\u003E init();\u003Cbr\u003E }\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E3、HashMap(int initialCapacity)\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E该构造函数意在构造一个指定初始容量和默认负载因子 (0.75)的空 HashMap，其源码如下：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F\u002F Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75)\u003Cbr\u003E public HashMap(int initialCapacity) {\u003Cbr\u003E this(initialCapacity, DEFAULT_LOAD_FACTOR); \u002F\u002F 直接调用上述构造函数\u003Cbr\u003E }\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E4、HashMap(Map<? extends K, ? extends V> m)\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E该构造函数意在构造一个与指定 Map 具有相同映射的 HashMap，其 初始容量不小于 16 (具体依赖于指定Map的大小)，负载因子是 0.75，是 Java Collection Framework 规范推荐提供的，其源码如下：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F\u002F Constructs a new HashMap with the same mappings as the specified Map. \u003Cbr\u003E \u002F\u002F The HashMap is created with default load factor (0.75) and an initial capacity\u003Cbr\u003E \u002F\u002F sufficient to hold the mappings in the specified Map.\u003Cbr\u003E public HashMap(Map<? extends K, ? extends V> m) {\u003Cbr\u003E \u002F\u002F 初始容量不小于 16 \u003Cbr\u003E this(Math.max((int) (m.size() \u002F DEFAULT_LOAD_FACTOR) + 1,\u003Cbr\u003E DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);\u003Cbr\u003E putAllForCreate(m);\u003Cbr\u003E }\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E在这里，我们提到了两个非常重要的参数：\u003Cstrong\u003E初始容量 和 负载因子\u003C\u002Fstrong\u003E，这两个参数是影响HashMap性能的重要参数。其中，\u003Cstrong\u003E容量表示哈希表中桶的数量 (table 数组的大小)，初始容量是创建哈希表时桶的数量；负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小\u003C\u002Fstrong\u003E。\u003C\u002Fp\u003E\u003Ch1\u003E\u003Cstrong\u003EHashMap 的数据结构\u003C\u002Fstrong\u003E\u003C\u002Fh1\u003E\u003Cp\u003E\u003Cstrong\u003E哈希的相关概念\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003EHash 就是把任意长度的输入(又叫做预映射， pre-image)，通过哈希算法，变换成固定长度的输出(通常是整型)，该输出就是哈希值。这种转换是一种 压缩映射 ，也就是说，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，从而不可能从散列值来唯一的确定输入值。简单的说，就是一种将任意长度的消息压缩到某一固定长度的息摘要函数。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003E哈希的应用：数据结构\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E我们知道，\u003Cstrong\u003E数组的特点是：寻址容易，插入和删除困难\u003C\u002Fstrong\u003E；\u003Cstrong\u003E而链表的特点是：寻址困难，插入和删除容易\u003C\u002Fstrong\u003E。那么我们能不能综合两者的特性，做出一种寻址容易，插入和删除也容易的数据结构呢？答案是肯定的，这就是我们要提起的哈希表。事实上，哈希表有多种不同的实现方法，我们接下来解释的是最经典的一种方法 —— 拉链法，我们可以将其理解为 链表的数组，如下图所示：\u003C\u002Fp\u003E\u003Cdiv class=\"pgc-img\"\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002Fd79d403c97664f5c8ce3d328575a8461\" img_width=\"541\" img_height=\"456\" alt=\"300000年薪架构技术（HashMap）身为程序员的你还没掌握吗？\" inline=\"0\"\u003E\u003Cp class=\"pgc-img-caption\"\u003E\u003C\u002Fp\u003E\u003C\u002Fdiv\u003E\u003Cp\u003E我们可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征计算元素数组下标的方法就是 哈希算法。\u003C\u002Fp\u003E\u003Cp\u003E总的来说，哈希表适合用作快速查找、删除的基本数据结构，通常需要总数据量可以放入内存。在使用哈希表时，有以下几个关键点：\u003C\u002Fp\u003E\u003Cul\u003E\u003Cli\u003Ehash 函数（哈希算法）的选择：针对不同的对象(字符串、整数等)具体的哈希方法；\u003C\u002Fli\u003E\u003Cli\u003E碰撞处理：常用的有两种方式，一种是open hashing，即 >拉链法；\u003C\u002Fli\u003E\u003Cli\u003E另一种就是 closed hashing，即开地址法(opened addressing)。\u003C\u002Fli\u003E\u003C\u002Ful\u003E\u003Cp\u003E\u003Cstrong\u003EHashMap 的数据结构\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E我们知道，在Java中最常用的两种结构是 数组 和 链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap 就是这种应用的一个典型。实际上，HashMap 就是一个 链表数组，如下是它数据结构：\u003C\u002Fp\u003E\u003Cp class=\"ql-align-center\"\u003E\u003Cbr\u003E\u003C\u002Fp\u003E\u003Cdiv class=\"pgc-img\"\u003E\u003Cimg src=\"http:\u002F\u002Fp3.pstatp.com\u002Flarge\u002Fpgc-image\u002Ff4b4b83c75f44442ae6c6c52475e5dd1\" img_width=\"640\" img_height=\"372\" alt=\"300000年薪架构技术（HashMap）身为程序员的你还没掌握吗？\" inline=\"0\"\u003E\u003Cp class=\"pgc-img-caption\"\u003E\u003C\u002Fp\u003E\u003C\u002Fdiv\u003E\u003Cp\u003E 从上图中，我们可以形象地看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity 就代表了该数组的长度，也就是桶的个数。在第三节我们已经了解了HashMap 的默认构造函数的源码：\u003C\u002Fp\u003E\u003Cpre\u003E \u002F**\u003Cbr\u003E * Constructs an empty HashMap with the default initial capacity\u003Cbr\u003E * (16) and the default load factor (0.75).\u003Cbr\u003E *\u002F\u003Cbr\u003E public HashMap() {\u003Cbr\u003E \u002F\u002F负载因子:用于衡量的是一个散列表的空间的使用程度\u003Cbr\u003E this.loadFactor = DEFAULT_LOAD_FACTOR; \u003Cbr\u003E \u002F\u002FHashMap进行扩容的阈值，它的值等于 HashMap 的容量乘以负载因子\u003Cbr\u003E threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);\u003Cbr\u003E \u002F\u002F HashMap的底层实现仍是数组，只是数组的每一项都是一条链\u003Cbr\u003E table = new Entry[DEFAULT_INITIAL_CAPACITY];\u003Cbr\u003E init();\u003Cbr\u003E }\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E从上述源码中我们可以看出，每次新建一个HashMap时，都会初始化一个Entry类型的table数组，其中 Entry类型的定义如下：\u003C\u002Fp\u003E\u003Cpre\u003Estatic class Entry<K,V> implements Map.Entry<K,V> {\u003Cbr\u003E final K key; \u002F\u002F 键值对的键\u003Cbr\u003E V value; \u002F\u002F 键值对的值\u003Cbr\u003E Entry<K,V> next; \u002F\u002F 下一个节点\u003Cbr\u003E final int hash; \u002F\u002F hash(key.hashCode())方法的返回值\u003Cbr\u003E \u002F**\u003Cbr\u003E * Creates new entry.\u003Cbr\u003E *\u002F\u003Cbr\u003E Entry(int h, K k, V v, Entry<K,V> n) { \u002F\u002F Entry 的构造函数\u003Cbr\u003E value = v;\u003Cbr\u003E next = n;\u003Cbr\u003E key = k;\u003Cbr\u003E hash = h;\u003Cbr\u003E }\u003Cbr\u003E ......\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E其中，Entry为HashMap的内部类，实现了 Map.Entry 接口，其包含了键key、值value、下一个节点next，以及hash值四个属性。事实上，Entry 是构成哈希表的基石，是哈希表所存储的元素的具体形式。\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Ch1\u003E\u003Cstrong\u003EHashMap 的快速存取\u003C\u002Fstrong\u003E\u003C\u002Fh1\u003E\u003Cp\u003E\u003Cstrong\u003E下面我们结合JDK源码看HashMap 的存取实现\u003C\u002Fstrong\u003E。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003EHashMap 的存储实现\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E在 HashMap 中，键值对的存储是通过 put(key,vlaue) 方法来实现的，其源码如下：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E * Associates the specified value with the specified key in this map.\u003Cbr\u003E * If the map previously contained a mapping for the key, the old\u003Cbr\u003E * value is replaced.\u003Cbr\u003E *\u003Cbr\u003E * @param key key with which the specified value is to be associated\u003Cbr\u003E * @param value value to be associated with the specified key\u003Cbr\u003E * @return the previous value associated with key, or null if there was no mapping for key.\u003Cbr\u003E * Note that a null return can also indicate that the map previously associated null with key.\u003Cbr\u003E *\u002F\u003Cbr\u003E public V put(K key, V value) {\u003Cbr\u003E \u002F\u002F当key为null时，调用putForNullKey方法，并将该键值对保存到table的第一个位置 \u003Cbr\u003E if (key == null)\u003Cbr\u003E return putForNullKey(value); \u003Cbr\u003E \u002F\u002F根据key的hashCode计算hash值\u003Cbr\u003E int hash = hash(key.hashCode()); \u002F\u002F ------- (1)\u003Cbr\u003E \u002F\u002F计算该键值对在数组中的存储位置（哪个桶）\u003Cbr\u003E int i = indexFor(hash, table.length); \u002F\u002F ------- (2)\u003Cbr\u003E \u002F\u002F在table的第i个桶上进行迭代，寻找 key 保存的位置\u003Cbr\u003E for (Entry<K,V> e = table[i]; e != null; e = e.next) { \u002F\u002F ------- (3)\u003Cbr\u003E Object k;\u003Cbr\u003E \u002F\u002F判断该条链上是否存在hash值相同且key值相等的映射，若存在，则直接覆盖 value，并返回旧value\u003Cbr\u003E if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {\u003Cbr\u003E V oldValue = e.value;\u003Cbr\u003E e.value = value;\u003Cbr\u003E e.recordAccess(this);\u003Cbr\u003E return oldValue; \u002F\u002F 返回旧值\u003Cbr\u003E }\u003Cbr\u003E }\u003Cbr\u003E modCount++; \u002F\u002F修改次数增加1，快速失败机制\u003Cbr\u003E \u002F\u002F原HashMap中无该映射，将该添加至该链的链头\u003Cbr\u003E addEntry(hash, key, value, i); \u003Cbr\u003E return null;\u003Cbr\u003E }\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E对NULL键的特别处理：putForNullKey()\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E我们直接看其源码：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E * Offloaded version of put for null keys\u003Cbr\u003E *\u002F\u003Cbr\u003E private V putForNullKey(V value) {\u003Cbr\u003E \u002F\u002F 若key==null，则将其放入table的第一个桶，即 table[0]\u003Cbr\u003E for (Entry<K,V> e = table[0]; e != null; e = e.next) { \u003Cbr\u003E if (e.key == null) { \u002F\u002F 若已经存在key为null的键，则替换其值，并返回旧值\u003Cbr\u003E V oldValue = e.value;\u003Cbr\u003E e.value = value;\u003Cbr\u003E e.recordAccess(this);\u003Cbr\u003E return oldValue;\u003Cbr\u003E }\u003Cbr\u003E }\u003Cbr\u003E modCount++; \u002F\u002F 快速失败\u003Cbr\u003E addEntry(0, null, value, 0); \u002F\u002F 否则，将其添加到 table[0] 的桶中\u003Cbr\u003E return null;\u003Cbr\u003E }\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003EHashMap 中的哈希策略（算法）\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E* Applies a supplemental hash function to a given hashCode, which\u003Cbr\u003E* defends against poor quality hash functions. This is critical\u003Cbr\u003E* because HashMap uses power-of-two length hash tables, that\u003Cbr\u003E* otherwise encounter collisions for hashCodes that do not differ\u003Cbr\u003E* in lower bits.\u003Cbr\u003E*\u003Cbr\u003E* Note: Null keys always map to hash 0, thus index 0.\u003Cbr\u003E*\u002F\u003Cbr\u003Estatic int hash(int h) {\u003Cbr\u003E\u002F\u002F This function ensures that hashCodes that differ only by\u003Cbr\u003E\u002F\u002F constant multiples at each bit position have a bounded\u003Cbr\u003E\u002F\u002F number of collisions (approximately 8 at default load factor).\u003Cbr\u003Eh ^= (h >>> 20) ^ (h >>> 12);\u003Cbr\u003Ereturn h ^ (h >>> 7) ^ (h >>> 4);\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E正如JDK官方对该方法的描述那样，使用hash()方法对一个对象的hashCode进行重新计算是为了防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是 2 的幂次，通过右移可以使低位的数据尽量的不同，从而使hash值的分布尽量均匀。\u003C\u002Fp\u003E\u003Cp\u003E通过上述hash()方法计算得到 Key 的 hash值 后，怎么才能保证元素均匀分布到table的每个桶中呢？我们会想到取模，但是由于取模的效率较低，HashMap 是通过调用上面的indexFor()方法处理的，其不但简单而且效率很高，对应源码如下所示：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E *\u003Cbr\u003E * Returns index for hash code h.\u003Cbr\u003E *\u003Cbr\u003E *\u002F\u003Cbr\u003Estatic int indexFor( int h, int length )\u003Cbr\u003E{\u003Cbr\u003E return(h & (length - 1) ); \u002F* 作用等价于取模运算，但这种方式效率更高 *\u002F\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003EHashMap 中键值对的添加：addEntry()\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E我们直接看其源码：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E * Adds a new entry with the specified key, value and hash code to\u003Cbr\u003E * the specified bucket. It is the responsibility of this\u003Cbr\u003E * method to resize the table if appropriate.\u003Cbr\u003E *\u003Cbr\u003E * Subclass overrides this to alter the behavior of put method.\u003Cbr\u003E * \u003Cbr\u003E * 永远都是在链表的表头添加新元素\u003Cbr\u003E *\u002F\u003Cbr\u003E void addEntry(int hash, K key, V value, int bucketIndex) {\u003Cbr\u003E \u002F\u002F获取bucketIndex处的链表\u003Cbr\u003E Entry<K,V> e = table[bucketIndex];\u003Cbr\u003E \u002F\u002F将新创建的 Entry 链入 bucketIndex处的链表的表头 \u003Cbr\u003E table[bucketIndex] = new Entry<K,V>(hash, key, value, e);\u003Cbr\u003E \u002F\u002F若HashMap中元素的个数超过极限值 threshold，则容量扩大两倍\u003Cbr\u003E if (size++ >= threshold)\u003Cbr\u003E resize(2 * table.length);\u003Cbr\u003E }\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003EHashMap 的扩容：resize()\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E随着HashMap中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子链长度就会越来越长，这样势必会影响HashMap的存取速度。\u003Cem\u003E为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理，该临界点就是HashMap中元素的数量在数值上等于threshold（table数组长度加载因子）。但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。所以，如果我们能够提前预知HashMap 中元素的个数，那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能\u003C\u002Fem\u003E*。我们直接看其源码：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E *\u003Cbr\u003E * Rehashes the contents of this map into a new array with a\u003Cbr\u003E *\u003Cbr\u003E * larger capacity. This method is called automatically when the\u003Cbr\u003E *\u003Cbr\u003E * number of keys in this map reaches its threshold.\u003Cbr\u003E *\u003Cbr\u003E *\u003Cbr\u003E *\u003Cbr\u003E * If current capacity is MAXIMUM_CAPACITY, this method does not\u003Cbr\u003E *\u003Cbr\u003E * resize the map, but sets threshold to Integer.MAX_VALUE.\u003Cbr\u003E *\u003Cbr\u003E * This has the effect of preventing future calls.\u003Cbr\u003E *\u003Cbr\u003E *\u003Cbr\u003E *\u003Cbr\u003E * @param newCapacity the new capacity, MUST be a power of two;\u003Cbr\u003E *\u003Cbr\u003E * must be greater than current capacity unless current\u003Cbr\u003E *\u003Cbr\u003E * capacity is MAXIMUM_CAPACITY (in which case value\u003Cbr\u003E *\u003Cbr\u003E * is irrelevant).\u003Cbr\u003E *\u003Cbr\u003E *\u002F\u003Cbr\u003Evoid resize( int newCapacity )\u003Cbr\u003E{\u003Cbr\u003E Entry[] oldTable = table;\u003Cbr\u003E int oldCapacity = oldTable.length;\u003Cbr\u003E \u002F* 若 oldCapacity 已达到最大值，直接将 threshold 设为 Integer.MAX_VALUE *\u002F\u003Cbr\u003E if ( oldCapacity == MAXIMUM_CAPACITY )\u003Cbr\u003E {\u003Cbr\u003E threshold = Integer.MAX_VALUE;\u003Cbr\u003E return; \u002F* 直接返回 *\u002F\u003Cbr\u003E }\u003Cbr\u003E \u002F* 否则，创建一个更大的数组 *\u002F\u003Cbr\u003E Entry[] newTable = new Entry[newCapacity];\u003Cbr\u003E \u002F* 将每条Entry重新哈希到新的数组中 *\u002F\u003Cbr\u003E transfer( newTable );\u003Cbr\u003E table = newTable;\u003Cbr\u003E threshold = (int) (newCapacity * loadFactor); \u002F* 重新设定 threshold *\u002F\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003EHashMap 的重哈希：transfer()\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E重哈希的主要是一个重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程，我们直接看其源码：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E*\u003Cbr\u003E* Transfers all entries from current table to newTable.\u003Cbr\u003E*\u003Cbr\u003E*\u002F\u003Cbr\u003Evoid transfer( Entry[] newTable )\u003Cbr\u003E{\u003Cbr\u003E\u002F* 将原数组 table 赋给数组 src *\u002F\u003Cbr\u003EEntry[] src = table;\u003Cbr\u003Eint newCapacity = newTable.length;\u003Cbr\u003E\u002F* 将数组 src 中的每条链重新添加到 newTable 中 *\u002F\u003Cbr\u003Efor ( int j = 0; j < src.length; j++ )\u003Cbr\u003E{\u003Cbr\u003EEntry<K, V> e = src[j];\u003Cbr\u003Eif ( e != null )\u003Cbr\u003E{\u003Cbr\u003Esrc[j] = null; \u002F* src 回收 *\u002F\u003Cbr\u003E\u002F* 将每条链的每个元素依次添加到 newTable 中相应的桶中 *\u002F\u003Cbr\u003Edo\u003Cbr\u003E{\u003Cbr\u003EEntry<K, V> next = e.next;\u003Cbr\u003E\u002F* e.hash指的是 hash(key.hashCode())的返回值; *\u002F\u003Cbr\u003E\u002F* 计算在newTable中的位置，注意原来在同一条子链上的元素可能被分配到不同的子链 *\u002F\u003Cbr\u003Eint i = indexFor( e.hash, newCapacity );\u003Cbr\u003Ee.next = newTable[i];\u003Cbr\u003EnewTable[i] = e;\u003Cbr\u003Ee = next;\u003Cbr\u003E}\u003Cbr\u003Ewhile ( e != null );\u003Cbr\u003E}\u003Cbr\u003E}\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E特别需要注意的是，在重哈希的过程中，原属于一个桶中的Entry对象可能被分到不同的桶，因为HashMap 的容量发生了变化，那么 h&(length - 1) 的值也会发生相应的变化。极端地说，如果重哈希后，原属于一个桶中的Entry对象仍属于同一桶，那么重哈希也就失去了意义。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003EHashMap 的读取实现\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp\u003E相对于HashMap的存储而言，读取就显得比较简单了。因为，HashMap只需通过key的hash值定位到table数组的某个特定的桶，然后查找并返回该key对应的value即可，源码如下：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E* Returns the value to which the specified key is mapped,\u003Cbr\u003E* or {@code null} if this map contains no mapping for the key.\u003Cbr\u003E* <p>More formally, if this map contains a mapping from a key\u003Cbr\u003E* {@code k} to a value {@code v} such that {@code (key==null ? k==null :\u003Cbr\u003E* key.equals(k))}, then this method returns {@code v}; otherwise\u003Cbr\u003E* it returns {@code null}. (There can be at most one such mapping.)\u003Cbr\u003E* <p>A return value of {@code null} does not <i>necessarily<\u002Fi>\u003Cbr\u003E* indicate that the map contains no mapping for the key; it's also\u003Cbr\u003E* possible that the map explicitly maps the key to {@code null}.\u003Cbr\u003E* The {@link #containsKey containsKey} operation may be used to\u003Cbr\u003E* distinguish these two cases.\u003Cbr\u003E* @see #put(Object, Object)\u003Cbr\u003E*\u002F\u003Cbr\u003Epublic V get( Object key )\u003Cbr\u003E{\u003Cbr\u003E\u002F* 若为null，调用getForNullKey方法返回相对应的value *\u002F\u003Cbr\u003Eif ( key == null )\u003Cbr\u003E\u002F* 从table的第一个桶中寻找 key 为 null 的映射；若不存在，直接返回null *\u002F\u003Cbr\u003Ereturn(getForNullKey() );\u003Cbr\u003E\u002F* 根据该 key 的 hashCode 值计算它的 hash 码 *\u002F\u003Cbr\u003Eint hash = hash( key.hashCode() );\u003Cbr\u003E\u002F* 找出 table 数组中对应的桶 *\u002F\u003Cbr\u003Efor ( Entry<K, V> e = table[indexFor( hash, table.length )];\u003Cbr\u003Ee != null;\u003Cbr\u003Ee = e.next )\u003Cbr\u003E{\u003Cbr\u003EObject k;\u003Cbr\u003E\u002F* 若搜索的key与查找的key相同，则返回相对应的value *\u002F\u003Cbr\u003Eif ( e.hash == hash && ( (k = e.key) == key || key.equals( k ) ) )\u003Cbr\u003Ereturn(e.value);\u003Cbr\u003E}\u003Cbr\u003Ereturn(null);\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E针对键为NULL的键值对，HashMap 提供了专门的处理：getForNullKey()，\u003C\u002Fstrong\u003E其源码如下：\u003C\u002Fp\u003E\u003Cpre\u003E\u002F**\u003Cbr\u003E *\u003Cbr\u003E * Offloaded version of get() to look up null keys. Null keys map\u003Cbr\u003E *\u003Cbr\u003E * to index 0\\. This null case is split out into separate methods\u003Cbr\u003E *\u003Cbr\u003E * for the sake of performance in the two most commonly used\u003Cbr\u003E *\u003Cbr\u003E * operations (get and put), but incorporated with conditionals in\u003Cbr\u003E *\u003Cbr\u003E * others.\u003Cbr\u003E *\u003Cbr\u003E *\u002F\u003Cbr\u003Eprivate V getForNullKey()\u003Cbr\u003E{\u003Cbr\u003E \u002F* 键为NULL的键值对若存在，则必定在第一个桶中 *\u002F\u003Cbr\u003E for ( Entry<K, V> e = table[0]; e != null; e = e.next )\u003Cbr\u003E {\u003Cbr\u003E if ( e.key == null )\u003Cbr\u003E return(e.value);\u003Cbr\u003E }\u003Cbr\u003E \u002F* 键为NULL的键值对若不存在，则直接返回 null *\u002F\u003Cbr\u003E return(null);\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E因此，调用HashMap的get(Object key)方法后，若返回值是 NULL，则存在如下两种可能：\u003C\u002Fp\u003E\u003Col\u003E\u003Cli\u003E该 key 对应的值就是 null;\u003C\u002Fli\u003E\u003Cli\u003EHashMap 中不存在该 key。\u003C\u002Fli\u003E\u003C\u002Fol\u003E\u003Cblockquote\u003E\u003Cp\u003E\u003Cstrong\u003E关注转发点赞一气呵成，感谢支持\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003C\u002Fblockquote\u003E\u003C\u002Fdiv\u003E"'.slice(6, -6), groupId: '6713865576982249988