本文为博主原创文章，转载请注明出处：http://blog.csdn.net/eson_15/article/details/51154989       

        上一章总体分析了Map架构，并简单分析了一下AbstractMap源码，这一章开始我们将对Map的具体实现类进行详细的学习。本章先研究HashMap。依然遵循以下步骤：先对HashMap有个整体的认识，然后学习它的源码，深入剖析HashMap。

1.HashMap简介

        首先看一下HashMap的继承关系

[java]  view plain  copy

 

1. java.lang.Object  
2.    ↳     java.util.AbstractMap<K, V>  
3.          ↳     java.util.HashMap<K, V>  
4.   
5. public class HashMap<K,V>  
6.     extends AbstractMap<K,V>  
7.     implements Map<K,V>, Cloneable, Serializable { }  

[java]  view plain  copy

 

1. Map map = Collections.synchronizedMap(new HashMap());  

[java]  view plain  copy

 

1. void                 clear()  
2. Object               clone()  
3. boolean              containsKey(Object key)  
4. boolean              containsValue(Object value)  
5. Set<Entry<K, V>>     entrySet()  
6. V                    get(Object key)  
7. boolean              isEmpty()  
8. Set<K>               keySet()  
9. V                    put(K key, V value)  
10. void                 putAll(Map<? extends K, ? extends V> map)  
11. V                    remove(Object key)  
12. int                  size()  
13. Collection<V>        values()  

2.HashMap的数据结构

2.1存储结构

        HashMap存储数据的数组定义如下，里面存放的是Entry<K,V>实体：

[java]  view plain  copy

 

1. transient Entry<K,V>[] table  

        图中紫色部分代表哈希表，其实就是哈希数组，数组的每个元素都是一个单链表的头结点，链表是用来解决hash冲突的，如果不同的key映射到了数组的同一位置，那么就将其放入单链表中。下面的图可能在代码的角度更能说明问题：

        下面我们阅读一下数组中存储的Entry实体类源码。

2.2Entry实体

[java]  view plain  copy

 

1. /** 
2.  * Entry其实是个单向链表：它是“HashMap链式存储法”对应的链表。 
3.  * 它实现了Map.Entry接口，也就是实现了getKey()、getValue()、setValue(V value) 
4.  * equals(Object o)和hashCode()这些方法。 
5. **/  
6. static class Entry<K,V> implements Map.Entry<K,V> {  
7.     final K key;  
8.     V value;  
9.     Entry<K,V> next; //指向下一个节点  
10.     int hash;  
11.   
12.     /** 
13.      * 构造方法，创建一个Entry 
14.      * 参数：哈希值h，键值k，值v和下一个节点n 
15.      */  
16.     Entry(int h, K k, V v, Entry<K,V> n) {  
17.         value = v;  
18.         next = n;  
19.         key = k;  
20.         hash = h;  
21.     }  
22.   
23.     public final K getKey() {  
24.         return key;  
25.     }  
26.   
27.     public final V getValue() {  
28.         return value;  
29.     }  
30.   
31.     public final V setValue(V newValue) {  
32.         V oldValue = value;  
33.         value = newValue;  
34.         return oldValue;  
35.     }  
36.   
37.     //判断两个Entry是否相等，必须key和value都相等，才返回true  
38.     public final boolean equals(Object o) {  
39.         if (!(o instanceof Map.Entry))  
40.             return false;  
41.         Map.Entry e = (Map.Entry)o;  
42.         Object k1 = getKey();  
43.         Object k2 = e.getKey();  
44.         if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
45.             Object v1 = getValue();  
46.             Object v2 = e.getValue();  
47.             if (v1 == v2 || (v1 != null && v1.equals(v2)))  
48.                 return true;  
49.         }  
50.         return false;  
51.     }  
52.   
53.     public final int hashCode() { //实现hashCode  
54.         return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());  
55.     }  
56.   
57.     public final String toString() {  
58.         return getKey() + "=" + getValue();  
59.     }  
60.   
61.     /** 
62.      * 当向HashMap中添加元素时，即调用put(k,v)时， 
63.      * 对已经在HashMap中k位置进行v的覆盖时，会调用此方法 
64.      * 这里没做任何处理 
65.      */  
66.     void recordAccess(HashMap<K,V> m) {  
67.     }  
68.   
69.     /** 
70.      * 当从HashMap中删除了一个Entry时，会调用该函数 
71.      * 这里没做任何处理 
72.      */  
73.     void recordRemoval(HashMap<K,V> m) {  
74.     }  
75. }  

3. HashMap源码分析（基于JDK1.7)

        之前分析源码都是将所有源码全部贴上来，然后分析部分放到源码内部，这样看起来有点太多，一下子好几百行源码看的有点懵。这章开始采用分段式分析，将源码分分类，然后各部分突破，这样看起来更加清晰明朗。

3.1成员属性

        先看看HashMap的几个关键属性：

[java]  view plain  copy

 

