Map 综述(一)：彻头彻尾理解 HashMap

Map 综述（一）：彻头彻尾理解HashMap一. HashMap 概述Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。 HashMap 是 Java Collection Framework 的重要成员，也是 Map 族（如下图所示）中我们最为 常用的一种。简单地说， HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形 式存在，即存储的对象是 Entry （同时包含了 Key 和 Value） 。在 HashMap 中，其会根据 hash算法来计算key-value的存储位置并进行快速存取。特别地，HashMap最多只允许一条 Entry的键为Null（多条会覆盖），但允许多条Entry的值为Null。此外，HashMap是Map的 一个 非同步的实现。iMFrficvl(inEirfaDB(irTttriu*)1EnumtrwbonTgbi强 p同样地， HashSet 也是 Java Collection Framework 的重要成员，是 Set 接口的常用实 现类，但其与 HashMap 有很多相似之处。对于 HashSet 而言，其采用 Hash 算法决定元 素在 Set 中的存储位置，这样可以保证元素的快速存取；对于 HashMap 而言，其将 key-value 当成一个整体（Entry对象）来处理，其也采用同样的Hash算法去决定key-value的存储位 置从而保证键值对的快速存取。虽然 HashMap 和 HashSet 实现的接口规范不同，但是它 们底层的 Hash 存储机制完全相同。实际上， HashSet 本身就是在 HashMap 的基础上实现 的。因此，通过对 HashMap 的数据结构、实现原理、源码实现三个方面了解，我们不但可 以进一步掌握其底层的 Hash 存储机制，也有助于对 HashSet 的了解。必须指出的是，虽然容器号称存储的是 Java 对象，但实际上并不会真正将 Java 对象放入容器中，只是在容器中保留这些对象的引用。也就是说， Java 容器实际上包含的 是引用变量，而这些引用变量指向了我们要实际保存的 Java 对象。. HashMap 在 JDK 中的定义HashMap 实现了 Map 接口，并继承 AbstractMap 抽象类，其中 Map 接口定义了 键值映射规则。和 AbstractCollection 抽象类在 Collection 族的作用类似， AbstractMap 抽 象类提供了 Map接口的骨干实现，以最大限度地减少实现Map接口所需的工作。HashMap 在 JDK 中的定义为：public class HashMapextends AbstractMap implements Map, Cloneable, Serializable三. HashMap 的构造函数HashMap 一共提供了四个构造函数，其中 默认无参的构造函数 和 参数为 HashMap 的构造函数 为 Java Collection Framework 规范的推荐实现，其余两个构造函数则 是 HashMap 专门提供的。1、HashMap()该构造函数意在构造一个具有 默认初始容量 (16) 和 默认负载因子(0.75) 的空 HashMap，是Java Collection Framework规范推荐提供的，其源码如下：/* Constructs an empty HashMap with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() /负载因子:用于衡量的是一个散列表的空间的使用程度 this.loadFactor = DEFAULT_LOAD_FACTOR;/HashMap进行扩容的阈值，它的值等于HashMap的容量乘以负载因子 threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);/ HashMap的底层实现仍是数组，只是数组的每一项都是一条链table = new EntryDEFAULT_INITIAL_CAPACITY;init();2、HashMap(int initialCapacity, float loadFactor)该构造函数意在构造一个指定初始容量和指定负载因子的空HashMap，其源码如下：/* Constructs an empty HashMap with the specified initial capacity and load factor. */public HashMap(int initialCapacity, float loadFactor) /初始容量不能小于 0 if (initialCapacity MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;/负载因子不能小于 0 if (loadFactor = 0 | Float.isNaN(loadFactor) throw new IllegalArgumentException(Illegal load factor: + loadFactor);/ HashMap的容量必须是2的幕次方，超过initialCapacity的最小2An int capacity = 1;while (capacity initialCapacity) capacity = 1;/负载因子 this.loadFactor = loadFactor;设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行自动 扩容操作threshold = (int)(capacity * loadFactor);/ HashMap的底层实现仍是数组，只是数组的每一项都是一条链 table = new Entrycapacity;init();3、HashMap(int initialCapacity)该构造函数意在构造一个指定初始容量 和 默认负载因子 (0.75) 的空 HashMap， 其源码如下：/ Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75)public HashMap(int initialCapacity) this(initialCapacity, DEFAULT_LOAD_FACTOR); / 直接调用上述构造函数4、HashMap(Map m)该构造函数意在构造一个与指定Map具有相同映射的HashMap,其初始容量不 小于16 (具体依赖于指定Map的大小)，负载因子是0.75,是Java Collection Framework规 范推荐提供的,其源码如下：/ Constructs a new HashMap with the same mappings as the specified Map./ The HashMap is created with default load factor (0.75) and an initial capacity/ sufficient to hold the mappings in the specified Map.public HashMap(Map m) / 初始容量不小于 16this(Math.max(int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY),DEFAULT_LOAD_FACTOR);putAllForCreate(m);在这里，我们提到了两个非常重要的参数：初始容量 和 负载因子，这两个参数是 影响HashMap性能的重要参数。其中，容量表示哈希表中桶的数量(table数组的大小)， 初始容量是创建哈希表时桶的数量；负载因子是哈希表在其容量自动增加之前可以达到多满 的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程 度越高，反之愈小。对于使用 拉链法(下文会提到)的哈希表来说，查找一个元素的平均时间是O(1+a)， a 指的是链的长度，是一个常数。特别地，若负载因子越大，那么对空间的利用更 充分，但查找效率的也就越低；若负载因子越小，那么哈希表的数据将越稀疏，对空间造成 的浪费也就越严重。系统默认负载因子为 0.75，这是时间和空间成本上一种折衷，一般情 况下我们是无需修改的。四. HashMap 的数据结构1、哈希的相关概念Hash就是把任意长度的输入(又叫做预映射，pre-image)，通过哈希算法，变换成 固定长度的输出(通常是整型)，该输出就是哈希值。这种转换是一种 压缩映射，也就是说， 散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，从而不可能从 散列值来唯一的确定输入值。简单的说，就是一种将任意长度的消息压缩到某一固定长度的 消息摘要函数 。2、哈希的应用：数据结构我们知道，数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困 难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入和删除也 容易的数据结构呢？答案是肯定的，这就是我们要提起的哈希表。事实上，哈希表有多种不 同的实现方法，我们接下来解释的是最经典的一种方法 拉链法，我们可以将其理解为 链表的数组，如下图所示：我们可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结 构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素 分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出 正确的元素。其中，根据元素特征计算元素数组下标的方法就是 哈希算法。总的来说，哈希表适合用作快速查找、删除的基本数据结构，通常需要总数据量可 以放入内存。在使用哈希表时，有以下几个关键点：hash 函数（哈希算法）的选择：针对不同的对象（字符串、整数等）具体的哈希方法；碰撞处理：常用的有两种方式，一种是open hashing,即拉链法；另一种就是closed hashing,即卩开地址法（opened addressing）。3、HashMap 的数据结构我们知道，在Java中最常用的两种结构是数组和链表，几乎所有的数据结构都 可以利用这两种来组合实现， HashMap 就是这种应用的一个典型。实际上， HashMap 就是 一个 链表数组，如下是它数据结构：从上图中，我们可以形象地看出HashMap底层实现还是数组，只是数组的每一项都是 一条链。其中参数 initialCapacity 就代表了该数组的长度，也就是桶的个数。在第三节我们 已经了解了 HashMap 的默认构造函数的源码：/* Constructs an empty HashMap with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() /负载因子:用于衡量的是一个散列表的空间的使用程度 this.loadFactor = DEFAULT_LOAD_FACTOR;/HashMap进行扩容的阈值，它的值等于HashMap的容量乘以负载因子 threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);/ HashMap的底层实现仍是数组，只是数组的每一项都是一条链table = new EntryDEFAULT_INITIAL_CAPACITY;init();从上述源码中我们可以看出，每次新建一个HashMap时，都会初始化一个Entry类型 的 table 数组，其中 Entry 类型的定义如下：static class Entry implements Map.Entry final K key;/ 键值对的键V value;/ 键值对的值Entry next; / 下一个节点final int hash;/ hash(key.hashCode()方法的返回值/* Creates new entry.*/Entry(int h, K k, V v, Entry n) / Entry 的构造函数value = v;next = n; key = k; hash = h;其中，Entry为HashMap的内部类，实现了 Map.Entry接口，其包含了键key、值value、 下一个节点next，以及hash值四个属性。事实上，Entry是构成哈希表的基石，是哈希表所 存储的元素的具体形式。五. HashMap 的快速存取在HashMap中，我们最常用的两个操作就是：put(Key,Value)和get(Key)。我们都 知道， HashMap 中的 Key 是唯一的，那它是如何保证唯一性的呢？我们首先想到的是用 equals 比较，没错，这样可以实现，但随着元素的增多， put 和 get 的效率将越来越低，这 里的时间复杂度是O(n)。也就是说，假如HashMap有1000个元素，那么put时就需要比 较1000次，这是相当耗时的，远达不到HashMap快速存取的目的。实际上，HashMap很 少会用到 equals 方法，因为其内通过一个哈希表管理所有元素，利用哈希算法可以快速的 存取元素。当我们调用 put 方法存值时， HashMap 首先会调用 Key 的 hashCode 方法，然后 基于此获取 Key 哈希码，通过哈希码快速找到某个桶，这个位置可以被称之为 bucketIndex。 通过Java中的=,equals与hashCode的区别与联系所述hashCode的协定可以知道， 如果两个对象的hashCode不同，那么equals 一定为false；否则，如果其hashCode相同， equals也不一定为true。所以，理论上，hashCode可能存在碰撞的情况，当碰撞发生时， 这时会取出bucketIndex桶内已存储的元素,并通过hashCode()和equals()来逐个比较以判 断Key是否已存在。如果已存在，则使用新Value值替换旧Value值，并返回旧Value值； 如果不存在，则存放新的键值对vKey, ValueBJ桶中。因此，在HashMap中，equals()方法 只有在哈希码碰撞时才会被用到。下面我们结合JDK源码看HashMap的存取实现。1、 HashMap 的存储实现在 HashMap 中，键值对的存储是通过 put(key,vlaue) 方法来实现的，其源码如下：/* Associates the specified value with the specified key in this map.* If the map previously contained a mapping for the key, the old* value is replaced.* param key key with which the specified value is to be associated* param value value to be associated with the specified key* return the previous value associated with key, or null if there was no mapping for key.* Note that a null return can also indicate that the map previously associated null with key.*/ public V put(K key, V value) /当 key 为 null 时，调用 putForNullKey 方法，并将该键值对保存到 table 的第 一个位置if (key = null)return putForNullKey(value);/根据 key 的 hashCode 计算 hash 值int hash = hash(key.hashCode(); / (1)/计算该键值对在数组中的存储位置(哪个桶)int i = indexFor(hash, table.length); / (2)在table的第i个桶上进行迭代，寻找key保存的位置for (EntryvK,V e = tablei; e != null; e = e.next) /(3)Object k;判断该条链上是否存在hash值相同且key值相等的映射，若存在，则直 接覆盖 value，并返回旧 lueif (e.hash = hash & (k = e.key) = key | key.equals(k) V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue; / 返回旧值modCount+; /修改次数增加 l ，快速失败机制/原 HashMap 中无该映射，将该添加至该链的链头 addEntry(hash, key, value, i);return null;通过上述源码我们可以清楚了解到HashMap保存数据的过程:首先，判断key是否为null,若为null，则直接调用putForNullKey方法；若不为 空，则先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table 数组在该位置处有元素，则查找是否存在相同的key，若存在则覆盖原来key的value，否 则将该元素保存在链头(最先保存的元素放在链尾)。此外，若table在该处没有元素，则直 接保存。这个过程看似比较简单，但其实有很多需要回味的地方，下面我们一一来看。先看源码中的 (3) 处，此处迭代原因就是为了防止存在相同的 key 值。如果发现 两个hash值(key)相同时，HashMap的处理方式是用新value替换旧value，这里并没有处 理key，这正好解释了 HashMap中没有两个相同的key。1) . 对 NULL 键的特别处理: putForNullKey()我们直接看其源码:/* Offloaded version of put for null keys*/private V putForNullKey(V value) /若key=null，则将其放入table的第一个桶，即table0for (Entry e = table0; e != null; e = e.next) if (e.key = null) / 若已经存在 key 为 null 的键，则替换其值，并返回旧值V oldValue = e.value;e.value = value;e.recordAccess(this); return oldValue;modCount+;/ 快速失败addEntry(0, null, value, 0);/ 否则，将其添加到 table0 的桶中return null;通过上述源码我们可以清楚知到，HashMap中可以保存键为NULL的键值对，且该键 值对是唯一的。若再次向其中添加键为NULL的键值对,将覆盖其原值。此外，如果HashMap 中存在键为NULL的键值对，那么一定在第一个桶中。2) . HashMap 中的哈希策略(算法)在上述的 put(key,vlaue) 方法的源码中，我们标出了 HashMap 中的哈希策略(即 (1)、(2)两处)，hash()方法用于对Key的hashCode进行重新计算，而indexFor()方法用于 生成这个Entry对象的插入位置。当计算出来的hash值与hashMap的(length-1)做了&运算后， 会得到位于区间0, length-1 的一个值。特别地，这个值分布的越均匀，HashMap的空间 利用率也就越高，存取效率也就越好。我们首先看(1)处的 hash() 方法，该方法为一个纯粹的数学计算，用于进一步计算 key 的 hash 值，源码如下：/* Applies a supplemental hash function to a given hashCode, which* defends against poor quality hash functions. This is critical* because HashMap uses power-of-two length hash tables, that* otherwise encounter collisions for hashCodes that do not differ* in er bits.* Note: Null keys always map to hash 0, thus index 0.*/static int hash(int h) / This function ensures that hashCodes that differ only by/ constant multiples at each bit position have a bounded/ number of collisions (approximately 8 at default load factor).h A= (h 20)人(h 12); return h a (h 7) a (h 4);正如JDK官方对该方法的描述那样，使用hash()方法对一个对象的hashCode进行重新 计算是为了防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是2的 倍数，通过右移可以使低位的数据尽量的不同，从而使hash值的分布尽量均匀。更多关于 该hash(int h)方法的介绍请见HashMap hash方法分析，此不赘述。通过上述hash()方法计算得到Key的hash值后，怎么才能保证元素均匀分布到 table 的每个桶中呢？我们会想到取模，但是由于取模的效率较低， HashMap 是通过调用(2) 处的indexFor()方法处理的，其不但简单而且效率很高，对应源码如下所示：/* Returns index for hash code h.*/static int indexFor(int h, int length) return h & (length-1); / 作用等价于取模运算，但这种方式效率更高我们知道,HashMap的底层数组长度总是2的n次方。当length为2的n次方时,h&(length -1)就相当于对length取模，而且速度比直接取模要快得多，这是HashMap在速度上的一个 优化。至于HashMap的底层数组长度为什么是2的n次方，下一节将给出解释。总而言之，上述的hash()方法和indexFor()方法的作用只有一个：保证元素均匀分 布到 table 的每个桶中以便充分利用空间。3) . HashMap中键值对的添加：addEntry()我们直接看其源码：/* Adds a new entry with the specified key, value and hash code to* the specified bucket. It is the responsibility of this* method to resize the table if appropriate.* Subclass overrides this to alter the behavior of put method.* 永远都是在链表的表头添加新元素*/void addEntry(int hash, K key, V value, int bucketIndex) /获取 bucketIndex 处的链表Entry e = tablebucketIndex;/将新创建的 Entry 链入 bucketIndex 处的链表的表头 tablebucketIndex = new Entry(hash, key, value, e);若HashMap中元素的个数超过极限值threshold,则容量扩大两倍 if (size+ = threshold)resize(2 * table.length);通过上述源码我们可以清楚地了解到链的产生时机。HashMap总是将新的Entry对象 添加到 bucketIndex 处，若 bucketIndex 处已经有了 Entry 对象，那么新添加的 Entry 对象将 指向原有的Entry对象，并形成一条新的以它为链头的Entry链；但是，若bucketindex处原 先没有Entry对象，那么新添加的Entry对象将指向null，也就生成了一条长度为1的全新 的 Entry 链了。 HashMap 永远都是在链表的表头添加新元素。此外，若 HashMap 中元素的 个数超过极限值threshold，其将进行扩容操作，一般情况下，容量将扩大至原来的两倍。4) . HashMap 的扩容： resize()随着 HashMap 中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子 链长度就会越来越长，这样势必会影响HashMap的存取速度。为了保证HashMap的效率， 系统必须要在某个临界点进行扩容处理，该临界点就是 HashMap 中元素的数量在数值上等 于 threshold(table 数组长度*加载因子)。但是，不得不说，扩容是一个非常耗时的过程， 因为它需要重新计算这些元素在新 table 数组中的位置并进行复制处理。所以，如果我们能 够提前预知HashMap中元素的个数，那么在构造HashMap时预设元素的个数能够有效的提 高 HashMap 的性能。我们直接看其源码：* Rehashes the contents of this map into a new array with a* larger capacity. This method is called automatically when the* number of keys in this map reaches its threshold.* If current capacity is MAXIMUM_CAPACITY, this method does not* resize the map, but sets threshold to Integer.MAX_VALUE.* This has the effect of preventing future calls.*/* param newCapacity the new capacity, MUST be a power of two;must be greater than current capacity unless current capacity is MAXIMUM_CAPACITY (in which case value is irrelevant).void resize(int newCapacity) Entry oldTable = table; int oldCapacity = oldTable.length;/ 若 oldCapacity 已 达 到 最 大 值 ， 直 接 将 threshold 设 为 Integer.MAX_VALUEif (oldCapacity = MAXIMUM_CAPACITY) threshold = Integer.MAX_VALUE; return; / 直接返回 / 否则，创建一个更大的数组Entry newTable = new EntrynewCapacity;/将每条 Entry 重新哈希到新的数组中 transfer(newTable);table = newTable;threshold = (int)(newCapacity * loadFactor); / 重新设定 threshold 该方法的作用及触发动机如下：Rehashes the contents of this map into a new array with a larger capacity. This method is called automatically when the number of keys in this map reaches its threshold.5) . HashMap 的重哈希：transfer。重哈希的主要是一个重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程，我们直接看其源码：/* Transfers all entries from current table to newTable.*/ void transfer(Entry newTable) / 将原数组 table 赋给数组 src Entry src = table;int newCapacity = newTable.length;/ 将数组 src 中的每条链重新添加到 newTable 中 for (int j = 0; j src.length; j+) Entry e = srcj; if (e != null) srcj = null; / src 回收/ 将每条链的每个元素依次添加到 newTable 中相应的桶中 do Entry next = e.next;/ e.hash 指的是 hash(key.hashCode()的返回值；/ 计算在 newTable 中的位置，注意原来在同一条子链上的元素 可能被分配到不同的子链int i = indexFor(e.hash, newCapacity)；e.next = newTablei； newTablei = e； e = next； while (e != null)； 特别需要注意的是，在重哈希的过程中，原属于一个桶中的Entry对象可能被分到不同 的桶，因为HashMap的容量发生了变化，那么h&(length - 1)的值也会发生相应的变化。 极端地说，如果重哈希后，原属于一个桶中的Entry对象仍属于同一桶，那么重哈希也就失 去了意义。2、HashMap 的读取实现相对于HashMap的存储而言，读取就显得比较简单了。因为，HashMap只需通过 key的hash值定位到table数组的某个特定的桶，然后查找并返回该key对应的value即可， 源码如下：/* Returns the value to which the specified key is mapped,* or code null if this map contains no mapping for the key.* More formally, if this map contains a mapping from a key* code k to a value code v such that code (key=null ? k=null :* key.equals(k), then this method returns code v; otherwise* it returns code null. (There can be at most one such mapping.)* A return value of code null does not necessarily* indicate that the map contains no mapping for the key; its also* possible that the map explicitly maps the key to code null.* The link #containsKey containsKey operation may be used to* distinguish these two cases.* see #put(Object, Object)*/public V get(Object key) /若为null,调用getForNullKey方法返回相对应的valueif (key = null)/ 从 table 的第一个桶中寻找 key 为 null 的映射；若不存在,直接返回 nullreturn getForNullKey();/ 根据该 key 的 hashCode 值计算它的 hash 码int hash = sh(key.hashCode();/ 找出 table 数组中对应的桶for (Entry e = tableindexFor(hash, table.length);e != null;e = e.next) Object k;/若搜索的 key 与查找的 key 相同,则返回相对应的 valueif (e.hash = hash & (k = e.key) = key | key.equals(k)return e.value;return null;在这里能够根据key快速的取到value，除了和HashMap的数据结构密不可分外，还和 Entry有莫大的关系。在前面就已经提到过,HashMap在存储过程中并没有将key，value分 开来存储，而是当做一个整体 key-value 来处理的，这个整体就是 Entry 对象。特别地，在 Entry对象中，value的地位要比key低一些，相当于是key的附属。其中，针对键为NULL的键值对，HashMap提供了专门的处理：getForNullKey(),其源码如下：/* Offloaded version of get() to look up null keys. Null keys map * to index 0. This null case is split out into separate methods* for the sake of performance in the two most commonly used* operations (get and put), but incorporated with conditionals in* others.*/private V getForNullKey() / 键为 NULL 的键值对若存在，则必定在第一个桶中 for (Entry e = table0; e != null; e = e.next) if (e.key = null)return e.value;/ 键为 NULL 的键值对若不存在，则直接返回 null return null;因此，调用HashMap的get(Object key)方法后，若返回值是NULL,则存在如下两种可能：该 key 对应的值就是 null;HashMap 中不存在该 key。3、HashMap 存取小结在存储的过程中，系统根据key的hash值来定位Entry在table数组中的哪个桶， 并且将其放到对应的链表的链头;在取的过程中，同样根据key的hash值来定位Entry在table 数组中的哪个桶，然后在该桶中查找并返回。六.HashMap的底层数组长度为何总是2的n次方？我们知道，HashMap的底层数组长度总是2的n次方，原因是HashMap在其构造 函数 HashMap(int initialCapacity, float loadFactor) 中作了特别的处理，如下面的代码所示。 当底层数组的 length 为 2 的 n 次方时， h&(length - 1) 就相当于对 length 取模，其效率要比 直接取模高得多，这是 HashMap 在效率上的一个优化。/ HashMap的容量必须是2的幕次方，超过initialCapacity的最小2An int capacity = 1;while (capacity initialCapacity)capacity lC2414& nm = oioo4&140101 t 1110 01004&14oiw mo cue67149111 1U QUOaL41000 & 1110 = 1000891001 & 1110 = 100081014L010 比 1110 = 1010101114L01L ft 11L0 = 10101012iiw & ma noo1213141101 t 1110 110012阳L41110 也 1110 = MWid从上面的图表中我们可以看到，当 length 为15时总共发生了8次碰撞，同时发现空间浪费非常大，因为在1、3、5、7、9、11、13、15这八处没有存放数据。这是因为hash值 在与14(即 1110)进行&运算时，得到的结果最后一位永远都是0，即 0001、 0011、 0101、 0111、 1001、 1011、 1101、 1111位置处是不可能存储数据的。这样，空间的减少会导致碰撞 几率的进一步增加，从而就会导致查询速度慢。而当length为16时，length - 1 = 15,即1111,那么，在进行低位&运算时， 值总是与原来hash值相同，而进行高位运算时，其值等于其低位值。所以，当length=2An时， 不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询 速度也较快。因此，总的来说， HashMap 的底层数组长度总是 2 的 n 次方的原因有两个，即当 length=2An 时：不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀， 空间利用率较高，查询速度也较快；h&(length-1)就相当于对length取模，而且在速度、效率上比直接取模要快得多，即 二者是等价不等效的，这是HashMap在速度和效率上的一个优化。