HashMap源码分析（转）

一、 数据结构   Map 将实际数据存储在 Entry 类的数组中。 代码片段：

1. transient Entry[] table;//HashMap 的成员变量，存放数据   
2. static class Entry<K,V> implements Map.Entry<K,V> {// 内部类 Entry  
3. final K key;  
4. V value;
5. Entry<K,V> next; // 指向下一个数据   
6. final int hash;  
7. /** 
8. * Creates new entry. 
9. */  
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. }

执行下面代码后，可能的存储内部结构是 : Map map = new HashMap();

map.put("key1","value1"); map.put("key2","value2"); map.put("key3","value3");  

执行 put 方法时根据 key 的 hash 值来计算放到 table 数组的下标，如果 hash 到相同的下标，则新 put 进去的元素放到 Entry 链的头部，如上图所示。 put 方法的源码后面详细解释。  

  static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量， 1073741824  

  static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认的负载因子，如果没有通过构造方法传入负载因子，则使用 0.75 。   

  transient Entry[] table; // 存放具体键值对的 Entry 数组   

  transient int size; //HashMap 的大小   

  int threshold;// 阀值   threshold = (int)(capacity * loadFactor);  即容量 * 负载因子，执行 put 方法时如果 size 大于 threshold 则进行扩容，后面 put 方法将会看到   

  final float loadFactor; // 用户设置的负载因子   

构造方法一、

1. public HashMap() {  
2. this.loadFactor = DEFAULT_LOAD_FACTOR;  
3. threshold = ( int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);  
4. table =  new Entry[DEFAULT_INITIAL_CAPACITY];  
5. init();
6. }

使用了默认的容量和默认的负载因子。 构造方法二、

1. public HashMap(int initialCapacity) {  
2. this(initialCapacity, DEFAULT_LOAD_FACTOR);  
3. }

使用了用户设置的初始容量和默认的负载因子。 构造方法三、

1. public HashMap(int initialCapacity, float loadFactor) {  
2. if (initialCapacity < 0)  
3. throw new IllegalArgumentException("Illegal initial capacity: " +  
4. initialCapacity);
5. if (initialCapacity > MAXIMUM_CAPACITY)  
6. initialCapacity = MAXIMUM_CAPACITY;
7. if (loadFactor <= 0 || Float.isNaN(loadFactor))  
8. throw new IllegalArgumentException("Illegal load factor: " +  
9. loadFactor);
10. // Find a power of 2 >= initialCapacity  
11. int capacity = 1;  
12. while (capacity < initialCapacity)  
13. capacity <<=  1;  
14. this.loadFactor = loadFactor;  
15. threshold = ( int)(capacity * loadFactor);  
16. table =  new Entry[capacity];  
17. init();
18. }

用户传入了初始容量和负载因子，这两个值是 HashMap 性能优化的关键，涉及到了 HashMap 的扩容问题。 HashMap 的容量永远是 2 的倍数，如果传入的不是 2 的倍数则被调整为大于传入值的最近的 2 的倍数，例如如果传入 130 ，则 capacity 计算后是 256 。是这段代码起的作用：

1. while (capacity < initialCapacity)  
2. capacity <<=  1;  

构造方法四、

1. public HashMap(Map<? extends K, ? extends V> m) {  
2. this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,  
3. DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); // 计算 Map 的大小   
4. putAllForCreate(m); // 初始化   
5. }
6. private void putAllForCreate(Map<? extends K, ? extends V> m) {  
7. for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {// 通过 entryset 进行遍历   
8. Map.Entry<?  extends K, ? extends V> e = i.next();  
9. putForCreate(e.getKey(), e.getValue());
10. }
11. }

根据传入的 map 进行初始化。  

三、关键方法   1 ） put

1. public V put(K key, V value) {  
2. if (key == null)  
3. return putForNullKey(value);// 单独处理，总是放到 table[0] 中   
4. int hash = hash(key.hashCode());// 计算 key 的 hash 值，后面介绍性能的时候再说这个 hash 方法。   
5. int i = indexFor(hash, table.length);// 将 hash 和 length-1 取 & 来得到数组的下表   
6. for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
7. Object k;
8. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
9. V oldValue = e.value;
10. e.value = value;
11. e.recordAccess( this);  
12. return oldValue;  
13. }
14. } // 如果这个 key 值，原来已经则替换后直接返回。   
15. modCount++;
16. addEntry(hash, key, value, i);
17. return null;  
18. }
19. void addEntry(int hash, K key, V value, int bucketIndex) {  
20. Entry<K,V> e = table[bucketIndex];
21. table[bucketIndex] =  new Entry<K,V>(hash, key, value, e);// 如果 table[bucketIndex] 中已经存在 Entry 则放到头部。   
22. if (size++ >= threshold)// 如果大于了阀值，则扩容到原来大小的 2 倍。   
23. resize( 2 * table.length);  
24. }
25. void resize(int newCapacity) {  
26. Entry[] oldTable = table;
27. int oldCapacity = oldTable.length;  
28. if (oldCapacity == MAXIMUM_CAPACITY) {  
29. threshold = Integer.MAX_VALUE;
30. return;  
31. }
32. Entry[] newTable =  new Entry[newCapacity];  
33. transfer(newTable); // 赋值到新的 table 中，注意转移后会重新 hash ，所以位置可能会跟之前不同，目的是均匀分不到新的 table 中。   
34. table = newTable;
35. threshold = ( int)(newCapacity * loadFactor);  
36. }

