HashMap详细介绍(源码解析)和使用示例

柔光的暖阳◎ 2022-05-25 09:49 216阅读 0赞

### **转载出处：[http://www.cnblogs.com/skywang12345/p/3310835.html][http_www.cnblogs.com_skywang12345_p_3310835.html]**    ###

### **第1部分 HashMap介绍** ###

**HashMap简介**

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。  
HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。  
HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

HashMap 的实例有两个参数影响其性能：“**初始容量**” 和 “**加载因子**”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。  
通常，**默认加载因子是 0.75**, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

**HashMap的构造函数**

HashMap共有**4个构造函数**,如下：

![复制代码][copycode.gif]

// 默认构造函数。
    HashMap()
    
    // 指定“容量大小”的构造函数
    HashMap(int capacity)
    
    // 指定“容量大小”和“加载因子”的构造函数
    HashMap(int capacity, float loadFactor)
    
    // 包含“子Map”的构造函数
    HashMap(Map<? extends K, ? extends V> map)

![复制代码][copycode.gif]

**HashMap的API**

![复制代码][copycode.gif]

void                 clear()
    Object               clone()
    boolean              containsKey(Object key)
    boolean              containsValue(Object value)
    Set<Entry<K, V>>     entrySet()
    V                    get(Object key)
    boolean              isEmpty()
    Set<K>               keySet()
    V                    put(K key, V value)
    void                 putAll(Map<? extends K, ? extends V> map)
    V                    remove(Object key)
    int                  size()
    Collection<V>        values()

![复制代码][copycode.gif]

### **第2部分 HashMap数据结构** ###

**HashMap的继承关系**

![复制代码][copycode.gif]

java.lang.Object
       ↳     java.util.AbstractMap<K, V>
             ↳     java.util.HashMap<K, V>
    
    public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable { }

![复制代码][copycode.gif]

**HashMap与Map关系如下图**：

[![280024326252470.jpg][]][280024326252470.jpg]

从图中可以看出：   
(01) HashMap继承于AbstractMap类，实现了Map接口。Map是"key-value键值对"接口，AbstractMap实现了"键值对"的通用函数接口。   
(02) HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。  
 　　table是一个Entry\[\]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。   
 　　size是HashMap的大小，它是HashMap保存的键值对的数量。   
 　　threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量\*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。  
 　　loadFactor就是加载因子。   
 　　modCount是用来实现fail-fast机制的。

### **第3部分 HashMap源码解析(基于JDK1.6.0\_45)** ###