1. //默认初始容量是16，必须是2的幂  
2. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  
3.   
4. //最大容量（必须是2的幂且小于2的30次方，传入容量过大会被这个值替换）  
5. static final int MAXIMUM_CAPACITY = 1 << 30;  
6.   
7. //默认加载因子，所谓加载因子是指哈希表在其容量自动增加之前可以达到多满的一种尺度  
8. static final float DEFAULT_LOAD_FACTOR = 0.75f;  
9.   
10. //存储Entry的默认空数组  
11. static final Entry<?,?>[] EMPTY_TABLE = {};  
12.   
13. //存储Entry的数组，长度为2的幂。HashMap采用拉链法实现的，每个Entry的本质是个单向链表  
14. transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  
15.   
16. //HashMap的大小，即HashMap存储的键值对数量  
17. transient int size;  
18.   
19. //HashMap的阈值，用于判断是否需要调整HashMap的容量  
20. int threshold;  
21.   
22. //加载因子实际大小  
23. final float loadFactor;  
24.   
25. //HashMap被修改的次数，用于fail-fast机制  
26. transient int modCount;  

        若加载因子设置过大，则填满的元素越多，无疑空间利用率变高了，但是冲突的机会增加了，冲突的越多，链表就会变得越长，那么查找效率就会变得更低；

        若加载因子设置过小，则填满的元素越少，那么空间利用率变低了，表中数据将变得更加稀疏，但是冲突的机会减小了，这样链表就不会太长，查找效率变得更高。

        这看起来有点绕口，我举个简单的例子，如果数组容量为100，加载因子设置为80，即装满了80个才开始扩容，但是在装的过程中，可能有很多key对应相同的hash值，这样就会放到同一个链表中（因为没到80个不能扩容），这样就会导致很多链表都变得很长，也就是说，不同的key对应相同的hash值比数组填满到80个更加容易出现。

        但是如果设置加载因子为10，那么数组填满10个就开始扩容了，10个相对来说是很容易填满的，而且在10个内出现相同的hash值概率比上面的情况要小的多，一旦扩容之后，那么计算hash值又会跟原来不一样，就不会再冲突了，这样保证了链表不会很长，甚至就一个表头都有可能，但是空间利用率很低，因为始终有很多空间没利用就开始扩容。

        因此，就需要在“减小冲突”和“空间利用率”之间寻找一种平衡，这种平衡就是数据结构中有名的“时-空”矛盾的平衡。如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没什么要求的话可以将加载因子设置大一点。一般我们都使用它的默认值，即0.75。

3.2构造方法

      下面看看HashMap的几个构造方法：

[java]  view plain  copy

 

1. /************************** 构造函数 *******************************/  
2.   
3. public HashMap(int initialCapacity, float loadFactor) {//带有初始容量和加载因子  
4.     //确保容量数字合法  
5.     if (initialCapacity < 0)   
6.         throw new IllegalArgumentException("Illegal initial capacity: " +  
7.                                            initialCapacity);  
8.     if (initialCapacity > MAXIMUM_CAPACITY)  
9.         initialCapacity = MAXIMUM_CAPACITY;  
10.     if (loadFactor <= 0 || Float.isNaN(loadFactor))  
11.         throw new IllegalArgumentException("Illegal load factor: " +  
12.                                            loadFactor);  
13.   
14.     this.loadFactor = loadFactor;  
15.         //将阈值设置为初始容量，这里不是真正的阈值，是为了扩展table的，后面这个阈值会重新计算  
16.         threshold = initialCapacity;   
17.     init();//一个空方法用于未来的子对象扩展</span></span>  
18. }  
19.   
20. public HashMap(int initialCapacity) { //带有初始容量，加载因子设为默认值  
21.     this(initialCapacity, DEFAULT_LOAD_FACTOR);  
22. }  
23.   
24. public HashMap() { //初始容量和加载因子均为默认值  
25.     this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);  
26. }  
27.   
28. //构造一个映射关系与指定 Map 相同的新 HashMap  
29. public HashMap(Map<? extends K, ? extends V> m) {  
30.     this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,  
31.                   DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  
32.     inflateTable(threshold);  
33.   
34.     putAllForCreate(m);  
35. }  

3.3存取方法

        存取部分重点分析一下put和get方法，因为这两个方法也是最常用的。其他的存取方法，我放到代码中分析。首先看看HashMap中是如何存储数据的，看put方法：

[java]  view plain  copy

 