2 ） get 方法

1. public V get(Object key) {  
2. if (key == null)  
3. return getForNullKey();  
4. int hash = hash(key.hashCode());  
5. for (Entry<K,V> e = table[indexFor(hash, table.length)];// 找到数组的下表，进行遍历   
6. e !=  null;  
7. e = e.next) {
8. Object k;
9. if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
10. return e.value;// 找到则返回   
11. }
12. return null;// 否则，返回 null  
13. }

3)remove 方法

1. public V remove(Object key) {  
2. Entry<K,V> e = removeEntryForKey(key);
3. return (e == null ? null : e.value);  
4. }
5. final Entry<K,V> removeEntryForKey(Object key) {  
6. int hash = (key == null) ? 0 : hash(key.hashCode());  
7. int i = indexFor(hash, table.length);  
8. Entry<K,V> prev = table[i];
9. Entry<K,V> e = prev;
10. while (e != null) {//Entry 链未遍历完则一直遍历   
11. Entry<K,V> next = e.next;
12. Object k;
13. if (e.hash == hash &&  
14. ((k = e.key) == key || (key !=  null && key.equals(k)))) {  
15. modCount++;
16. size--;
17. if (prev == e)// 如果是第一个，则将 table[i] 执行 e.next  
18. table[i] = next;
19. else // 否则将前一个的 next 指向 e.next  
20. prev.next = next;
21. e.recordRemoval( this);  
22. return e;  
23. }
24. prev = e; // 未找到则继续往后遍历   
25. e = next;
26. }
27. return e;  
28. }

4)HashMap 的遍历方法

1. Map map =  new HashMap();  
2. map.put( "key1","value1");  
3. map.put( "key2","value2");  
4. map.put( "key3", "value3");  
5. for(Iterator it = map.entrySet().iterator();it.hasNext();){  
6. Map.Entry e = (Map.Entry)it.next();
7. System.out.println(e.getKey() +  "=" + e.getValue());  
8. }
9. System.out.println( "-----------------------------------------");  
10. for(Iterator it = map.keySet().iterator();it.hasNext();){  
11. Object key = it.next();
12. Object value = map.get(key);
13. System.out.println(key+ "="+value);  
14. }
15. System.out.println( "-----------------------------------------");  
16. System.out.println(map.values());
17. 输出为：
18. key3=value3
19. key2=value2
20. key1=value1
21. -----------------------------------------
22. key3=value3
23. key2=value2
24. key1=value1
25. -----------------------------------------
26. [value3, value2, value1]

四、性能相关   1 ） hash 如果总计算到相同的数组下标，则得进行 Entry 的遍历来取值和存放值，必然会影响性能。 所以 HashMap 提供了 hash 方法，来解决 key 的 hashCode 方法质量不高问题。

1. public V put(K key, V value) {  
2. ...
3. int hash = hash(key.hashCode());  
4. ...
5. }
6. static int hash(int h) {  
7. // This function ensures that hashCodes that differ only by  
8. // constant multiples at each bit position have a bounded  
9. // number of collisions (approximately 8 at default load factor).  
10. h ^= (h >>>  20) ^ (h >>> 12);  
11. return h ^ (h >>> 7) ^ (h >>> 4);  
12. }

2 ）初始容量和负载因子 因为 put 的时候可能需要做扩容，扩容会导致性能损耗，所以如果可以预知 Map 大小的话，可以设置合理的初始大小和负载因子来避免 HashMap 的频繁扩容导致的性能消耗。

1. void addEntry(int hash, K key, V value, int bucketIndex) {  
2. ntry<K,V> e = table[bucketIndex];
3. table[bucketIndex] =  new Entry<K,V>(hash, key, value, e);  
4. if (size++ >= threshold)  
5. resize( 2 * table.length);  
6.   }

五、同 Hashtable 的区别   1 ） HashMap 允许 key 和 value 都可以为 null,Hashtable 都不可以为空。 HashMap 的 put 方法，代码片段：

1. if (key == null)  
2. return putForNullKey(value);  

Hashtable 的 put 方法，代码片段：

1. if (value == null) {  
2. throw new NullPointerException();  
3. }
4. Entry tab[] = table;
5. int hash = key.hashCode();