为了更了解HashMap的原理，下面对HashMap源码代码作出分析。  
在阅读源码时，**建议参考后面的说明来建立对HashMap的整体认识**，这样更容易理解HashMap。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 package java.util;
      2 import java.io.*;
      3 
      4 public class HashMap<K,V>
      5     extends AbstractMap<K,V>
      6     implements Map<K,V>, Cloneable, Serializable
      7 {
      8 
      9     // 默认的初始容量是16，必须是2的幂。
     10     static final int DEFAULT_INITIAL_CAPACITY = 16;
     11 
     12     // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
     13     static final int MAXIMUM_CAPACITY = 1 << 30;
     14 
     15     // 默认加载因子
     16     static final float DEFAULT_LOAD_FACTOR = 0.75f;
     17 
     18     // 存储数据的Entry数组，长度是2的幂。
     19     // HashMap是采用拉链法实现的，每一个Entry本质上是一个单向链表
     20     transient Entry[] table;
     21 
     22     // HashMap的大小，它是HashMap保存的键值对的数量
     23     transient int size;
     24 
     25     // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
     26     int threshold;
     27 
     28     // 加载因子实际大小
     29     final float loadFactor;
     30 
     31     // HashMap被改变的次数
     32     transient volatile int modCount;
     33 
     34     // 指定“容量大小”和“加载因子”的构造函数
     35     public HashMap(int initialCapacity, float loadFactor) {
     36         if (initialCapacity < 0)
     37             throw new IllegalArgumentException("Illegal initial capacity: " +
     38                                                initialCapacity);
     39         // HashMap的最大容量只能是MAXIMUM_CAPACITY
     40         if (initialCapacity > MAXIMUM_CAPACITY)
     41             initialCapacity = MAXIMUM_CAPACITY;
     42         if (loadFactor <= 0 || Float.isNaN(loadFactor))
     43             throw new IllegalArgumentException("Illegal load factor: " +
     44                                                loadFactor);
     45 
     46         // 找出“大于initialCapacity”的最小的2的幂
     47         int capacity = 1;
     48         while (capacity < initialCapacity)
     49             capacity <<= 1;
     50 
     51         // 设置“加载因子”
     52         this.loadFactor = loadFactor;
     53         // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
     54         threshold = (int)(capacity * loadFactor);
     55         // 创建Entry数组，用来保存数据
     56         table = new Entry[capacity];
     57         init();
     58     }
     59 
     60 
     61     // 指定“容量大小”的构造函数
     62     public HashMap(int initialCapacity) {
     63         this(initialCapacity, DEFAULT_LOAD_FACTOR);
     64     }
     65 
     66     // 默认构造函数。
     67     public HashMap() {
     68         // 设置“加载因子”
     69         this.loadFactor = DEFAULT_LOAD_FACTOR;
     70         // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
     71         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
     72         // 创建Entry数组，用来保存数据
     73         table = new Entry[DEFAULT_INITIAL_CAPACITY];
     74         init();
     75     }
     76 
     77     // 包含“子Map”的构造函数
     78     public HashMap(Map<? extends K, ? extends V> m) {
     79         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
     80                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
     81         // 将m中的全部元素逐个添加到HashMap中
     82         putAllForCreate(m);
     83     }
     84 
     85     static int hash(int h) {
     86         h ^= (h >>> 20) ^ (h >>> 12);
     87         return h ^ (h >>> 7) ^ (h >>> 4);
     88     }
     89 
     90     // 返回索引值
     91     // h & (length-1)保证返回值的小于length
     92     static int indexFor(int h, int length) {
     93         return h & (length-1);
     94     }
     95 
     96     public int size() {
     97         return size;
     98     }
     99 
    100     public boolean isEmpty() {
    101         return size == 0;
    102     }
    103 
    104     // 获取key对应的value
    105     public V get(Object key) {
    106         if (key == null)
    107             return getForNullKey();
    108         // 获取key的hash值
    109         int hash = hash(key.hashCode());
    110         // 在“该hash值对应的链表”上查找“键值等于key”的元素
    111         for (Entry<K,V> e = table[indexFor(hash, table.length)];
    112              e != null;
    113              e = e.next) {
    114             Object k;
    115             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    116                 return e.value;
    117         }
    118         return null;
    119     }
    120 
    121     // 获取“key为null”的元素的值
    122     // HashMap将“key为null”的元素存储在table[0]位置！
    123     private V getForNullKey() {
    124         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
    125             if (e.key == null)
    126                 return e.value;
    127         }
    128         return null;
    129     }
    130 
    131     // HashMap是否包含key
    132     public boolean containsKey(Object key) {
    133         return getEntry(key) != null;
    134     }
    135 
    136     // 返回“键为key”的键值对
    137     final Entry<K,V> getEntry(Object key) {
    138         // 获取哈希值
    139         // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值
    140         int hash = (key == null) ? 0 : hash(key.hashCode());
    141         // 在“该hash值对应的链表”上查找“键值等于key”的元素
    142         for (Entry<K,V> e = table[indexFor(hash, table.length)];
    143              e != null;
    144              e = e.next) {
    145             Object k;
    146             if (e.hash == hash &&
    147                 ((k = e.key) == key || (key != null && key.equals(k))))
    148                 return e;
    149         }
    150         return null;
    151     }
    152 
    153     // 将“key-value”添加到HashMap中
    154     public V put(K key, V value) {
    155         // 若“key为null”，则将该键值对添加到table[0]中。
    156         if (key == null)
    157             return putForNullKey(value);
    158         // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
    159         int hash = hash(key.hashCode());
    160         int i = indexFor(hash, table.length);
    161         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    162             Object k;
    163             // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
    164             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    165                 V oldValue = e.value;
    166                 e.value = value;
    167                 e.recordAccess(this);
    168                 return oldValue;
    169             }
    170         }
    171 
    172         // 若“该key”对应的键值对不存在，则将“key-value”添加到table中
    173         modCount++;
    174         addEntry(hash, key, value, i);
    175         return null;
    176     }
    177 
    178     // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置
    179     private V putForNullKey(V value) {
    180         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
    181             if (e.key == null) {
    182                 V oldValue = e.value;
    183                 e.value = value;
    184                 e.recordAccess(this);
    185                 return oldValue;
    186             }
    187         }
    188         // 这里的完全不会被执行到!
    189         modCount++;
    190         addEntry(0, null, value, 0);
    191         return null;
    192     }
    193 
    194     // 创建HashMap对应的“添加方法”，
    195     // 它和put()不同。putForCreate()是内部方法，它被构造函数等调用，用来创建HashMap
    196     // 而put()是对外提供的往HashMap中添加元素的方法。
    197     private void putForCreate(K key, V value) {
    198         int hash = (key == null) ? 0 : hash(key.hashCode());
    199         int i = indexFor(hash, table.length);
    200 
    201         // 若该HashMap表中存在“键值等于key”的元素，则替换该元素的value值
    202         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    203             Object k;
    204             if (e.hash == hash &&
    205                 ((k = e.key) == key || (key != null && key.equals(k)))) {
    206                 e.value = value;
    207                 return;
    208             }
    209         }
    210 
    211         // 若该HashMap表中不存在“键值等于key”的元素，则将该key-value添加到HashMap中
    212         createEntry(hash, key, value, i);
    213     }
    214 
    215     // 将“m”中的全部元素都添加到HashMap中。
    216     // 该方法被内部的构造HashMap的方法所调用。
    217     private void putAllForCreate(Map<? extends K, ? extends V> m) {
    218         // 利用迭代器将元素逐个添加到HashMap中
    219         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
    220             Map.Entry<? extends K, ? extends V> e = i.next();
    221             putForCreate(e.getKey(), e.getValue());
    222         }
    223     }
    224 
    225     // 重新调整HashMap的大小，newCapacity是调整后的单位
    226     void resize(int newCapacity) {
    227         Entry[] oldTable = table;
    228         int oldCapacity = oldTable.length;
    229         if (oldCapacity == MAXIMUM_CAPACITY) {
    230             threshold = Integer.MAX_VALUE;
    231             return;
    232         }
    233 
    234         // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中，
    235         // 然后，将“新HashMap”赋值给“旧HashMap”。
    236         Entry[] newTable = new Entry[newCapacity];
    237         transfer(newTable);
    238         table = newTable;
    239         threshold = (int)(newCapacity * loadFactor);
    240     }
    241 
    242     // 将HashMap中的全部元素都添加到newTable中
    243     void transfer(Entry[] newTable) {
    244         Entry[] src = table;
    245         int newCapacity = newTable.length;
    246         for (int j = 0; j < src.length; j++) {
    247             Entry<K,V> e = src[j];
    248             if (e != null) {
    249                 src[j] = null;
    250                 do {
    251                     Entry<K,V> next = e.next;
    252                     int i = indexFor(e.hash, newCapacity);
    253                     e.next = newTable[i];
    254                     newTable[i] = e;
    255                     e = next;
    256                 } while (e != null);
    257             }
    258         }
    259     }
    260 
    261     // 将"m"的全部元素都添加到HashMap中
    262     public void putAll(Map<? extends K, ? extends V> m) {
    263         // 有效性判断
    264         int numKeysToBeAdded = m.size();
    265         if (numKeysToBeAdded == 0)
    266             return;
    267 
    268         // 计算容量是否足够，
    269         // 若“当前实际容量 < 需要的容量”，则将容量x2。
    270         if (numKeysToBeAdded > threshold) {
    271             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
    272             if (targetCapacity > MAXIMUM_CAPACITY)
    273                 targetCapacity = MAXIMUM_CAPACITY;
    274             int newCapacity = table.length;
    275             while (newCapacity < targetCapacity)
    276                 newCapacity <<= 1;
    277             if (newCapacity > table.length)
    278                 resize(newCapacity);
    279         }
    280 
    281         // 通过迭代器，将“m”中的元素逐个添加到HashMap中。
    282         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
    283             Map.Entry<? extends K, ? extends V> e = i.next();
    284             put(e.getKey(), e.getValue());
    285         }
    286     }
    287 
    288     // 删除“键为key”元素
    289     public V remove(Object key) {
    290         Entry<K,V> e = removeEntryForKey(key);
    291         return (e == null ? null : e.value);
    292     }
    293 
    294     // 删除“键为key”的元素
    295     final Entry<K,V> removeEntryForKey(Object key) {
    296         // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算
    297         int hash = (key == null) ? 0 : hash(key.hashCode());
    298         int i = indexFor(hash, table.length);
    299         Entry<K,V> prev = table[i];
    300         Entry<K,V> e = prev;
    301 
    302         // 删除链表中“键为key”的元素
    303         // 本质是“删除单向链表中的节点”
    304         while (e != null) {
    305             Entry<K,V> next = e.next;
    306             Object k;
    307             if (e.hash == hash &&
    308                 ((k = e.key) == key || (key != null && key.equals(k)))) {
    309                 modCount++;
    310                 size--;
    311                 if (prev == e)
    312                     table[i] = next;
    313                 else
    314                     prev.next = next;
    315                 e.recordRemoval(this);
    316                 return e;
    317             }
    318             prev = e;
    319             e = next;
    320         }
    321 
    322         return e;
    323     }
    324 
    325     // 删除“键值对”
    326     final Entry<K,V> removeMapping(Object o) {
    327         if (!(o instanceof Map.Entry))
    328             return null;
    329 
    330         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
    331         Object key = entry.getKey();
    332         int hash = (key == null) ? 0 : hash(key.hashCode());
    333         int i = indexFor(hash, table.length);
    334         Entry<K,V> prev = table[i];
    335         Entry<K,V> e = prev;
    336 
    337         // 删除链表中的“键值对e”
    338         // 本质是“删除单向链表中的节点”
    339         while (e != null) {
    340             Entry<K,V> next = e.next;
    341             if (e.hash == hash && e.equals(entry)) {
    342                 modCount++;
    343                 size--;
    344                 if (prev == e)
    345                     table[i] = next;
    346                 else
    347                     prev.next = next;
    348                 e.recordRemoval(this);
    349                 return e;
    350             }
    351             prev = e;
    352             e = next;
    353         }
    354 
    355         return e;
    356     }
    357 
    358     // 清空HashMap，将所有的元素设为null
    359     public void clear() {
    360         modCount++;
    361         Entry[] tab = table;
    362         for (int i = 0; i < tab.length; i++)
    363             tab[i] = null;
    364         size = 0;
    365     }
    366 
    367     // 是否包含“值为value”的元素
    368     public boolean containsValue(Object value) {
    369     // 若“value为null”，则调用containsNullValue()查找
    370     if (value == null)
    371             return containsNullValue();
    372 
    373     // 若“value不为null”，则查找HashMap中是否有值为value的节点。
    374     Entry[] tab = table;
    375         for (int i = 0; i < tab.length ; i++)
    376             for (Entry e = tab[i] ; e != null ; e = e.next)
    377                 if (value.equals(e.value))
    378                     return true;
    379     return false;
    380     }
    381 
    382     // 是否包含null值
    383     private boolean containsNullValue() {
    384     Entry[] tab = table;
    385         for (int i = 0; i < tab.length ; i++)
    386             for (Entry e = tab[i] ; e != null ; e = e.next)
    387                 if (e.value == null)
    388                     return true;
    389     return false;
    390     }
    391 
    392     // 克隆一个HashMap，并返回Object对象
    393     public Object clone() {
    394         HashMap<K,V> result = null;
    395         try {
    396             result = (HashMap<K,V>)super.clone();
    397         } catch (CloneNotSupportedException e) {
    398             // assert false;
    399         }
    400         result.table = new Entry[table.length];
    401         result.entrySet = null;
    402         result.modCount = 0;
    403         result.size = 0;
    404         result.init();
    405         // 调用putAllForCreate()将全部元素添加到HashMap中
    406         result.putAllForCreate(this);
    407 
    408         return result;
    409     }
    410 
    411     // Entry是单向链表。
    412     // 它是 “HashMap链式存储法”对应的链表。
    413     // 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数
    414     static class Entry<K,V> implements Map.Entry<K,V> {
    415         final K key;
    416         V value;
    417         // 指向下一个节点
    418         Entry<K,V> next;
    419         final int hash;
    420 
    421         // 构造函数。
    422         // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
    423         Entry(int h, K k, V v, Entry<K,V> n) {
    424             value = v;
    425             next = n;
    426             key = k;
    427             hash = h;
    428         }
    429 
    430         public final K getKey() {
    431             return key;
    432         }
    433 
    434         public final V getValue() {
    435             return value;
    436         }
    437 
    438         public final V setValue(V newValue) {
    439             V oldValue = value;
    440             value = newValue;
    441             return oldValue;
    442         }
    443 
    444         // 判断两个Entry是否相等
    445         // 若两个Entry的“key”和“value”都相等，则返回true。
    446         // 否则，返回false
    447         public final boolean equals(Object o) {
    448             if (!(o instanceof Map.Entry))
    449                 return false;
    450             Map.Entry e = (Map.Entry)o;
    451             Object k1 = getKey();
    452             Object k2 = e.getKey();
    453             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
    454                 Object v1 = getValue();
    455                 Object v2 = e.getValue();
    456                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
    457                     return true;
    458             }
    459             return false;
    460         }
    461 
    462         // 实现hashCode()
    463         public final int hashCode() {
    464             return (key==null   ? 0 : key.hashCode()) ^
    465                    (value==null ? 0 : value.hashCode());
    466         }
    467 
    468         public final String toString() {
    469             return getKey() + "=" + getValue();
    470         }
    471 
    472         // 当向HashMap中添加元素时，绘调用recordAccess()。
    473         // 这里不做任何处理
    474         void recordAccess(HashMap<K,V> m) {
    475         }
    476 
    477         // 当从HashMap中删除元素时，绘调用recordRemoval()。
    478         // 这里不做任何处理
    479         void recordRemoval(HashMap<K,V> m) {
    480         }
    481     }
    482 
    483     // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
    484     void addEntry(int hash, K key, V value, int bucketIndex) {
    485         // 保存“bucketIndex”位置的值到“e”中
    486         Entry<K,V> e = table[bucketIndex];
    487         // 设置“bucketIndex”位置的元素为“新Entry”，
    488         // 设置“e”为“新Entry的下一个节点”
    489         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    490         // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小
    491         if (size++ >= threshold)
    492             resize(2 * table.length);
    493     }
    494 
    495     // 创建Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
    496     // 它和addEntry的区别是：
    497     // (01) addEntry()一般用在 新增Entry可能导致“HashMap的实际容量”超过“阈值”的情况下。
    498     //   例如，我们新建一个HashMap，然后不断通过put()向HashMap中添加元素；
    499     // put()是通过addEntry()新增Entry的。
    500     //   在这种情况下，我们不知道何时“HashMap的实际容量”会超过“阈值”；
    501     //   因此，需要调用addEntry()
    502     // (02) createEntry() 一般用在 新增Entry不会导致“HashMap的实际容量”超过“阈值”的情况下。
    503     //   例如，我们调用HashMap“带有Map”的构造函数，它绘将Map的全部元素添加到HashMap中；
    504     // 但在添加之前，我们已经计算好“HashMap的容量和阈值”。也就是，可以确定“即使将Map中
    505     // 的全部元素添加到HashMap中，都不会超过HashMap的阈值”。
    506     //   此时，调用createEntry()即可。
    507     void createEntry(int hash, K key, V value, int bucketIndex) {
    508         // 保存“bucketIndex”位置的值到“e”中
    509         Entry<K,V> e = table[bucketIndex];
    510         // 设置“bucketIndex”位置的元素为“新Entry”，
    511         // 设置“e”为“新Entry的下一个节点”
    512         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    513         size++;
    514     }
    515 
    516     // HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。
    517     // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
    518     private abstract class HashIterator<E> implements Iterator<E> {
    519         // 下一个元素
    520         Entry<K,V> next;
    521         // expectedModCount用于实现fast-fail机制。
    522         int expectedModCount;
    523         // 当前索引
    524         int index;
    525         // 当前元素
    526         Entry<K,V> current;
    527 
    528         HashIterator() {
    529             expectedModCount = modCount;
    530             if (size > 0) { // advance to first entry
    531                 Entry[] t = table;
    532                 // 将next指向table中第一个不为null的元素。
    533                 // 这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。
    534                 while (index < t.length && (next = t[index++]) == null)
    535                     ;
    536             }
    537         }
    538 
    539         public final boolean hasNext() {
    540             return next != null;
    541         }
    542 
    543         // 获取下一个元素
    544         final Entry<K,V> nextEntry() {
    545             if (modCount != expectedModCount)
    546                 throw new ConcurrentModificationException();
    547             Entry<K,V> e = next;
    548             if (e == null)
    549                 throw new NoSuchElementException();
    550 
    551             // 注意！！！
    552             // 一个Entry就是一个单向链表
    553             // 若该Entry的下一个节点不为空，就将next指向下一个节点;
    554             // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
    555             if ((next = e.next) == null) {
    556                 Entry[] t = table;
    557                 while (index < t.length && (next = t[index++]) == null)
    558                     ;
    559             }
    560             current = e;
    561             return e;
    562         }
    563 
    564         // 删除当前元素
    565         public void remove() {
    566             if (current == null)
    567                 throw new IllegalStateException();
    568             if (modCount != expectedModCount)
    569                 throw new ConcurrentModificationException();
    570             Object k = current.key;
    571             current = null;
    572             HashMap.this.removeEntryForKey(k);
    573             expectedModCount = modCount;
    574         }
    575 
    576     }
    577 
    578     // value的迭代器
    579     private final class ValueIterator extends HashIterator<V> {
    580         public V next() {
    581             return nextEntry().value;
    582         }
    583     }
    584 
    585     // key的迭代器
    586     private final class KeyIterator extends HashIterator<K> {
    587         public K next() {
    588             return nextEntry().getKey();
    589         }
    590     }
    591 
    592     // Entry的迭代器
    593     private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
    594         public Map.Entry<K,V> next() {
    595             return nextEntry();
    596         }
    597     }
    598 
    599     // 返回一个“key迭代器”
    600     Iterator<K> newKeyIterator()   {
    601         return new KeyIterator();
    602     }
    603     // 返回一个“value迭代器”
    604     Iterator<V> newValueIterator()   {
    605         return new ValueIterator();
    606     }
    607     // 返回一个“entry迭代器”
    608     Iterator<Map.Entry<K,V>> newEntryIterator()   {
    609         return new EntryIterator();
    610     }
    611 
    612     // HashMap的Entry对应的集合
    613     private transient Set<Map.Entry<K,V>> entrySet = null;
    614 
    615     // 返回“key的集合”，实际上返回一个“KeySet对象”
    616     public Set<K> keySet() {
    617         Set<K> ks = keySet;
    618         return (ks != null ? ks : (keySet = new KeySet()));
    619     }
    620 
    621     // Key对应的集合
    622     // KeySet继承于AbstractSet，说明该集合中没有重复的Key。
    623     private final class KeySet extends AbstractSet<K> {
    624         public Iterator<K> iterator() {
    625             return newKeyIterator();
    626         }
    627         public int size() {
    628             return size;
    629         }
    630         public boolean contains(Object o) {
    631             return containsKey(o);
    632         }
    633         public boolean remove(Object o) {
    634             return HashMap.this.removeEntryForKey(o) != null;
    635         }
    636         public void clear() {
    637             HashMap.this.clear();
    638         }
    639     }
    640 
    641     // 返回“value集合”，实际上返回的是一个Values对象
    642     public Collection<V> values() {
    643         Collection<V> vs = values;
    644         return (vs != null ? vs : (values = new Values()));
    645     }
    646 
    647     // “value集合”
    648     // Values继承于AbstractCollection，不同于“KeySet继承于AbstractSet”，
    649     // Values中的元素能够重复。因为不同的key可以指向相同的value。
    650     private final class Values extends AbstractCollection<V> {
    651         public Iterator<V> iterator() {
    652             return newValueIterator();
    653         }
    654         public int size() {
    655             return size;
    656         }
    657         public boolean contains(Object o) {
    658             return containsValue(o);
    659         }
    660         public void clear() {
    661             HashMap.this.clear();
    662         }
    663     }
    664 
    665     // 返回“HashMap的Entry集合”
    666     public Set<Map.Entry<K,V>> entrySet() {
    667         return entrySet0();
    668     }
    669 
    670     // 返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象
    671     private Set<Map.Entry<K,V>> entrySet0() {
    672         Set<Map.Entry<K,V>> es = entrySet;
    673         return es != null ? es : (entrySet = new EntrySet());
    674     }
    675 
    676     // EntrySet对应的集合
    677     // EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。
    678     private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    679         public Iterator<Map.Entry<K,V>> iterator() {
    680             return newEntryIterator();
    681         }
    682         public boolean contains(Object o) {
    683             if (!(o instanceof Map.Entry))
    684                 return false;
    685             Map.Entry<K,V> e = (Map.Entry<K,V>) o;
    686             Entry<K,V> candidate = getEntry(e.getKey());
    687             return candidate != null && candidate.equals(e);
    688         }
    689         public boolean remove(Object o) {
    690             return removeMapping(o) != null;
    691         }
    692         public int size() {
    693             return size;
    694         }
    695         public void clear() {
    696             HashMap.this.clear();
    697         }
    698     }
    699 
    700     // java.io.Serializable的写入函数
    701     // 将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中
    702     private void writeObject(java.io.ObjectOutputStream s)
    703         throws IOException
    704     {
    705         Iterator<Map.Entry<K,V>> i =
    706             (size > 0) ? entrySet0().iterator() : null;
    707 
    708         // Write out the threshold, loadfactor, and any hidden stuff
    709         s.defaultWriteObject();
    710 
    711         // Write out number of buckets
    712         s.writeInt(table.length);
    713 
    714         // Write out size (number of Mappings)
    715         s.writeInt(size);
    716 
    717         // Write out keys and values (alternating)
    718         if (i != null) {
    719             while (i.hasNext()) {
    720             Map.Entry<K,V> e = i.next();
    721             s.writeObject(e.getKey());
    722             s.writeObject(e.getValue());
    723             }
    724         }
    725     }
    726 
    727 
    728     private static final long serialVersionUID = 362498820763181265L;
    729 
    730     // java.io.Serializable的读取函数：根据写入方式读出
    731     // 将HashMap的“总的容量，实际容量，所有的Entry”依次读出
    732     private void readObject(java.io.ObjectInputStream s)
    733          throws IOException, ClassNotFoundException
    734     {
    735         // Read in the threshold, loadfactor, and any hidden stuff
    736         s.defaultReadObject();
    737 
    738         // Read in number of buckets and allocate the bucket array;
    739         int numBuckets = s.readInt();
    740         table = new Entry[numBuckets];
    741 
    742         init();  // Give subclass a chance to do its thing.
    743 
    744         // Read in size (number of Mappings)
    745         int size = s.readInt();
    746 
    747         // Read the keys and values, and put the mappings in the HashMap
    748         for (int i=0; i<size; i++) {
    749             K key = (K) s.readObject();
    750             V value = (V) s.readObject();
    751             putForCreate(key, value);
    752         }
    753     }
    754 
    755     // 返回“HashMap总的容量”
    756     int   capacity()     { return table.length; }
    757     // 返回“HashMap的加载因子”
    758     float loadFactor()   { return loadFactor;   }
    759 }

