HashMap

HashMap的底层主要是基于数组和链表来实现的，主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突/碰撞。HashMap底层是通过链表来解决hash冲突的。

hashmap.png

    /** Entry是单向链表。
     * 它是 “HashMap链式存储法”对应的链表。
     * 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value),
     * equals(Object o), hashCode()这些函数
    **/
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        // 指向下一个节点
        Entry<K,V> next;
        final int hash;
   
        // 构造函数。    
        // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"    
      Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
   
        public final K getKey() {
            return key;
        }
   
        public final V getValue() {
            return value;
        }
   
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
   
        // 判断两个Entry是否相等
        // 若两个Entry的“key”和“value”都相等，则返回true。
        // 否则，返回false
        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }
   
        // 实现hashCode()
        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }
   
        public final String toString() {
            return getKey() + "=" + getValue();
        }
   
        // 当向HashMap中添加元素时，绘调用recordAccess()。
        // 这里不做任何处理
        void recordAccess(HashMap<K,V> m) {
        }
   
        // 当从HashMap中删除元素时，绘调用recordRemoval()。
        // 这里不做任何处理
        void recordRemoval(HashMap<K,V> m) {
        }
    }

HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。

public HashMap(int initialCapacity, float loadFactor) {
          //确保数字合法
          if (initialCapacity < 0)
              throw new IllegalArgumentException("Illegal initial capacity: " +
                                                initialCapacity);
          if (initialCapacity > MAXIMUM_CAPACITY)
              initialCapacity = MAXIMUM_CAPACITY;
          if (loadFactor <= 0 || Float.isNaN(loadFactor))
              throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
 
         // Find a power of 2 >= initialCapacity
         int capacity = 1;   //初始容量
         while (capacity < initialCapacity)   //确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂
             capacity <<= 1;
 
         this.loadFactor = loadFactor;
         threshold = (int)(capacity * loadFactor);
         table = new Entry[capacity];
        init();
    }
 
     public HashMap(int initialCapacity) {
         this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
 
     public HashMap() {
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
         table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
     }

public V put(K key, V value) {
     // 若“key为null”，则将该键值对添加到table[0]中。
     if (key == null)
         return putForNullKey(value);
     // 若“key不为null”，则计算该key.hashCode()的哈希值，然后将其添加到该哈希值对应的链表中。
     int hash = hash(key.hashCode());
     //搜索指定hash值在对应table中的索引
     int i = indexFor(hash, table.length);
     // 循环遍历Entry数组,若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
         Object k;
 //如果key相同则覆盖并返回旧值
         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
          }
      }
     //修改次数+1
     modCount++;
     //将key-value添加到table[i]处
     addEntry(hash, key, value, i);
     return null;
}

     static int indexFor(int h, int length) { 
        //根据hash值和数组长度算出索引值
        // h&(length-1)==h%length (求余数)         
        return h & (length-1);  
        //这里不能随便算取，用hash&(length-1)是有原因的，这样可以确保算出来的索引是在数组大小范围内，不会超出
     }

void addEntry(int hash, K key, V value, int bucketIndex) {
     //链表的头插法,将原来头位置的Entry设置成新Entry的下一个节点
     Entry<K,V> e = table[bucketIndex];
     table[bucketIndex] = new Entry<>(hash, key, value, e);
     if (size++ >= threshold) //如果大于临界值就扩容
         resize(2 * table.length); //以2的倍数扩容
}

void resize(int newCapacity) {
          Entry[] oldTable = table;
          int oldCapacity = oldTable.length;
          if (oldCapacity == MAXIMUM_CAPACITY) {
              threshold = Integer.MAX_VALUE;
              return;
         }
  
         Entry[] newTable = new Entry[newCapacity];
         transfer(newTable);//用来将原先table的元素全部移到newTable里面
         table = newTable;  //再将newTable赋值给table
         threshold = (int)(newCapacity * loadFactor);//重新计算临界值
     }

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for(int j=0;j<src.length;j++) {
        Entry<K, V> e = src[j];
        if(e!=null) {
            src[j]=null;
            do {
               Entry<K, V> next = e.next; //保存下一次循环的Entry
                int i = indexFor(e.hash, newCapacity); //计算新table需要插入的位置
                //头插法,原位置上的Entry设置成新节点的next
               e.next = newTable[i];
                //新节点占据原位置
                newTable[i] = e;
                //轮替，下一次循环
                e = next;
            } while(e!=null);
        }
    }
}