【2】HashMap

 1  public V put(K key, V value) {  
 2         if (key == null)  
 3             return putForNullKey(value);  
 4         int hash = hash(key.hashCode());  
 5         int i = indexFor(hash, table.length);  
 6         for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
 7             Object k;  
 8             //判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。  
 9             //如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果不相同，这时就是产生了hash冲突。  
10             //Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。  
11             //系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），  
12             //那系统必须循环到最后才能找到该元素。  
13             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
14                 V oldValue = e.value;  
15                 e.value = value;  
16                 return oldValue;  
17             }  
18         }  
19         modCount++;  
20         addEntry(hash, key, value, i);  
21         return null;  
22     }  

1     void addEntry(int hash, K key, V value, int bucketIndex) {  
2         Entry<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     bsp;  

 1 /** Entry是单向链表。    
 2      * 它是 “HashMap链式存储法”对应的链表。    
 3      *它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数  
 4     **/  
 5     static class Entry<K,V> implements Map.Entry<K,V> {    
 6         final K key;    
 7         V value;    
 8         // 指向下一个节点    
 9         Entry<K,V> next;    
10         final int hash;    
11    
12         // 构造函数。    
13         // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"    
14         Entry(int h, K k, V v, Entry<K,V> n) {    
15             value = v;    
16             next = n;    
17             key = k;    
18             hash = h;    
19         }    
20    
21         public final K getKey() {    
22             return key;    
23         }    
24    
25         public final V getValue() {    
26             return value;    
27         }    
28    
29         public final V setValue(V newValue) {    
30             V oldValue = value;    
31             value = newValue;    
32             return oldValue;    
33         }    
34    
35         // 判断两个Entry是否相等    
36         // 若两个Entry的“key”和“value”都相等，则返回true。    
37         // 否则，返回false    
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         // 实现hashCode()    
54         public final int hashCode() {    
55             return (key==null   ? 0 : key.hashCode()) ^    
56                    (value==null ? 0 : value.hashCode());    
57         }    
58    
59         public final String toString() {    
60             return getKey() + "=" + getValue();    
61         }    
62    
63         // 当向HashMap中添加元素时，绘调用recordAccess()。    
64         // 这里不做任何处理    
65         void recordAccess(HashMap<K,V> m) {    
66         }    
67    
68         // 当从HashMap中删除元素时，绘调用recordRemoval()。    
69         // 这里不做任何处理    
70         void recordRemoval(HashMap<K,V> m) {    
71         }    
72     }

1 1 transient Entry[] table;//存储元素的实体数组
2 2  
3 3 transient int size;//存放元素的个数
4 4  
5 5 int threshold; //临界值   当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量
6 6 
7 7  final float loadFactor; //加载因子
8 8  
9 9 transient int modCount;//被修改的次数

 1 public HashMap(int initialCapacity, float loadFactor) {
 2  2         //确保数字合法
 3  3         if (initialCapacity < 0)
 4  4             throw new IllegalArgumentException("Illegal initial capacity: " +
 5  5                                               initialCapacity);
 6  6         if (initialCapacity > MAXIMUM_CAPACITY)
 7  7             initialCapacity = MAXIMUM_CAPACITY;
 8  8         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 9  9             throw new IllegalArgumentException("Illegal load factor: " +
10 10                                               loadFactor);
11 11 
12 12         // Find a power of 2 >= initialCapacity
13 13         int capacity = 1;   //初始容量
14 14         while (capacity < initialCapacity)   //确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂
15 15             capacity <<= 1;
16 16 
17 17         this.loadFactor = loadFactor;
18 18         threshold = (int)(capacity * loadFactor);
19 19         table = new Entry[capacity];
20 20        init();
21 21    }
22 22 
23 23     public HashMap(int initialCapacity) {
24 24         this(initialCapacity, DEFAULT_LOAD_FACTOR);
25 25    }
26 26 
27 27     public HashMap() {
28 28         this.loadFactor = DEFAULT_LOAD_FACTOR;
29 29         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
30 30         table = new Entry[DEFAULT_INITIAL_CAPACITY];
31 31        init();
32 32     }

 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      //搜索指定hash值在对应table中的索引
 8          int i = indexFor(hash, table.length);
 9      // 循环遍历Entry数组,若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
10          for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
11              Object k;
12               if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同则覆盖并返回旧值
13                   V oldValue = e.value;
14                  e.value = value;
15                  e.recordAccess(this);
16                  return oldValue;
17               }
18          }
19      //修改次数+1
20          modCount++;
21      //将key-value添加到table[i]处
22      addEntry(hash, key, value, i);
23      return null;
24 }

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

1  //计算hash值的方法 通过键的hashCode来计算
2 2     static int hash(int h) {
3 3         // This function ensures that hashCodes that differ only by
4 4         // constant multiples at each bit position have a bounded
5 5         // number of collisions (approximately 8 at default load factor).
6 6         h ^= (h >>> 20) ^ (h >>> 12);
7 7         return h ^ (h >>> 7) ^ (h >>> 4);
8 8     }