![复制代码][copycode.gif]

**说明**:

在详细介绍HashMap的代码之前，我们需要了解：**HashMap就是一个散列表，它是通过“拉链法”解决哈希冲突的**。  
还需要再补充说明的一点是影响HashMap性能的有两个参数：**初始容量**(initialCapacity) 和**加载因子**(loadFactor)。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

**第3.1部分 HashMap的“拉链法”相关内容**

**3.1.1 HashMap数据存储数组**

transient Entry[] table;

HashMap中的key-value都是存储在**Entry数组**中的。

**3.1.2 数据节点Entry的数据结构**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 static class Entry<K,V> implements Map.Entry<K,V> {
     2     final K key;
     3     V value;
     4     // 指向下一个节点
     5     Entry<K,V> next;
     6     final int hash;
     7 
     8     // 构造函数。
     9     // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
    10     Entry(int h, K k, V v, Entry<K,V> n) {
    11         value = v;
    12         next = n;
    13         key = k;
    14         hash = h;
    15     }
    16 
    17     public final K getKey() {
    18         return key;
    19     }
    20 
    21     public final V getValue() {
    22         return value;
    23     }
    24 
    25     public final V setValue(V newValue) {
    26         V oldValue = value;
    27         value = newValue;
    28         return oldValue;
    29     }
    30 
    31     // 判断两个Entry是否相等
    32     // 若两个Entry的“key”和“value”都相等，则返回true。
    33     // 否则，返回false
    34     public final boolean equals(Object o) {
    35         if (!(o instanceof Map.Entry))
    36             return false;
    37         Map.Entry e = (Map.Entry)o;
    38         Object k1 = getKey();
    39         Object k2 = e.getKey();
    40         if (k1 == k2 || (k1 != null && k1.equals(k2))) {
    41             Object v1 = getValue();
    42             Object v2 = e.getValue();
    43             if (v1 == v2 || (v1 != null && v1.equals(v2)))
    44                 return true;
    45         }
    46         return false;
    47     }
    48 
    49     // 实现hashCode()
    50     public final int hashCode() {
    51         return (key==null   ? 0 : key.hashCode()) ^
    52                (value==null ? 0 : value.hashCode());
    53     }
    54 
    55     public final String toString() {
    56         return getKey() + "=" + getValue();
    57     }
    58 
    59     // 当向HashMap中添加元素时，绘调用recordAccess()。
    60     // 这里不做任何处理
    61     void recordAccess(HashMap<K,V> m) {
    62     }
    63 
    64     // 当从HashMap中删除元素时，绘调用recordRemoval()。
    65     // 这里不做任何处理
    66     void recordRemoval(HashMap<K,V> m) {
    67     }
    68 }