1. public V put(K key, V value) {  
2.     if (table == EMPTY_TABLE) { //如果哈希表没有初始化(table为空)  
3.         inflateTable(threshold); //用构造时的阈值(其实就是初始容量)扩展table  
4.     }  
5.     //如果key==null，就将value加到table[0]的位置  
6.     //该位置永远只有一个value，新传进来的value会覆盖旧的value  
7.     if (key == null)   
8.         return putForNullKey(value);  
9.   
10.     int hash = hash(key); //根据键值计算hash值  
11.   
12.     int i = indexFor(hash, table.length); //搜索指定hash在table中的索引  
13.   
14.     //循环遍历Entry数组，若该key对应的键值对已经存在，则用新的value取代旧的value  
15.     for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
16.         Object k;  
17.         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
18.             V oldValue = e.value;  
19.             e.value = value;  
20.             e.recordAccess(this);  
21.             return oldValue; //并返回旧的value  
22.         }  
23.     }  
24.   
25.     modCount++;  
26.     //如果在table[i]中没找到对应的key，那么就直接在该位置的链表中添加此Entry  
27.     addEntry(hash, key, value, i);  
28.     return null;  
29. }  

        首先检测table是不是为空table，如果是空table，说明并没有给table初始化，所以调用inflateTable(threadshold)方法给table初始化。该方法如下：

[java]  view plain  copy

 

1. //扩展table  
2. private void inflateTable(int toSize) {  
3.     // Find a power of 2 >= toSize  
4.     int capacity = roundUpToPowerOf2(toSize); //获取和toSize最接近的2的幂作为容量  
5.     //重新计算阈值 threshold = 容量 * 加载因子  
6.     threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  
7.     table = new Entry[capacity]; //用该容量初始化table  
8.     initHashSeedAsNeeded(capacity);  
9. }  
10. //将初始容量转变成2的幂  
11. private static int roundUpToPowerOf2(int number) {  
12.     // assert number >= 0 : "number must be non-negative";  
13.     return number >= MAXIMUM_CAPACITY  
14.             ? MAXIMUM_CAPACITY //如果容量超过了最大值，设置为最大值  
15.             //否则设置为最接近给定值的2的次幂数  
16.             : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;  
17. }  

        初始化好了table后，就开始往table中存入数据了，table中存的是Entry实体，而put方法传进来的是key和value，所以接下来要做两件事：

        1. 找到table数组中要存入的位置；

        2. 将key和value封装到Entry中存入。

        我们再回到put方法中，先来分析第一步，找存储的位置就要依靠key的值了，因为需要用key的值来计算hash值，根据hash值来决定在table中的位置。首先当key为null时，调用putForNullKey方法，该方法内部实现如下：

[java]  view plain  copy

 

1. //传进key==null的Entry  
2. private V putForNullKey(V value) {  
3.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
4.         if (e.key == null) {   
5.             V oldValue = e.value;  
6.             e.value = value;  
7.             e.recordAccess(this);  
8.             return oldValue;  
9.         }  
10.     }  
11.     modCount++;  
12.     //如果table[0]处没有key为null  
13.     addEntry(0, null, value, 0);//如果键为null的话，则hash值为0  
14.     return null;  
15. }  

[java]  view plain  copy

 

1. //向HashMap中添加Entry  
2. void addEntry(int hash, K key, V value, int bucketIndex) {  
3.     if ((size >= threshold) && (null != table[bucketIndex])) {  
4.         resize(2 * table.length); //扩容2倍  
5.         hash = (null != key) ? hash(key) : 0;  
6.         bucketIndex = indexFor(hash, table.length);  
7.     }  
8.   
9.     createEntry(hash, key, value, bucketIndex);  
10. }  
11. //创建一个Entry  
12. void createEntry(int hash, K key, V value, int bucketIndex) {  
13.     Entry<K,V> e = table[bucketIndex];//先把table中该位置原来的Entry保存  
14.     //在table中该位置新建一个Entry，将原来的Entry挂到该Entry的next  
15.     table[bucketIndex] = new Entry<>(hash, key, value, e);  
16.     //所以table中的每个位置永远只保存一个最新加进来的Entry，其他Entry是一个挂一个，这样挂上去的  
17.     size++;  
18. }  

[java]  view plain  copy

 

