源码分析

变量解释

约定前面的数组结构的每一个格格称为桶
约定桶后面存放的每一个数据称为bin

transient int size;HashMap中存放KV的数量（为链表和树中的KV的总和）
int threshold; 如果当前size超过threshold，会调用resize方法
（capacity * load factor）
final float loadFactor;装载因子，默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。

    final int capacity() {
        return (table != null) ? table.length :
            (threshold > 0) ? threshold :
            DEFAULT_INITIAL_CAPACITY;
    }

capacity:HashMap中桶的数量。默认值为16

重要函数解析（JDK1.7）

put

public V put(K key, V value) {
      if (table == EMPTY_TABLE) {
          inflateTable(threshold);
      }
      if (key == null)
          return putForNullKey(value);
      int hash = hash(key);
      int i = indexFor(hash, table.length);
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
          Object k;
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
              V oldValue = e.value;
              e.value = value;
              e.recordAccess(this);
              return oldValue;
          }
      }
 
      modCount++;
      addEntry(hash, key, value, i);
      return null;
  }

  void addEntry(int hash, K key, V value, int bucketIndex) {
      if ((size >= threshold) && (null != table[bucketIndex])) {
          resize(2 * table.length);
          hash = (null != key) ? hash(key) : 0;
          bucketIndex = indexFor(hash, table.length);
      }
      createEntry(hash, key, value, bucketIndex);
  }

indexFor

static int indexFor(int h, int length) {    
     return h & (length-1);    
 }   

最常见的取hash算法是value mod length，而这里用的是‘&’运算
分析：HashMap的capacity都是2的幂，length-1转换成二进制就全是1，例如（16的容量，length-1就为1111），这样&运算的话，参与运算的另一个成员的每位是什么，运算结果就是什么。假设与hash值参与运算的某一位为0，那么不管hash的对应的那一位是什么，对应的运算结果位都为0，造成hash冲突。
&运算的好处

1. 1.length（2的整数次幂）的特殊性导致了length-1的特殊性（二进制全为1）
2. 位运算快于十进制运算，hashmap扩容也是按位扩容，所以相比较就选择了后者

put过程

1. 首先检测table是否为空，为空则创建一个数组
2. 判断key是否为null。若为null，特殊处理，创建一个（key为null）hash值为0的k-v对
3. 算出key所对应的hash值，找出数组中对应的下标i
4. 遍历table[i]是否存在相同的键值，如果相同则覆盖，返回一个老value值
5. 如果没有一样的，调用addEntry()，判断在插入之前的size是否超过threshold，如果超过就调用resize()扩容两倍的长度,注意扩容的顺序，扩容之前old1->old2->old3，扩容之后old3->old2->old1
6. 如果扩容了，因为数组的长度变了，需要重新计算下标。
7. 插入：注意插入的顺序，原先table[index]的链表比如 old1->old2->old3，插入新值之后为new1->old1->old2->old3.

1.7之前是头插法，1.8之后是尾插法。因为1.8是数组+ 链表+红黑树（table[i]超过8个），效率变高，之前头插法是因为如果链表接了10000个，尾插法遍历太多。

resize

   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;    
       threshold = (int)(newCapacity * loadFactor);    
   }    

transfer

    void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;  
        for (Entry<K,V> e : table) {  
  
            while(null != e) {  
                Entry<K,V> next = e.next;            ---------------------(1)  
                if (rehash) {  
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }  
                int i = indexFor(e.hash, newCapacity);   
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            } // while  
        }  

get

public V get(Object key) {
       if (key == null)
           return getForNullKey();
       Entry<K,V> entry = getEntry(key);
 
       return null == entry ? null : entry.getValue();
   }
   final Entry<K,V> getEntry(Object key) {
       if (size == 0) {
           return null;
       }
 
       int hash = (key == null) ? 0 : hash(key);
       for (Entry<K,V> e = table[indexFor(hash, table.length)];
            e != null;
            e = e.next) {
           Object k;
           if (e.hash == hash &&
               ((k = e.key) == key || (key != null && key.equals(k))))
               return e;
       }
       return null;
   }

get过程：

1. 如果key为null，则在table[0]寻找
2. 否则计算key对应的hash，找到在table表中的下标
3. 遍历table[i]的链表，通过hash和equals找到Entry
4. 得到entry中的value

多线程为什么导致死循环

1. size超过当前最大容量*负载因子时候会发生resize
2. 两个线程同时执行了resize的方法（transfer()），在各自内部线程的栈里都生成了局部的table。
   比如：
3. 扩容前 table[i] - >3 - > 7 - > null
4. 需要扩容了，transfer方法：

• 线程1： e指向3,nexr指向7 暂时挂起
• 线程2：完成扩容，table[j] = 7 -> 3 - > null

3. 线程1获取时间片，继续执行循环，这时把table[j] - >3 -> null，此时e指向7，next指向3；
   然后继续插入，table[j] -> 7 -> 3 - >null，但是此时7的next已经是3，不是null了，则继续循环3；
   e指向3，next为null；循环之后，3指向7；
   互相指向，以后一旦执行到遍历next操作，会死循环，cpu占用率到100%

参考

HashMap的indexFor方法
Java集合框架：HashMap
疫苗：JAVA HASHMAP的死循环