![复制代码][copycode.gif]

从中，我们可以看出 Entry 实际上就是一个单向链表。这也是为什么我们说HashMap是通过拉链法解决哈希冲突的。  
Entry 实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数。这些都是基本的读取/修改key、value值的函数。

**第3.2部分 HashMap的构造函数**

**HashMap共包括4个构造函数**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 // 默认构造函数。
     2 public HashMap() {
     3     // 设置“加载因子”
     4     this.loadFactor = DEFAULT_LOAD_FACTOR;
     5     // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
     6     threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
     7     // 创建Entry数组，用来保存数据
     8     table = new Entry[DEFAULT_INITIAL_CAPACITY];
     9     init();
    10 }
    11 
    12 // 指定“容量大小”和“加载因子”的构造函数
    13 public HashMap(int initialCapacity, float loadFactor) {
    14     if (initialCapacity < 0)
    15         throw new IllegalArgumentException("Illegal initial capacity: " +
    16                                            initialCapacity);
    17     // HashMap的最大容量只能是MAXIMUM_CAPACITY
    18     if (initialCapacity > MAXIMUM_CAPACITY)
    19         initialCapacity = MAXIMUM_CAPACITY;
    20     if (loadFactor <= 0 || Float.isNaN(loadFactor))
    21         throw new IllegalArgumentException("Illegal load factor: " +
    22                                            loadFactor);
    23 
    24     // Find a power of 2 >= initialCapacity
    25     int capacity = 1;
    26     while (capacity < initialCapacity)
    27         capacity <<= 1;
    28 
    29     // 设置“加载因子”
    30     this.loadFactor = loadFactor;
    31     // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
    32     threshold = (int)(capacity * loadFactor);
    33     // 创建Entry数组，用来保存数据
    34     table = new Entry[capacity];
    35     init();
    36 }
    37 
    38 // 指定“容量大小”的构造函数
    39 public HashMap(int initialCapacity) {
    40     this(initialCapacity, DEFAULT_LOAD_FACTOR);
    41 }
    42 
    43 // 包含“子Map”的构造函数
    44 public HashMap(Map<? extends K, ? extends V> m) {
    45     this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
    46                   DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    47     // 将m中的全部元素逐个添加到HashMap中
    48     putAllForCreate(m);
    49 }