1. final int hash(Object k) {  
2.     int h = hashSeed;  
3.     if (0 != h && k instanceof String) {  
4.         return sun.misc.Hashing.stringHash32((String) k);  
5.     }  
6.   
7.     h ^= k.hashCode();  
8.         // 预处理hash值，避免较差的离散hash序列，导致table没有充分利用</span><span>  </span></span>  
9.     h ^= (h >>> 20) ^ (h >>> 12);  
10.     return h ^ (h >>> 7) ^ (h >>> 4);  
11. }  
12. //这个方法有点意思，也是为什么容量要设置为2的幂的原因  
13. static int indexFor(int h, int length) {  
14.     // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";  
15.     return h & (length-1);  
16. }  

        首先，h & (length-1)相当于h & length，但是h % length效率比较低（HashTable中是这儿干的）。为啥h & (length-1)相当于h % length呢？现在假设length为2的幂，那么length就可以表示成100......00的形式（表示至少1个0），那么length-1就是01111....11。对于任意小于length的数h来说，与01111...11做&后都是h本身，对于h=length来说，&后结果为0，对于大于length的数h，&过后相当于h-j*length，也就是h % length。这也就是为啥容量必须为2的幂了，为了优化，好做&运算，效率高。

        其次，length为2的次幂的话，是偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h & (length-1)的最后一位可能为0也可能为1（取决于h的值），即结果可能为奇数，也可能为偶数，这样便可以保证散列的均匀性，即均匀分布在数组table中；而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h & (length-1)的最后一位肯定为0，级只能为偶数，这样任何hash值都会被映射到数组的偶数下标位置上，这便浪费了近一半的空间！因此，length去2的整数次幂，也是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀的散列。

        再回到addEntry方法中，接下来就调用createEntry方法在table数组适当的位置开创一个Entry了，new Entry的时候，将next置为原本在该位置的Entry即可，这样，原来的Entry就挂到现在的Entry上了，以后只要在该位置新new一个Entry，就将原来的挂上去，这样一个挂一个，形成了一个链表。但是table中永远存储的是最新的Entry，并非一个真正的链表数据结构，只是这么多Entry是一个个连在一起的，跟链表很像而已。

        现在往上回到put方法，我们刚刚分析完了key==null的情况，接着往下走，下面其实跟刚刚分析的一样了，先计算hash值，然后找到在table中的位置，然后开始判断是否已经有相同的key的Entry放在那了，如果有，用新的value取代旧的value，如果没有，用传进来的key和value新new一个Entry放到table中，并与原来的Entry挂上。过程跟上面分析的一模一样，唯一不同的就是key!=null。这里就不再赘述了。

        下面再看看HashMap中读取数据的get方法：

[java]  view plain  copy

 

1. public V get(Object key) {  
2.     if (key == null)  
3.         return getForNullKey(); //hey==null时，从table[0]中取  
4.     Entry<K,V> entry = getEntry(key);//key!=null->getEntry  
5.   
6.     return null == entry ? null : entry.getValue();  
7. }  
8.   
9. private V getForNullKey() {  
10.     if (size == 0) {  
11.         return null;  
12.     }  
13.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
14.         if (e.key == null)  
15.             return e.value;//从table[0]中取key==null的value值  
16.     }  
17.     return null;  
18. }  
19.   
20. final Entry<K,V> getEntry(Object key) {  
21.     if (size == 0) {  
22.         return null;  
23.     }  
24.     //取值与上面put中传值相反  
25.     int hash = (key == null) ? 0 : hash(key);  
26.     for (Entry<K,V> e = table[indexFor(hash, table.length)];  
27.          e != null;  
28.          e = e.next) {  
29.         Object k;  
30.         // 如果hash值相等，并且key相等则证明这个Entry里的东西是我们想要的  
31.         if (e.hash == hash &&  
32.             ((k = e.key) == key || (key != null && key.equals(k))))  
33.             return e;  
34.     }  
35.     return null;  
36. }  

        有了对put方法的理解，这段get方法应该就很容易了。从源码中更可以看出，从HashMap中get元素时，先计算key的hashCode，找到数组中国对应的位置，然后通过key的equals在对应位置的链表中找到需要的元素。这里就不再赘述了。

3.4其他方法

        上面我们重点分析了HashMap中的存取方法，当然HashMap中还有其他很多方法，如remove、containsXXX等，以及与迭代器和序列化相关的方法等等。该部分方法的解析全部放在源码里了。源码如下：

[java]  view plain  copy

 

