Java 集合框架分析 - HashMap
zgy61
8年前
<p>本篇文章主要分析一下Java集合框架中的Map部分，HashMap，该源码分析基于JDK1.8，分析工具，AndroidStudio，文章分析不足之处，还请见谅！</p> <h3>一、HashMap简介</h3> <p>基于哈希表的一个Map接口实现，存储的对象是一个键值对对象 (Entry<K,V>) ；值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。</p> <pre> <code class="language-java">Map map = Collections.synchronizedMap(new HashMap());</code></pre> <h3>二、数据结构</h3> <p>Java最基本的数据结构有数组和链表。数组的特点是空间连续（大小固定）、寻址迅速，但是插入和删除时需要移动元素，所以查询快，增加删除慢。链表恰好相反，可动态增加或减少空间以适应新增和删除元素，但查找时只能顺着一个个节点查找，所以增加删除快，查找慢。有没有一种结构综合了数组和链表的优点呢？当然有，那就是哈希表（虽说是综合优点，但实际上查找肯定没有数组快，插入删除没有链表快，一种折中的方式吧），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/f22ab97e958a2981f553b5f0b7f27639.png"></p> <p>HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。</p> <p>图中，左边部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。</p> <h3>三、内部接口Entry</h3> <p>Entry接口是Map定义的一个内部接口</p> <pre> <code class="language-java">interface Entry<K, V> { K getKey(); V getValue(); V setValue(V value); boolean equals(Object o); int hashCode(); public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() { return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getKey().compareTo(c2.getKey()); } public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() { return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getValue().compareTo(c2.getValue()); } public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) { Objects.requireNonNull(cmp); return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey()); } public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) { Objects.requireNonNull(cmp); return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue()); } }</code></pre> <p>对于HashMap，它的内部里面实现一个静态内部类，即为 HashMapEntry<K,V> ，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来HashMapEntry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是HashMapEntry[]，Map里面的内容都保存在HashMapEntry[]里面。</p> <pre> <code class="language-java">/** * The table, resized as necessary. Length MUST Always be a power of two. */ transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;</code></pre> <p>我们可以来简单分析一下这个静态内部类HashMapEntry.java</p> <pre> <code class="language-java">// HashMapEntry.java静态内部类，实现的HashMap线性数组 static class HashMapEntry<K,V> implements Map.Entry<K,V> { //key,value值 final K key; V value; //每个数组里面包含的链表 HashMapEntry<K,V> next; int hash; /** * 构造函数 * 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" */ HashMapEntry(int h, K k, V v, HashMapEntry<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; } /** * 判断两个Entry是否相等 * 若两个Entry的“key”和“value”都相等，则返回true。 * 否则，返回false */ 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(); } /** * 当向HashMap中添加元素时，会调用recordAccess() */ void recordAccess(HashMap<K,V> m) { } /** * 当从HashMap中删除元素时，会调用recordRemoval()。 */ void recordRemoval(HashMap<K,V> m) { } }</code></pre> <p>HashMap其实就是一个HashMapEntry数组，HashMapEntry对象中包含了键和值，其中next也是一个HashMapEntry对象，它就是用来处理hash冲突的，形成一个链表。</p> <p>基本结构我们已经分析了，接下来我们就开始正题，开始分析HashMap的源码实现啦！</p> <h3>四、源码分析</h3> <p>4.1 类申明</p> <pre> <code class="language-java">public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable</code></pre> <p>首先我们来看看HashMap内部申明的一些属性，</p> <pre> <code class="language-java">//属性申明 //默认的初始容量，必须是2的幂次方。 static final int DEFAULT_INITIAL_CAPACITY = 4; //最大容量，默认为2的30次方， static final int MAXIMUM_CAPACITY = 1 << 30; //加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // static final HashMapEntry<?,?>[] EMPTY_TABLE = {}; //数组表，大小可以改变，且大小必须为2的幂 transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE; //当前Map中key-value映射的个数 transient int size; //当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量 int threshold; //加载因子 final float loadFactor = DEFAULT_LOAD_FACTOR; //Hash表结构性修改次数 transient int modCount;</code></pre> <p>对于加载因子loadFactor，我们可以稍作解释：</p> <p>loadFactor加载因子是表示Hsah表中元素的填满的程度.</p> <p>若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）冲突的机会越大,则查找的成本越高.因此,必须在</p> <p>"冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.</p> <p>如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值0.75就好了。</p> <p>以上一些基本属性是在HashMap中申明的，如果不明白什么意思的话，可以等到后面再来看看。我们接着分析下面的代码。</p> <p>4.2 构造函数</p> <p>接着我们来分析分析HashMap的构造函数</p> <pre> <code class="language-java">/** * 设置初始容量大小以及加载因子 * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) { //初始容量大小在[DEFAULT_INITIAL_CAPACITY,MAXIMUM_CAPACITY]之间 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) { initialCapacity = MAXIMUM_CAPACITY; } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) { initialCapacity = DEFAULT_INITIAL_CAPACITY; } if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); threshold = initialCapacity; init(); } /** * 设置初始容量，加载因子为默认的0.75 * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 使用默认的容量大小和加载因子 */ public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * 根据指定的map生成一个新的HashMap,负载因子使用默认值，初始容量大小为Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY) * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); //初始化HashMapEntry数组 inflateTable(threshold); putAllForCreate(m); }</code></pre> <p>通过以上HashMap的四种构造函数我们可以发现，我们可以通过设置初始容量大小和加载因子或者直接通过一个map来构造一个HashMap，其中初始容量大小我们设定为4，它必须是2的幂次方，同时它的范围在4和2的30次方之间。构造函数比较简单，没什么可以分析的，接下来我们着重分析一下HashMap的添加和获取方法，也就是put和get方法。</p> <p>4.3 存储数据put</p> <pre> <code class="language-java">//向map存入一个键值对，如果key已存在，则覆盖 public V put(K key, V value) { //如果HashMapEntry数组为空，则重新初始化一下 if (table == EMPTY_TABLE) { inflateTable(threshold); } //对key为null的键值对调用putForNullKey处理 if (key == null) return putForNullKey(value); //生成hash值 int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); //生成hash值索引 int i = indexFor(hash, table.length); //循环遍历Entry数组,若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出,同时返回旧的value！ for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果找到了相同的key，则覆盖旧的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; //调用HashMapEntry增加这个Entry e.recordAccess(this); return oldValue; } } //修改次数 modCount++; //将key-value添加到table[i]处，也就是在链表的头部插入一个数据<k,v> addEntry(hash, key, value, i); return null; }</code></pre> <p>以上的大概内容就是，先获取key的hash值，然后根据hash值来获取在数组中的位置，判断在table[i]中是否存在这个key，也就是先循环遍历链表，如果找到这个key的值，那么就替换这个key值，然后将value修改进去，如果在链表中找不到这个key的话，那么就在链表的头部插入一个数据。</p> <p>在put方法中，我们来详细分析其中的一些方法。开头有一个判断数组是否为null的操作</p> <pre> <code class="language-java">//如果HashMapEntry数组为空，则重新初始化一下 if (table == EMPTY_TABLE) { inflateTable(threshold); } /** * 初始化这个数组 */ private void inflateTable(int toSize) { // 寻找大于toSize的2的幂次方的最小值 int capacity = roundUpToPowerOf2(toSize); float thresholdFloat = capacity * loadFactor; if (thresholdFloat > MAXIMUM_CAPACITY + 1) { thresholdFloat = MAXIMUM_CAPACITY + 1; } //初始化数组 threshold = (int) thresholdFloat; table = new HashMapEntry[capacity]; }</code></pre> <p>接下来，判断了key是否为null，如果为null的话，则进行 putForNullKey(V value) 操作</p> <pre> <code class="language-java">/** * 插入key为null的值，在数组的第一个位置进行插入操作 */ private V putForNullKey(V value) { //循环遍历数组第一个数组的链表，如果存在null的则进行覆盖更新操作 for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } //修改次数 modCount++; //链表中不存在key为null的值，则在链表的开头插入这个key为null的值 addEntry(0, null, value, 0); return null; }</code></pre> <p>如果key为null的话，hash值为0，对象存储在数组中索引为0的位置。即table[0]，接着我们分析一下addEntry方法，</p> <pre> <code class="language-java">//通过hash值来算出在table中哪个位置，然后进行插入操作 void addEntry(int hash, K key, V value, int bucketIndex) { // if ((size >= threshold) && (null != table[bucketIndex])) { //数组扩容 resize(2 * table.length); //如果key为null的话，那么hash值为0，也就是在数组的第一个位置，即table[0]位置 hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0; //根据hash的值来算出在数组的中位置 bucketIndex = indexFor(hash, table.length); } //数据插入或者更新操作 createEntry(hash, key, value, bucketIndex); }</code></pre> <p>我们通过hash值计算得到了table下表中的值，接着继续分析createEntry方法</p> <pre> <code class="language-java">//数据操作，在链表头部插入一个数组，这就是在一个链表头部插入一个节点的过程。获取table[i]的对象e，将table[i]的对象修改为新增对象，让新增对象的next指向e。 void createEntry(int hash, K key, V value, int bucketIndex) { //保存table[i]的对象为e HashMapEntry<K,V> e = table[bucketIndex]; //然后将table[i]的值修改为新增的对象，并将新增对象的next值设置为原先table[i]的值e,这就相当于在链表头部插入一个数据了。 table[bucketIndex] = new HashMapEntry<>(hash, key, value, e); size++; }</code></pre> <p>分析完了key为null的情况，接着我们分析一下key不等于null的情况。接着，我们通过key来计算出hash的，然后根据hash的值来计算在table数组中的位置 int i = indexFor(hash, table.length);</p> <pre> <code class="language-java">// indexFor返回hash值和table数组长度减1的与运算结果。为什么使用的是length-1？应为这样可以保证结果的最大值是length-1，不会产生数组越界问题。 static int indexFor(int h, int length) { return h & (length-1); }</code></pre> <p>我们找到了在数组table中的位置后，我们就开始遍历当前位置中的链表了，如果存在key则覆盖操作，不存在的话则在链表头部插入一个数据。</p> <p>上面便是一个完整的增加数据的操作，在这里我们进行概括一下中心思想。</p> <p>首先，我们判断我们需要增加数据的key是否为null，如果为null的话，则在数组的第一个位置即table[0]处进行插入或者更新操作（如果在第一个位置处的链表中存在key未null的数据，那么则进行覆盖更新操作，如果不存在的话，则在链表头插入一个数据，就是常见的链表插入操作），接下来就走key不等于null这一步了，我们需要根据key来计算出hash的值，其次，需要根据hash的值来计算在table中的位置，得到了位置之后，我们重复进行在链表中的操作（找到就覆盖更新，没找到就在链表头部插入一个数据），这就是HashMap的put操作。</p> <p>我们一般对哈希表的散列很自然地会想到用hash值对length取模（即除法散列法），Hashtable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是HashMap对Hashtable的一个改进。</p> <p>接下来，我们分析下为什么哈希表的容量一定要是2的整数次幂。首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。</p> <p>分析完了put方法，接下来我们分析一下putAll方法，</p> <pre> <code class="language-java">/** * @param m mappings to be stored in this map * @throws NullPointerException if the specified map is null */ public void putAll(Map<? extends K, ? extends V> m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; if (table == EMPTY_TABLE) { inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold)); } /* */ if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; if (newCapacity > table.length) resize(newCapacity); } //遍历m中的内容，然后调用put方法将元素添加到table数组中 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) put(e.getKey(), e.getValue()); }</code></pre> <p>遍历的时候涉及到了entrySet方法，这个方法定义在Map接口中，HashMap中也有实现。我们在HashMap构造函数有个方法叫putAllForCreate方法，分析一下内容。</p> <pre> <code class="language-java">private void putAllForCreate(Map<? extends K, ? extends V> m) { for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) putForCreate(e.getKey(), e.getValue()); }</code></pre> <p>看这个方法名就知道大概意思，在HashMap初始化的时候将一个map全部赋值给初始值。代码也是，先遍历一下Map，然后依次添加进去，我们进入putForCreate方法中查看具体源码</p> <pre> <code class="language-java">private void putForCreate(K key, V value) { //获取key的hash值 int hash = null == key ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key); //根据hash值来计算在table中的位置 int i = indexFor(hash, table.length); //循环遍历数组下标为i的链表，如果存在则覆盖更新，也就是上面计算出来的table中的位置 for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value; return; } } //当前数组中的位置链表中不存在，则在链表头部插入一条数据 createEntry(hash, key, value, i); }</code></pre> <p>该方法先计算需要添加的元素的hash值和在table数组中的索引i。接着遍历table[i]的链表，若有元素的key值与传入key值相等，则替换value，结束方法。若不存在key值相同的元素，则调用createEntry创建并添加元素。继续进入createEntry方法中查看源码</p> <pre> <code class="language-java">void createEntry(int hash, K key, V value, int bucketIndex) { HashMapEntry<K,V> e = table[bucketIndex]; table[bucketIndex] = new HashMapEntry<>(hash, key, value, e); size++; }</code></pre> <p>该方法比较简单，就是在链表头部插入一条数据，putAllForCreate方法类似于put方法。至此所有put相关操作都解释完毕了。put之外，另一个常用的操作就是get，下面就来看get方法。</p> <p>4.4 get方法</p> <p>相比较于put方法，get方法还是比较简单的，我们来具体看下实现。</p> <pre> <code class="language-java">public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); }</code></pre> <p>首先判断key是否等于null，等于的话那就从getForNullKey()中获取value，如果不等于的话，通过getEntry获取。我们首先看等于null的情况。</p> <pre> <code class="language-java">private V getForNullKey() { if (size == 0) { return null; } for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }</code></pre> <p>如果当前table的大小为0的话，那么将返回null，如果不为空的话，那么则在数组table[0]中的链表进行循环匹配，寻找key的null的链表节点，如果找到的话，则直接返回value，否则的话返回null，很简单。接着我们分析key不等于null的情况，即进入getEntry方法中分析。</p> <pre> <code class="language-java">final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key); for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }</code></pre> <p>我们已经分析了put方法，所以这里面的代码基本类似，很简单了，首先先获取hash值，然后根据hash值获取在table中的索引table[i]，其次根据这个数组中的位置来循环遍历table[i]中的链表，判断是否存在这个entry如果存在的话则返回value，不存在则返回null。</p> <p>以上便是HashMap中比较重要的两个方法，一个put，一个get，我们已经全部分析完了，接着我们分析一下其余剩下来的方法。</p> <p>4.5 remove方法</p> <p>分析完了put、get方法，接着分析一下remove方法。</p> <pre> <code class="language-java">public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.getValue()); }</code></pre> <p>在remove方法中，调用了一个removeEntryForKey方法，我们接着看看，</p> <pre> <code class="language-java">final Entry<K,V> removeEntryForKey(Object key) { //如果数组为空，直接返回null if (size == 0) { return null; } //获取需要移除的key的hash值 int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key); //获取在数组table[i]中的索引值i int i = indexFor(hash, table.length); 保存当前数组中的第一个链表节点 HashMapEntry<K,V> prev = table[i]; HashMapEntry<K,V> e = prev; while (e != null) { HashMapEntry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } //单链表删除操作 prev = e; e = next; } return e; }</code></pre> <p>上面的这个过程就是先找到table数组中对应的索引，接着就类似于一般的链表的删除操作，而且是单向链表删除节点，很简单。在C语言中就是修改指针，这个例子中就是将要删除节点的前一节点的next指向删除被删除节点的next即可。</p> <p>4.6 其余方法</p> <p>以上分析了HashMap的大部分代码，还有一些比较不重要的方法我们一次性给出解释，就不一一做分析了。</p> <pre> <code class="language-java">/** * 清空map */ public void clear() { modCount++; Arrays.fill(table, null); size = 0; } /** * 判断是否存在指定的value * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified value */ public boolean containsValue(Object value) { if (value == null) return containsNullValue(); HashMapEntry[] tab = table; for (int i = 0; i < tab.length ; i++) for (HashMapEntry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; } /** * 循环遍历数组，判断数组table[i]下面的链表是否存在value等于null的节点 */ private boolean containsNullValue() { HashMapEntry[] tab = table; for (int i = 0; i < tab.length ; i++) for (HashMapEntry e = tab[i] ; e != null ; e = e.next) if (e.value == null) return true; return false; } /** * 针对HashMap的浅复制 * * @return a shallow copy of this map */ public Object clone() { HashMap<K,V> result = null; try { result = (HashMap<K,V>)super.clone(); } catch (CloneNotSupportedException e) { // assert false; } if (result.table != EMPTY_TABLE) { result.inflateTable(Math.min( (int) Math.min( size * Math.min(1 / loadFactor, 4.0f), // we have limits... HashMap.MAXIMUM_CAPACITY), table.length)); } result.entrySet = null; result.modCount = 0; result.size = 0; result.init(); result.putAllForCreate(this); return result; }</code></pre> <p>以上便是HashMap大概的源码，其中还涉及到entrySet的概念，这是其他集合框架也涉及到的，所以打算一起说，本篇暂未说明。敬请期待后面的文章。如有错误，恳请指正，谢谢！</p> <h3> </h3> <h3>参考链接</h3> <p><a href="/misc/goto?guid=4959741700350876829" rel="nofollow,noindex">1、http://blog.csdn.net/vking_wang/article/details/14166593</a></p> <p><a href="/misc/goto?guid=4959741700448886514" rel="nofollow,noindex">2、http://www.cnblogs.com/hzmark/archive/2012/12/24/HashMap.html</a></p> <p><a href="/misc/goto?guid=4959741700526695548" rel="nofollow,noindex">3、http://www.cnblogs.com/chenpi/p/5280304.html</a></p> <p><a href="/misc/goto?guid=4959741700613883277" rel="nofollow,noindex">4、http://www.cnblogs.com/ITtangtang/p/3948406.html</a></p> <p> </p> <p>来自：https://juejin.im/entry/58c7ecb3128fe10060498577</p> <p> </p>