**第3.3部分 HashMap的主要对外接口**

3.3.1 **clear()**

clear() 的作用是**清空HashMap**。它是通过将所有的元素设为null来实现的。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public void clear() {
    2     modCount++;
    3     Entry[] tab = table;
    4     for (int i = 0; i < tab.length; i++)
    5         tab[i] = null;
    6     size = 0;
    7 }

3.3.2 **containsKey()**

containsKey() 的作用是**判断HashMap是否包含key**。

public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }

containsKey() 首先*通过getEntry(key)获取key对应的Entry*，然后*判断该Entry是否为null*。  
getEntry()的源码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 final Entry<K,V> getEntry(Object key) {
     2     // 获取哈希值
     3     // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值
     4     int hash = (key == null) ? 0 : hash(key.hashCode());
     5     // 在“该hash值对应的链表”上查找“键值等于key”的元素
     6     for (Entry<K,V> e = table[indexFor(hash, table.length)];
     7          e != null;
     8          e = e.next) {
     9         Object k;
    10         if (e.hash == hash &&
    11             ((k = e.key) == key || (key != null && key.equals(k))))
    12             return e;
    13     }
    14     return null;
    15 }

getEntry() 的作用就是**返回“键为key”的键值对**，它的实现源码中已经进行了说明。  
这里需要强调的是：**HashMap将“key为null”的元素都放在table的位置0处**，即table\[0\]中；“key不为null”的放在table的其余位置！

3.3.3 **containsValue()**

containsValue() 的作用是**判断HashMap是否包含“值为value”的元素**。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public boolean containsValue(Object value) {
     2     // 若“value为null”，则调用containsNullValue()查找
     3     if (value == null)
     4         return containsNullValue();
     5 
     6     // 若“value不为null”，则查找HashMap中是否有值为value的节点。
     7     Entry[] tab = table;
     8     for (int i = 0; i < tab.length ; i++)
     9         for (Entry e = tab[i] ; e != null ; e = e.next)
    10             if (value.equals(e.value))
    11                 return true;
    12     return false;
    13 }

从中，我们可以看出containsNullValue()分为两步进行处理：第一，若“value为null”，则调用containsNullValue()。第二，若“value不为null”，则查找HashMap中是否有值为value的节点。

containsNullValue() 的作用**判断HashMap中是否包含“值为null”的元素**。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 private boolean containsNullValue() {
    2     Entry[] tab = table;
    3     for (int i = 0; i < tab.length ; i++)
    4         for (Entry e = tab[i] ; e != null ; e = e.next)
    5             if (e.value == null)
    6                 return true;
    7     return false;
    8 }

3.3.4 **entrySet()、values()、keySet()**

它们3个的原理类似，这里以entrySet()为例来说明。  
entrySet()的作用是**返回“HashMap中所有Entry的集合”，它是一个集合。**实现代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 // 返回“HashMap的Entry集合”
     2 public Set<Map.Entry<K,V>> entrySet() {
     3     return entrySet0();
     4 }
     5 
     6 // 返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象
     7 private Set<Map.Entry<K,V>> entrySet0() {
     8     Set<Map.Entry<K,V>> es = entrySet;
     9     return es != null ? es : (entrySet = new EntrySet());
    10 }
    11 
    12 // EntrySet对应的集合
    13 // EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。
    14 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    15     public Iterator<Map.Entry<K,V>> iterator() {
    16         return newEntryIterator();
    17     }
    18     public boolean contains(Object o) {
    19         if (!(o instanceof Map.Entry))
    20             return false;
    21         Map.Entry<K,V> e = (Map.Entry<K,V>) o;
    22         Entry<K,V> candidate = getEntry(e.getKey());
    23         return candidate != null && candidate.equals(e);
    24     }
    25     public boolean remove(Object o) {
    26         return removeMapping(o) != null;
    27     }
    28     public int size() {
    29         return size;
    30     }
    31     public void clear() {
    32         HashMap.this.clear();
    33     }
    34 }

HashMap是通过拉链法实现的散列表。表现在HashMap包括许多的Entry，而每一个Entry本质上又是一个单向链表。那么HashMap遍历key-value键值对的时候，是如何逐个去遍历的呢？