1. //返回当前HashMap的key-value映射数，即Entry数量  
2. public int size() {  
3.     return size;  
4. }  
5.   
6. //判断HashMap是否为空，size==0表示空  
7. public boolean isEmpty() {  
8.     return size == 0;  
9. }  
10.   
11. //判断HashMap中是否包含指定键的映射  
12. public boolean containsKey(Object key) {  
13.     return getEntry(key) != null; //getEntry方法在上面已经拿出来分析了  
14. }  
15.   
16. //看看需不需要创建新的Entry  
17. private void putForCreate(K key, V value) {  
18.     // 如果key为null，则定义hash为0，否则用hash函数预处理    
19.     int hash = null == key ? 0 : hash(key);  
20.     int i = indexFor(hash, table.length);  
21.       
22.     //遍历所有的Entry  
23.     for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
24.         Object k;  
25.         //如果有hash相同，且key相同，那么则不需要创建新的Entry，退出  
26.         if (e.hash == hash &&  
27.             ((k = e.key) == key || (key != null && key.equals(k)))) {  
28.             e.value = value;  
29.             return;  
30.         }  
31.     }  
32.   
33.     createEntry(hash, key, value, i);//否则需要创建新的Entry  
34. }  
35.   
36. //根据已有的Map创建对应的Entry  
37. private void putAllForCreate(Map<? extends K, ? extends V> m) {  
38.     for (Map.Entry<? extends K, ? extends V> e : m.entrySet())  
39.         putForCreate(e.getKey(), e.getValue());  
40. }  
41.   
42. //用新的容量来给table扩容  
43. void resize(int newCapacity) {  
44.     Entry[] oldTable = table; //保存old table  
45.     int oldCapacity = oldTable.length; //保存old capacity  
46.     // 如果旧的容量已经是系统默认最大容量了，那么将阈值设置成整形的最大值，退出    
47.     if (oldCapacity == MAXIMUM_CAPACITY) {  
48.         threshold = Integer.MAX_VALUE;  
49.         return;  
50.     }  
51.   
52.     //根据新的容量新建一个table  
53.     Entry[] newTable = new Entry[newCapacity];  
54.     //将table转换成newTable  
55.     transfer(newTable, initHashSeedAsNeeded(newCapacity));  
56.     table = newTable;  
57.     //设置阈值  
58.     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);  
59. }  
60.   
61. //将所有的Entry移到新的table中  
62. void transfer(Entry[] newTable, boolean rehash) {  
63.     int newCapacity = newTable.length;  
64.     for (Entry<K,V> e : table) {//获得原来table中的所有Entry  
65.         while(null != e) {  
66.             Entry<K,V> next = e.next;  
67.             if (rehash) {  
68.                 e.hash = null == e.key ? 0 : hash(e.key);  
69.             }  
70.             int i = indexFor(e.hash, newCapacity);  
71.             //下面两句跟createEntry方法中原理一样的  
72.             e.next = newTable[i];//设置e.next为newTable[i]保存的Entry  
73.             newTable[i] = e; //将e设置为newTable[i]  
74.             e = next; //设置e为下一个Entry，继续上面while循环  
75.         }  
76.     }  
77. }  
78.   
79. //将指定的Map中所有映射复制到现有的HashMap中,这些映射关系将覆盖当前HashMap中针对指定键相同的映射关系  
80. //有点拗口，其实就是跟put的原理一样，key如果存在，就替换现有key对应的value  
81. public void putAll(Map<? extends K, ? extends V> m) {  
82.     //统计下需要复制多少个映射关系  
83.     int numKeysToBeAdded = m.size();  
84.     if (numKeysToBeAdded == 0)  
85.         return;  
86.     //如果table还没初始化，先用刚刚统计的复制数去初始化table  
87.     if (table == EMPTY_TABLE) {  
88.         inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));  
89.     }  
90.   
91.     //如果要复制的数目比阈值还要大  
92.     if (numKeysToBeAdded > threshold) {  
93.         //需要先resize  
94.         int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);  
95.         if (targetCapacity > MAXIMUM_CAPACITY)  
96.             targetCapacity = MAXIMUM_CAPACITY;  
97.         int newCapacity = table.length;  
98.         while (newCapacity < targetCapacity)  
99.             newCapacity <<= 1;  
100.         if (newCapacity > table.length)  
101.             resize(newCapacity);  
102.     }  
103.     //开始复制  
104.     for (Map.Entry<? extends K, ? extends V> e : m.entrySet())  
105.         put(e.getKey(), e.getValue());//其实就是一个个put进去  
106. }  
107.   
108. //根据指定的key删除Entry，返回对应的value  
109. public V remove(Object key) {  
110.     Entry<K,V> e = removeEntryForKey(key);  
111.     return (e == null ? null : e.value);  
112. }  
113.   
114. //根据指定的key，删除Entry,并返回对应的value  
115. final Entry<K,V> removeEntryForKey(Object key) {  
116.     if (size == 0) {  
117.         return null;  
118.     }  
119.     int hash = (key == null) ? 0 : hash(key);  
120.     int i = indexFor(hash, table.length);  
121.     Entry<K,V> prev = table[i];  
122.     Entry<K,V> e = prev;  
123.   
124.     while (e != null) {  
125.         Entry<K,V> next = e.next;  
126.         Object k;  
127.         if (e.hash == hash &&  
128.             ((k = e.key) == key || (key != null && key.equals(k)))) {  
129.             modCount++;  
130.             size--;  
131.             if (prev == e) //如果删除的是table中的第一项的引用  
132.                 table[i] = next;//直接将第一项中的next的引用存入table[i]中  
133.             else  
134.                 prev.next = next; //否则将table[i]中当前Entry的前一个Entry中的next置为当前Entry的next  
135.             e.recordRemoval(this);  
136.             return e;  
137.         }  
138.         prev = e;  
139.         e = next;  
140.     }  
141.   
142.     return e;  
143. }  
144.   
145. //根据Entry来删除HashMap中的值  
146. final Entry<K,V> removeMapping(Object o) {  
147.     if (size == 0 || !(o instanceof Map.Entry))  
148.         return null;  
149.   
150.     Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  
151.     Object key = entry.getKey();//第一步也是先获得该Entry中保存的key  
152.     int hash = (key == null) ? 0 : hash(key);//接下来就和上面根据key删除Entry道理一样了  
153.     int i = indexFor(hash, table.length);  
154.     Entry<K,V> prev = table[i];  
155.     Entry<K,V> e = prev;  
156.   
157.     while (e != null) {  
158.         Entry<K,V> next = e.next;  
159.         if (e.hash == hash && e.equals(entry)) {  
160.             modCount++;  
161.             size--;  
162.             if (prev == e)  
163.                 table[i] = next;  
164.             else  
165.                 prev.next = next;  
166.             e.recordRemoval(this);  
167.             return e;  
168.         }  
169.         prev = e;  
170.         e = next;  
171.     }  
172.   
173.     return e;  
174. }  
175.   
176. //清空HashMap中所有的Entry  
177. public void clear() {  
178.     modCount++;  
179.     Arrays.fill(table, null);//将table中存储的Entry全部置为null  
180.     size = 0;//size置为0  
181. }  
182.   
183. //判断HashMap中是否有key映射到指定的value  
184. public boolean containsValue(Object value) {  
185.     if (value == null)//如果value为空，调用下面特定的containsNullValue()方法  
186.         return containsNullValue();  
187.   
188.     Entry[] tab = table;//否则遍历链表中的每个Entry  
189.     for (int i = 0; i < tab.length ; i++)  
190.         for (Entry e = tab[i] ; e != null ; e = e.next)  
191.             if (value.equals(e.value))//如果有Entry中的value与指定的value相等  
192.                 return true;//返回true  
193.     return false;  
194. }  
195.   
196. //value为空时调用的方法  
197. private boolean containsNullValue() {  
198.     Entry[] tab = table;  
199.     for (int i = 0; i < tab.length ; i++)  
200.         for (Entry e = tab[i] ; e != null ; e = e.next)  
201.             if (e.value == null)//与上面的不为空时大同小异  
202.                 return true;  
203.     return false;  
204. }  
205.   
206. //克隆HashMap实例，这里是浅复制，并没有复制键和值的本身  
207. public Object clone() {  
208.     HashMap<K,V> result = null;  
209.     try {  
210.         result = (HashMap<K,V>)super.clone();  
211.     } catch (CloneNotSupportedException e) {  
212.         // assert false;  
213.     }  
214.     if (result.table != EMPTY_TABLE) {  
215.         result.inflateTable(Math.min(  
216.             (int) Math.min(  
217.                 size * Math.min(1 / loadFactor, 4.0f),  
218.                 // we have limits...  
219.                 HashMap.MAXIMUM_CAPACITY),  
220.            table.length));  
221.     }  
222.     result.entrySet = null;  
223.     result.modCount = 0;  
224.     result.size = 0;  
225.     result.init();  
226.     result.putAllForCreate(this);  
227.   
228.     return result;  
229. }  
230. /********************** 下面跟Iterator有关了 ************************/  
231. //hashIterator实现了Iterator接口  
232. private abstract class HashIterator<E> implements Iterator<E> {  
233.     Entry<K,V> next;        // 下一个Entry  
234.     int expectedModCount;   // 用于fail-fast机制  
235.     int index;              // 当前索引  
236.     Entry<K,V> current;     //当前的Entry  
237.   
238.     HashIterator() {  
239.         expectedModCount = modCount;//保存modCount用于fail-fast机制  
240.         if (size > 0) { // advance to first entry  
241.             Entry[] t = table;  
242.             while (index < t.length && (next = t[index++]) == null)  
243.                 ;  
244.         }  
245.     }  
246.     //判断有没有下一个Entry  
247.     public final boolean hasNext() {  
248.         return next != null;  
249.     }  
250.     //获得下一个Entry  
251.     final Entry<K,V> nextEntry() {  
252.         if (modCount != expectedModCount)//在迭代的过程中发现被修改了，就会抛出异常  
253.             throw new ConcurrentModificationException();//即fail-fast  
254.         Entry<K,V> e = next;  
255.         if (e == null) //没有就抛出异常  
256.             throw new NoSuchElementException();  
257.   
258.         if ((next = e.next) == null) {  
259.             Entry[] t = table;  
260.             while (index < t.length && (next = t[index++]) == null)  
261.                 ;  
262.         }  
263.         current = e;  
264.         return e;  
265.     }  
266.   
267.     public void remove() {//删除  
268.         if (current == null)  
269.             throw new IllegalStateException();  
270.         if (modCount != expectedModCount)  
271.             throw new ConcurrentModificationException();  
272.         Object k = current.key;  
273.         current = null;  
274.         HashMap.this.removeEntryForKey(k);  
275.         expectedModCount = modCount;  
276.     }  
277. }  
278. //内部class ValueIterator迭代器，它修改了next方法  
279. private final class ValueIterator extends HashIterator<V> {  
280.     public V next() {  
281.         return nextEntry().value;  
282.     }  
283. }  
284. //内部class KeyIterator迭代器，它修改了next方法  
285. private final class KeyIterator extends HashIterator<K> {  
286.     public K next() {  
287.         return nextEntry().getKey();  
288.     }  
289. }  
290. //内部class EntryIterator迭代器，它修改了next方法  
291. private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {  
292.     public Map.Entry<K,V> next() {  
293.         return nextEntry();  
294.     }  
295. }  
296.   
297. //定义上面三个对应的Iterator方法  
298. Iterator<K> newKeyIterator()   {  
299.     return new KeyIterator();  
300. }  
301. Iterator<V> newValueIterator()   {  
302.     return new ValueIterator();  
303. }  
304. Iterator<Map.Entry<K,V>> newEntryIterator()   {  
305.     return new EntryIterator();  
306. }  
307.   
308. private transient Set<Map.Entry<K,V>> entrySet = null;  
309.   
310. /**  
311.  * 返回此映射中所包含的键的 Set 视图。  
312.  * 该 set 受映射的支持，所以对映射的更改将反映在该 set 中，  
313.  * 反之亦然。如果在对 set 进行迭代的同时修改了映射（通过迭代器自己的 remove 操作除外），  
314.  * 则迭代结果是不确定的。该 set 支持元素的移除，通过   
315.  * Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作  
316.  * 可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。  
317.  */   
318. public Set<K> keySet() {  
319.     Set<K> ks = keySet;  
320.     return (ks != null ? ks : (keySet = new KeySet()));  
321. }  
322.   
323. private final class KeySet extends AbstractSet<K> {  
324.     public Iterator<K> iterator() {  
325.         return newKeyIterator();  
326.     }  
327.     public int size() {  
328.         return size;  
329.     }  
330.     public boolean contains(Object o) {  
331.         return containsKey(o);  
332.     }  
333.     public boolean remove(Object o) {  
334.         return HashMap.this.removeEntryForKey(o) != null;  
335.     }  
336.     public void clear() {  
337.         HashMap.this.clear();  
338.     }  
339. }  
340.   
341. /**  
342.  * 返回此映射所包含的值的 Collection 视图。  
343.  * 该 collection 受映射的支持，所以对映射的更改将反映在该 collection 中，  
344.  * 反之亦然。如果在对 collection 进行迭代的同时修改了映射（通过迭代器自己的 remove 操作除外），  
345.  * 则迭代结果是不确定的。该 collection 支持元素的移除，  
346.  * 通过 Iterator.remove、Collection.remove、removeAll、retainAll 和 clear 操作  
347.  * 可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。  
348.  */    
349. public Collection<V> values() {  
350.     Collection<V> vs = values;  
351.     return (vs != null ? vs : (values = new Values()));  
352. }  
353.   
354. private final class Values extends AbstractCollection<V> {  
355.     public Iterator<V> iterator() {  
356.         return newValueIterator();  
357.     }  
358.     public int size() {  
359.         return size;  
360.     }  
361.     public boolean contains(Object o) {  
362.         return containsValue(o);  
363.     }  
364.     public void clear() {  
365.         HashMap.this.clear();  
366.     }  
367. }  
368.   
369. /**  
370.  * 返回此映射所包含的映射关系的 Set 视图。   
371.  * 该 set 受映射支持，所以对映射的更改将反映在此 set 中，  
372.  * 反之亦然。如果在对 set 进行迭代的同时修改了映射  
373.  * （通过迭代器自己的 remove 操作，或者通过在该迭代器返回的映射项上执行 setValue 操作除外），  
374.  * 则迭代结果是不确定的。该 set 支持元素的移除，  
375.  * 通过 Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作  
376.  * 可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。  
377.  */    
378. public Set<Map.Entry<K,V>> entrySet() {  
379.     return entrySet0();  
380. }  
381.   
382. private Set<Map.Entry<K,V>> entrySet0() {  
383.     Set<Map.Entry<K,V>> es = entrySet;  
384.     return es != null ? es : (entrySet = new EntrySet());  
385. }  
386.   
387. private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {  
388.     public Iterator<Map.Entry<K,V>> iterator() {  
389.         return newEntryIterator();  
390.     }  
391.     public boolean contains(Object o) {  
392.         if (!(o instanceof Map.Entry))  
393.             return false;  
394.         Map.Entry<K,V> e = (Map.Entry<K,V>) o;  
395.         Entry<K,V> candidate = getEntry(e.getKey());  
396.         return candidate != null && candidate.equals(e);  
397.     }  
398.     public boolean remove(Object o) {  
399.         return removeMapping(o) != null;  
400.     }  
401.     public int size() {  
402.         return size;  
403.     }  
404.     public void clear() {  
405.         HashMap.this.clear();  
406.     }  
407. }  
408.   
409. /**************************　序列化　*****************************/  
410. private void writeObject(java.io.ObjectOutputStream s)  
411.     throws IOException  
412. {  
413.     // Write out the threshold, loadfactor, and any hidden stuff  
414.     s.defaultWriteObject();  
415.   
416.     //将table.length写入流  
417.     if (table==EMPTY_TABLE) {  
418.         s.writeInt(roundUpToPowerOf2(threshold));  
419.     } else {  
420.        s.writeInt(table.length);  
421.     }  
422.   
423.     //将size写入流  
424.     s.writeInt(size);  
425.   
426.     //这里之所以不直接将table写出，而是分开写里面保存Entry的key和value的原因是：  
427.     //table数组定义为了transient，也就是说在进行序列化时，并不包含该成员。  
428.     //为什么将其设置为transient呢？因为Object.hashCode方法对于一个类的两个实例返回的是不同的哈希值。  
429.     //即我们在机器A上算出对象A的哈希值与索引，然后把它插入到HashMap中，然后把该HashMap序列化后，  
430.     //在机器B上重新算对象的哈希值与索引，这与机器A上算出的是不一样的，  
431.     //所以我们在机器B上get对象A时，会得到错误的结果。  
432.     //所以我们分开序列化key和value  
433.     if (size > 0) {  
434.         for(Map.Entry<K,V> e : entrySet0()) {  
435.             s.writeObject(e.getKey());  
436.             s.writeObject(e.getValue());  
437.         }  
438.     }  
439. }  
440.   
441. private static final long serialVersionUID = 362498820763181265L;  
442.   
443. private void readObject(java.io.ObjectInputStream s)  
444.      throws IOException, ClassNotFoundException  
445. {  
446.     // Read in the threshold (ignored), loadfactor, and any hidden stuff  
447.     s.defaultReadObject();  
448.     if (loadFactor <= 0 || Float.isNaN(loadFactor)) {  
449.         throw new InvalidObjectException("Illegal load factor: " +  
450.                                            loadFactor);  
451.     }  
452.   
453.     // set other fields that need values  
454.     table = (Entry<K,V>[]) EMPTY_TABLE;  
455.   
456.     // Read in number of buckets  
457.     s.readInt(); // ignored.  
458.   
459.     // Read number of mappings  
460.     int mappings = s.readInt();  
461.     if (mappings < 0)  
462.         throw new InvalidObjectException("Illegal mappings count: " +  
463.                                            mappings);  
464.   
465.     // capacity chosen by number of mappings and desired load (if >= 0.25)  
466.     int capacity = (int) Math.min(  
467.                 mappings * Math.min(1 / loadFactor, 4.0f),  
468.                 // we have limits...  
469.                 HashMap.MAXIMUM_CAPACITY);  
470.   
471.     // allocate the bucket array;  
472.     if (mappings > 0) {  
473.         inflateTable(capacity);  
474.     } else {  
475.         threshold = capacity;  
476.     }  
477.   
478.     init();  // Give subclass a chance to do its thing.  
479.   
480.     // Read the keys and values, and put the mappings in the HashMap  
481.     for (int i = 0; i < mappings; i++) {  
482.         K key = (K) s.readObject();  
483.         V value = (V) s.readObject();  
484.         putForCreate(key, value);  
485.     }  
486. }  
487.   
488. // These methods are used when serializing HashSets  
489. int   capacity()     { return table.length; }  
490. float loadFactor()   { return loadFactor;   }  