下面我们就看看**HashMap是如何通过entrySet()遍历的。**  
entrySet()实际上是通过newEntryIterator()实现的。 下面我们看看它的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 // 返回一个“entry迭代器”
     2 Iterator<Map.Entry<K,V>> newEntryIterator()   {
     3     return new EntryIterator();
     4 }
     5 
     6 // Entry的迭代器
     7 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
     8     public Map.Entry<K,V> next() {
     9         return nextEntry();
    10     }
    11 }
    12 
    13 // HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。
    14 // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
    15 private abstract class HashIterator<E> implements Iterator<E> {
    16     // 下一个元素
    17     Entry<K,V> next;
    18     // expectedModCount用于实现fast-fail机制。
    19     int expectedModCount;
    20     // 当前索引
    21     int index;
    22     // 当前元素
    23     Entry<K,V> current;
    24 
    25     HashIterator() {
    26         expectedModCount = modCount;
    27         if (size > 0) { // advance to first entry
    28             Entry[] t = table;
    29             // 将next指向table中第一个不为null的元素。
    30             // 这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。
    31             while (index < t.length && (next = t[index++]) == null)
    32                 ;
    33         }
    34     }
    35 
    36     public final boolean hasNext() {
    37         return next != null;
    38     }
    39 
    40     // 获取下一个元素
    41     final Entry<K,V> nextEntry() {
    42         if (modCount != expectedModCount)
    43             throw new ConcurrentModificationException();
    44         Entry<K,V> e = next;
    45         if (e == null)
    46             throw new NoSuchElementException();
    47 
    48         // 注意！！！
    49         // 一个Entry就是一个单向链表
    50         // 若该Entry的下一个节点不为空，就将next指向下一个节点;
    51         // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
    52         if ((next = e.next) == null) {
    53             Entry[] t = table;
    54             while (index < t.length && (next = t[index++]) == null)
    55                 ;
    56         }
    57         current = e;
    58         return e;
    59     }
    60 
    61     // 删除当前元素
    62     public void remove() {
    63         if (current == null)
    64             throw new IllegalStateException();
    65         if (modCount != expectedModCount)
    66             throw new ConcurrentModificationException();
    67         Object k = current.key;
    68         current = null;
    69         HashMap.this.removeEntryForKey(k);
    70         expectedModCount = modCount;
    71     }
    72 
    73 }

当我们通过entrySet()获取到的Iterator的next()方法去遍历HashMap时，实际上调用的是 nextEntry() 。而nextEntry()的实现方式，先遍历Entry(根据Entry在table中的序号，从小到大的遍历)；然后对每个Entry(即每个单向链表)，逐个遍历。

3.3.5 **get()**

get() 的作用是**获取key对应的value**，它的实现代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public V get(Object key) {
     2     if (key == null)
     3         return getForNullKey();
     4     // 获取key的hash值
     5     int hash = hash(key.hashCode());
     6     // 在“该hash值对应的链表”上查找“键值等于key”的元素
     7     for (Entry<K,V> e = table[indexFor(hash, table.length)];
     8          e != null;
     9          e = e.next) {
    10         Object k;
    11         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    12             return e.value;
    13     }
    14     return null;
    15 }

3.3.6 **put()**

put() 的作用是**对外提供接口，让HashMap对象可以通过put()将“key-value”添加到HashMap中**。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public V put(K key, V value) {
     2     // 若“key为null”，则将该键值对添加到table[0]中。
     3     if (key == null)
     4         return putForNullKey(value);
     5     // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
     6     int hash = hash(key.hashCode());
     7     int i = indexFor(hash, table.length);
     8     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
     9         Object k;
    10         // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
    11         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    12             V oldValue = e.value;
    13             e.value = value;
    14             e.recordAccess(this);
    15             return oldValue;
    16         }
    17     }
    18 
    19     // 若“该key”对应的键值对不存在，则将“key-value”添加到table中
    20     modCount++;
    21     addEntry(hash, key, value, i);
    22     return null;
    23 }

若要添加到HashMap中的键值对对应的key已经存在HashMap中，则找到该键值对；然后新的value取代旧的value，并退出！  
若要添加到HashMap中的键值对对应的key不在HashMap中，则将其添加到该哈希值对应的链表中，并调用addEntry()。  
下面看看addEntry()的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 void addEntry(int hash, K key, V value, int bucketIndex) {
     2     // 保存“bucketIndex”位置的值到“e”中
     3     Entry<K,V> e = table[bucketIndex];
     4     // 设置“bucketIndex”位置的元素为“新Entry”，
     5     // 设置“e”为“新Entry的下一个节点”
     6     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
     7     // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小
     8     if (size++ >= threshold)
     9         resize(2 * table.length);
    10 }

addEntry() 的作用是**新增Entry**。将“key-value”插入指定位置，bucketIndex是位置索引。

说到addEntry()，就不得不说另一个函数createEntry()。createEntry()的代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 void createEntry(int hash, K key, V value, int bucketIndex) {
    2     // 保存“bucketIndex”位置的值到“e”中
    3     Entry<K,V> e = table[bucketIndex];
    4     // 设置“bucketIndex”位置的元素为“新Entry”，
    5     // 设置“e”为“新Entry的下一个节点”
    6     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    7     size++;
    8 }

它们的作用都是将key、value添加到HashMap中。而且，比较addEntry()和createEntry()的代码，我们发现addEntry()多了两句：

if (size++ >= threshold)
        resize(2 * table.length);

那它们的区别到底是什么呢？  
阅读代码，我们可以发现，它们的使用情景不同。  
(01) addEntry()一般用在 **新增Entry可能导致“HashMap的实际容量”超过“阈值”**的情况下。  
       例如，我们新建一个HashMap，然后不断通过put()向HashMap中添加元素；put()是通过addEntry()新增Entry的。  
       在这种情况下，我们不知道何时“HashMap的实际容量”会超过“阈值”；  
       因此，需要调用addEntry()  
(02) createEntry() 一般用在 **新增Entry不会导致“HashMap的实际容量”超过“阈值”**的情况下。  
        例如，我们调用HashMap“带有Map”的构造函数，它绘将Map的全部元素添加到HashMap中；  
       但在添加之前，我们已经计算好“HashMap的容量和阈值”。也就是，可以确定“即使将Map中的全部元素添加到HashMap中，都不会超过HashMap的阈值”。  
       此时，调用createEntry()即可。

3.3.7 **putAll()**

putAll() 的作用是**将"m"的全部元素都添加到HashMap中**，它的代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public void putAll(Map<? extends K, ? extends V> m) {
     2     // 有效性判断
     3     int numKeysToBeAdded = m.size();
     4     if (numKeysToBeAdded == 0)
     5         return;
     6 
     7     // 计算容量是否足够，
     8     // 若“当前实际容量 < 需要的容量”，则将容量x2。
     9     if (numKeysToBeAdded > threshold) {
    10         int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
    11         if (targetCapacity > MAXIMUM_CAPACITY)
    12             targetCapacity = MAXIMUM_CAPACITY;
    13         int newCapacity = table.length;
    14         while (newCapacity < targetCapacity)
    15             newCapacity <<= 1;
    16         if (newCapacity > table.length)
    17             resize(newCapacity);
    18     }
    19 
    20     // 通过迭代器，将“m”中的元素逐个添加到HashMap中。
    21     for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
    22         Map.Entry<? extends K, ? extends V> e = i.next();
    23         put(e.getKey(), e.getValue());
    24     }
    25 }

3.3.8 **remove()**

remove() 的作用是**删除“键为key”元素**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public V remove(Object key) {
     2     Entry<K,V> e = removeEntryForKey(key);
     3     return (e == null ? null : e.value);
     4 }
     5 
     6 
     7 // 删除“键为key”的元素
     8 final Entry<K,V> removeEntryForKey(Object key) {
     9     // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算
    10     int hash = (key == null) ? 0 : hash(key.hashCode());
    11     int i = indexFor(hash, table.length);
    12     Entry<K,V> prev = table[i];
    13     Entry<K,V> e = prev;
    14 
    15     // 删除链表中“键为key”的元素
    16     // 本质是“删除单向链表中的节点”
    17     while (e != null) {
    18         Entry<K,V> next = e.next;
    19         Object k;
    20         if (e.hash == hash &&
    21             ((k = e.key) == key || (key != null && key.equals(k)))) {
    22             modCount++;
    23             size--;
    24             if (prev == e)
    25                 table[i] = next;
    26             else
    27                 prev.next = next;
    28             e.recordRemoval(this);
    29             return e;
    30         }
    31         prev = e;
    32         e = next;
    33     }
    34 
    35     return e;
    36 }

**第3.4部分 HashMap实现的Cloneable接口**

HashMap**实现了Cloneable接口，即实现了clone()方法。**  
clone()方法的作用很简单，就是克隆一个HashMap对象并返回。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 // 克隆一个HashMap，并返回Object对象
     2 public Object clone() {
     3     HashMap<K,V> result = null;
     4     try {
     5         result = (HashMap<K,V>)super.clone();
     6     } catch (CloneNotSupportedException e) {
     7         // assert false;
     8     }
     9     result.table = new Entry[table.length];
    10     result.entrySet = null;
    11     result.modCount = 0;
    12     result.size = 0;
    13     result.init();
    14     // 调用putAllForCreate()将全部元素添加到HashMap中
    15     result.putAllForCreate(this);
    16 
    17     return result;
    18 }

**第3.5部分 HashMap实现的Serializable接口**

HashMap实现java.io.Serializable，分别实现了串行读取、写入功能。  
串行写入函数是**writeObject()**，它的作用是**将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中。**  
而串行读取函数是**readObject()**，它的作用是**将HashMap的“总的容量，实际容量，所有的Entry”依次读出**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 // java.io.Serializable的写入函数
     2 // 将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中
     3 private void writeObject(java.io.ObjectOutputStream s)
     4     throws IOException
     5 {
     6     Iterator<Map.Entry<K,V>> i =
     7         (size > 0) ? entrySet0().iterator() : null;
     8 
     9     // Write out the threshold, loadfactor, and any hidden stuff
    10     s.defaultWriteObject();
    11 
    12     // Write out number of buckets
    13     s.writeInt(table.length);
    14 
    15     // Write out size (number of Mappings)
    16     s.writeInt(size);
    17 
    18     // Write out keys and values (alternating)
    19     if (i != null) {
    20         while (i.hasNext()) {
    21         Map.Entry<K,V> e = i.next();
    22         s.writeObject(e.getKey());
    23         s.writeObject(e.getValue());
    24         }
    25     }
    26 }
    27 
    28 // java.io.Serializable的读取函数：根据写入方式读出
    29 // 将HashMap的“总的容量，实际容量，所有的Entry”依次读出
    30 private void readObject(java.io.ObjectInputStream s)
    31      throws IOException, ClassNotFoundException
    32 {
    33     // Read in the threshold, loadfactor, and any hidden stuff
    34     s.defaultReadObject();
    35 
    36     // Read in number of buckets and allocate the bucket array;
    37     int numBuckets = s.readInt();
    38     table = new Entry[numBuckets];
    39 
    40     init();  // Give subclass a chance to do its thing.
    41 
    42     // Read in size (number of Mappings)
    43     int size = s.readInt();
    44 
    45     // Read the keys and values, and put the mappings in the HashMap
    46     for (int i=0; i<size; i++) {
    47         K key = (K) s.readObject();
    48         V value = (V) s.readObject();
    49         putForCreate(key, value);
    50     }
    51 }

### **第4部分 HashMap遍历方式** ###

**4.1 遍历HashMap的键值对**

第一步：**根据entrySet()获取HashMap的“键值对”的Set集合。**  
第二步：**通过Iterator迭代器遍历“第一步”得到的集合。**

![复制代码][copycode.gif]

// 假设map是HashMap对象
    // map中的key是String类型，value是Integer类型
    Integer integ = null;
    Iterator iter = map.entrySet().iterator();
    while(iter.hasNext()) {
        Map.Entry entry = (Map.Entry)iter.next();
        // 获取key
        key = (String)entry.getKey();
            // 获取value
        integ = (Integer)entry.getValue();
    }

![复制代码][copycode.gif]

**4.2 遍历HashMap的键**

第一步：**根据keySet()获取HashMap的“键”的Set集合。**  
第二步：**通过Iterator迭代器遍历“第一步”得到的集合。**

![复制代码][copycode.gif]

// 假设map是HashMap对象
    // map中的key是String类型，value是Integer类型
    String key = null;
    Integer integ = null;
    Iterator iter = map.keySet().iterator();
    while (iter.hasNext()) {
            // 获取key
        key = (String)iter.next();
            // 根据key，获取value
        integ = (Integer)map.get(key);
    }

![复制代码][copycode.gif]

**4.3 遍历HashMap的值**

第一步：**根据value()获取HashMap的“值”的集合。**  
第二步：**通过Iterator迭代器遍历“第一步”得到的集合。**

![复制代码][copycode.gif]

// 假设map是HashMap对象
    // map中的key是String类型，value是Integer类型
    Integer value = null;
    Collection c = map.values();
    Iterator iter= c.iterator();
    while (iter.hasNext()) {
        value = (Integer)iter.next();
    }

![复制代码][copycode.gif]

**遍历测试程序如下**：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 import java.util.Map;
      2 import java.util.Random;
      3 import java.util.Iterator;
      4 import java.util.HashMap;
      5 import java.util.HashSet;
      6 import java.util.Map.Entry;
      7 import java.util.Collection;
      8 
      9 /*
     10  * @desc 遍历HashMap的测试程序。
     11  *   (01) 通过entrySet()去遍历key、value，参考实现函数：
     12  *        iteratorHashMapByEntryset()
     13  *   (02) 通过keySet()去遍历key、value，参考实现函数：
     14  *        iteratorHashMapByKeyset()
     15  *   (03) 通过values()去遍历value，参考实现函数：
     16  *        iteratorHashMapJustValues()
     17  *
     18  * @author skywang
     19  */
     20 public class HashMapIteratorTest {
     21 
     22     public static void main(String[] args) {
     23         int val = 0;
     24         String key = null;
     25         Integer value = null;
     26         Random r = new Random();
     27         HashMap map = new HashMap();
     28 
     29         for (int i=0; i<12; i++) {
     30             // 随机获取一个[0,100)之间的数字
     31             val = r.nextInt(100);
     32             
     33             key = String.valueOf(val);
     34             value = r.nextInt(5);
     35             // 添加到HashMap中
     36             map.put(key, value);
     37             System.out.println(" key:"+key+" value:"+value);
     38         }
     39         // 通过entrySet()遍历HashMap的key-value
     40         iteratorHashMapByEntryset(map) ;
     41         
     42         // 通过keySet()遍历HashMap的key-value
     43         iteratorHashMapByKeyset(map) ;
     44         
     45         // 单单遍历HashMap的value
     46         iteratorHashMapJustValues(map);        
     47     }
     48     
     49     /*
     50      * 通过entry set遍历HashMap
     51      * 效率高!
     52      */
     53     private static void iteratorHashMapByEntryset(HashMap map) {
     54         if (map == null)
     55             return ;
     56 
     57         System.out.println("\niterator HashMap By entryset");
     58         String key = null;
     59         Integer integ = null;
     60         Iterator iter = map.entrySet().iterator();
     61         while(iter.hasNext()) {
     62             Map.Entry entry = (Map.Entry)iter.next();
     63             
     64             key = (String)entry.getKey();
     65             integ = (Integer)entry.getValue();
     66             System.out.println(key+" -- "+integ.intValue());
     67         }
     68     }
     69 
     70     /*
     71      * 通过keyset来遍历HashMap
     72      * 效率低!
     73      */
     74     private static void iteratorHashMapByKeyset(HashMap map) {
     75         if (map == null)
     76             return ;
     77 
     78         System.out.println("\niterator HashMap By keyset");
     79         String key = null;
     80         Integer integ = null;
     81         Iterator iter = map.keySet().iterator();
     82         while (iter.hasNext()) {
     83             key = (String)iter.next();
     84             integ = (Integer)map.get(key);
     85             System.out.println(key+" -- "+integ.intValue());
     86         }
     87     }
     88     
     89 
     90     /*
     91      * 遍历HashMap的values
     92      */
     93     private static void iteratorHashMapJustValues(HashMap map) {
     94         if (map == null)
     95             return ;
     96         
     97         Collection c = map.values();
     98         Iterator iter= c.iterator();
     99         while (iter.hasNext()) {
    100             System.out.println(iter.next());
    101        }
    102     }
    103 }