3.HashMap 遍历方式

    HashMap的遍历方式比较单一，一般分两步走：

        1. 获得Entry或key或value的Set集合；

        2. 通过Iterator迭代器遍历此Set集合。

3.1遍历HashMap的Entry

[java]  view plain  copy

 

1. //假设map是HashMap对象  
2. //map中的key是String类型，value是Integer类型  
3. String key = null;  
4. Integer integ = null;  
5. Iterator iter = map.entrySet().iterator();//获得Entry的Iterator  
6. while(iter.hasNext()) {  
7.     Map.Entry entry = (Map.Entry)iter.next(); //先获取Entry  
8.     //再获取key和value  
9.     key = (String)entry.getKey();  
10.     integ = (Integer)entry.getValue();  
11. }  

3.2遍历HashMap的key

[java]  view plain  copy

 

1. //假设map是HashMap对象  
2. //map中的key是String类型，value是Integer类型  
3. String key = null;  
4. Integer integ = null;  
5. Iterator iter = map.keySet().iterator(); //获得Key的Iterator  
6. while (iter.hasNext()) {  
7.     //直接获取key  
8.     key = (String)iter.next();  
9.     //根据key，调用get方法获取value  
10.     integ = (Integer)map.get(key);  
11. }  

3.3遍历HashMap的value

[java]  view plain  copy

 

1. //假设map是HashMap对象  
2. //map中的key是String类型，value是Integer类型  
3. Integer value = null;  
4. Collection c = map.values();  
5. Iterator iter= c.iterator();//获得value的Iterator  
6. while (iter.hasNext()) {  
7.     value = (Integer)iter.next(); //直接获取  
8. }  

    HashMap的遍历比较简单，主要是通过Iterator迭代器来实现，但是方式有三种，都可以最终获得value值。

    最后给大家分享一个链接：https://www.cs.usfca.edu/~galles/visualization/OpenHash.html 。可以很直观的看到HashMap添加和删除数据的过程。帮助我们更好的理解HashMap。

    HashMap就讨论到这吧，如有错误，欢迎留言指正~

转载：http://blog.csdn.net/eson_15/article/details/51158865