### **第5部分 HashMap示例** ###

下面通过一个实例学习如何使用HashMap

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 import java.util.Map;
     2 import java.util.Random;
     3 import java.util.Iterator;
     4 import java.util.HashMap;
     5 import java.util.HashSet;
     6 import java.util.Map.Entry;
     7 import java.util.Collection;
     8 
     9 /*
    10  * @desc HashMap测试程序
    11  *        
    12  * @author skywang
    13  */
    14 public class HashMapTest {
    15 
    16     public static void main(String[] args) {
    17         testHashMapAPIs();
    18     }
    19     
    20     private static void testHashMapAPIs() {
    21         // 初始化随机种子
    22         Random r = new Random();
    23         // 新建HashMap
    24         HashMap map = new HashMap();
    25         // 添加操作
    26         map.put("one", r.nextInt(10));
    27         map.put("two", r.nextInt(10));
    28         map.put("three", r.nextInt(10));
    29 
    30         // 打印出map
    31         System.out.println("map:"+map );
    32 
    33         // 通过Iterator遍历key-value
    34         Iterator iter = map.entrySet().iterator();
    35         while(iter.hasNext()) {
    36             Map.Entry entry = (Map.Entry)iter.next();
    37             System.out.println("next : "+ entry.getKey() +" - "+entry.getValue());
    38         }
    39 
    40         // HashMap的键值对个数        
    41         System.out.println("size:"+map.size());
    42 
    43         // containsKey(Object key) :是否包含键key
    44         System.out.println("contains key two : "+map.containsKey("two"));
    45         System.out.println("contains key five : "+map.containsKey("five"));
    46 
    47         // containsValue(Object value) :是否包含值value
    48         System.out.println("contains value 0 : "+map.containsValue(new Integer(0)));
    49 
    50         // remove(Object key) ： 删除键key对应的键值对
    51         map.remove("three");
    52 
    53         System.out.println("map:"+map );
    54 
    55         // clear() ： 清空HashMap
    56         map.clear();
    57 
    58         // isEmpty() : HashMap是否为空
    59         System.out.println((map.isEmpty()?"map is empty":"map is not empty") );
    60     }
    61 }

![复制代码][copycode.gif]

** (某一次)运行结果：**

![复制代码][copycode.gif]

map:{two=7, one=9, three=6}
    next : two - 7
    next : one - 9
    next : three - 6
    size:3
    contains key two : true
    contains key five : false
    contains value 0 : false
    map:{two=7, one=9}
    map is empty

![复制代码][copycode.gif]

[http_www.cnblogs.com_skywang12345_p_3310835.html]: http://www.cnblogs.com/skywang12345/p/3310835.html
[copycode.gif]: /images/20220525/e6027cd11253448988eb331766ab0c7a.png
[280024326252470.jpg]: /images/20220525/f431b1f0820649c9bfc483c629fdcede.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220525/a2d47760e4564dfa9a195f3511befc87.png

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关 HashMap底层实现和原理（源码解析）

Note：文章的内容基于JDK1.7进行分析，1.8做的改动文章末尾进行讲解。大家可以看一下:[https://www.imooc.com/article/267756][

不念不忘少年蓝@/ 2022年12月17日 10:57/ 0 赞/ 142 阅读

相关 HashMap详细介绍(源码解析)和使用示例

转载出处：[http://www.cnblogs.com/skywang12345/p/3310835.html][http_www.cnblogs.com_skywang1

柔光的暖阳◎/ 2022年05月25日 09:49/ 0 赞/ 217 阅读

相关 Java 集合系列05之 LinkedList详细介绍(源码解析)和使用示例

概要前面，我们已经学习了ArrayList，并了解了fail-fast机制。这一章我们接着学习List的实现类——LinkedList。和学习ArrayList

古城微笑少年丶/ 2022年05月22日 02:24/ 0 赞/ 218 阅读

相关 Java 集合系列10之 HashMap详细介绍(源码解析)和使用示例

[http://www.cnblogs.com/skywang12345/p/3310835.html][http_www.cnblogs.com_skywang12345_p

雨点打透心脏的1/2处/ 2022年04月15日 03:56/ 0 赞/ 180 阅读

相关 HashMap源码解析（一）

本文以jdk1.8为例分析HashMap，不考虑和以前版本的比较。 1、成员变量 / The default initial capacity

Love The Way You Lie/ 2022年03月22日 12:54/ 0 赞/ 347 阅读

相关 Java集合系列之「ArrayList」使用示例和详细介绍（源码解析）

前言之前对所有集合进行了一个简单的概括，大致了解到有什么集合，接下来就是，分别对各个集合进行深入的了解。首先讲解List，而List中ArrayList又最为常用。

深碍√TFBOYSˉ_/ 2022年03月18日 05:20/ 0 赞/ 175 阅读

相关 Java 集合系列11之 Hashtable详细介绍(源码解析)和使用示例

第1部分 Hashtable介绍 Hashtable 简介和HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。 Has

叁歲伎倆/ 2022年01月20日 12:43/ 0 赞/ 205 阅读

相关 Java 集合系列07之 Stack详细介绍(源码解析)和使用示例

第1部分 Stack介绍 Stack简介 Stack是栈。它的特性是：先进后出(FILO, First In Last Out)。 java工具包中的Stack是继承于Ve

深碍√TFBOYSˉ_/ 2022年01月20日 12:43/ 0 赞/ 139 阅读

相关 Java 集合系列之 Vector详细介绍(源码解析)和使用示例

第1部分 Vector介绍 Vector简介 Vector 是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList，实现了List, RandomAc

淩亂°似流年/ 2021年09月19日 12:48/ 0 赞/ 240 阅读

相关 Java 集合系列之 Stack详细介绍(源码解析)和使用示例

第1部分 Stack介绍 Stack简介 Stack是栈。它的特性是：先进后出(FILO, First In Last Out)。 java工具包中的Stack是继承

布满荆棘的人生/ 2021年09月19日 12:46/ 0 赞/ 286 阅读