一、HashMap 简介

     前面介绍了LinkedList和ArrayList两个常用的集合，这次介绍的是另外一个常用的集合HashMap。HashMap的数据结构都用到了数组和链表。HashMap继承了AbstractMap， 实现了Map，Cloneable， Serializable接口，使用的是键(key)-值(value)对存储方式，key和value都允许为null，key不允许重复 。

二、 HashMap 的数据结构

节点表示如下：

Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。

static class Node
    
      implements Map.Entry
     
       {    final int hash;    final K key;    V value;    Node
      
        next;}
      
     
    

static final class TreeNode
    
      extends LinkedHashMap.Entry
     
       {    TreeNode
      
        parent;  // red-black tree links    TreeNode
       
         left;    TreeNode
        
          right;    TreeNode
         
           prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node
          
            next) { super(hash, key, val, next); }}
          
         
        
       
      
     
    

         JDK1.8之前的HashMap是使用数组 + 链表作为数据结构，利用key的hashCode来计算hash值，再跟数组长度 - 1进行按位与得出在数组的下标，但是因为计算出来的下标有可能一样，特别是在存储的数量多的情况下一样的几率就更高了，所以在JDK1.8之前使用链表来存储计算出来下标一样的元素。但是链表的查询速度较慢，在JDK1.8对HashMap做了优化，使用数组 + 链表 + 红黑树来存储，当链表的长度大于8的时候，会转成红黑树，红黑树是一种 平衡二叉查找树 ，有较高的查找性能。 为了阅读HashMap源码，特意去了解了下红黑树，有兴趣的朋友可以去了解下红黑树，      

三、HashMap 源码解析

public class HashMap
    
      extends AbstractMap
     
          implements Map
      
       , Cloneable, Serializable {    private static final long serialVersionUID = 362498820763181265L;    /**     * 默认初始化大小，值必须保证2次幂 - MUST be a power of two.     */    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 位运算效率最高    /**     * 最大容量，2次幂必须小于等于1<<30     * MUST be a power of two <= 1<<30.     */    static final int MAXIMUM_CAPACITY = 1 << 30;    /**     * 负载因子     */    static final float DEFAULT_LOAD_FACTOR = 0.75f;    /**     * 链表的长度，当链表大于8时，有可能转换成红黑树     */    static final int TREEIFY_THRESHOLD = 8;    /**     * 在容器进行扩容时发现红黑树的长度小于 6 时会转回链表     */    static final int UNTREEIFY_THRESHOLD = 6;    /**     * 在转变成树之前，还会有一次判断，当键-值对数量大于 64 才会转换。     * 这是为了避免在哈希表建立初期，多个键-值对恰     * 好被放入了同一个链表中而导致不必要的转化     */    static final int MIN_TREEIFY_CAPACITY = 64;     /**     * 计算hash值 ：假如数组的长度是 16 ，那计算出元素在数组中的存储下标就是 hash & (16 - 1)     * 也是是 hash & 1111 ，如果有两个key，其生成的hashCode分别为ABCD0000（8个16进制，32位），0ADC0000     * 将这两个hashCode（先转成二进制）和 1111按位与的话,得到的结果都是0，但是这两个hashCode相差很多，但却     * 存在数组的同一个位置上，这样会导致链表过长，而影响查询速度，所以为了减少这种情况，所以这里使用h >>> 16（无符号右移）     */    static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }    /**     * capacity必须满足2的N次方,如果在构造函数内指定的容量cap不满足,     * 通过下面的算法将其转换为大于n的最小的2的N次方数.     */    static final int tableSizeFor(int cap) {        int n = cap - 1;        n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;    }
      
     
    

/** *  Node节点的数组，主要容器 */transient Node
    
     [] table;/** *缓存entrySet() */transient Set
     
      
       > entrySet;/** * HashMap的大小，也就是存储键-值对的数量 */transient int size;/** * 修改次数 */transient int modCount;/** * 阈值，threshold = 容量(table.length) * 负载因子, * 当HashMap中存储的键-值对数量大于这个的时候进行扩容 * * @serial */int threshold;// 负载因子，默认0.75f，负载因子越低的话容器中的空闲空间越多，冲突机会较少，查询较快// 负载因子越高的话容器中填满的元素更多了，减少了空间的开销，但元素跟元素之间的冲突就多了，冲突的话// 会生成链表或红黑树，所以查询就慢了final float loadFactor;
      
     
    

/** * 在HashMap中的get方法就是调用该方法用key来获取value * 通过key获取对应存放的节点 */final Node
    
      getNode(int hash, Object key) {    Node
     
      [] tab; Node
      
        first, e; int n; K k;    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {        // (n - 1) & hash 该元素在table中的下标，如果获取到不为null的话。        // 获取第一个（链表的头或者红黑树的root）判断key是否一样，一样的话直接返回        if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k))))            return first;        // 如果不一样判断是否有下一个元素        if ((e = first.next) != null) {            // 有的话判断该下标的元素是不是树节点            if (first instanceof TreeNode)                // 遍历红黑树获取                return ((TreeNode
       
        )first).getTreeNode(hash, key);            // 如果是链表的话遍历链表获取            do {                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;            } while ((e = e.next) != null);        }    }    return null;}
       
      
     
    

/** * HashMap中的put方法就是调用该方法来插入值 * 如果onlyIfAbsent为true的话，不改变已经存在的值 * 如果evict为false的话，说明该HashMap是刚创建的 */final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node
    
     [] tab; Node
     
       p; int n, i;    // 如果table为null的话新创建一个table，这里的resize()方法有两个作用一个是新创建table，另一个是扩容    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // n - 1 & hash 计算出该键值对存放的下标，如果该下标没有其他节点，则直接生成节点并存入    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    else {        // e ：下面操作如果该key已经存在，则将该key对应的节点赋值给e        Node
      
        e; K k;        // 如果key已经存在并且key对应的节点是在第一个的话，则使用已经存在的key的节点        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;        // 如果下标使用的是红黑树结构，则使用红黑树的方法添加键值创建树节点并添加进去        else if (p instanceof TreeNode)            e = ((TreeNode
       
        )p).putTreeVal(this, tab, hash, key, value);        // 如果下标使用的是链表结构，则生成Node节点并添加到链表的尾部        else {            for (int binCount = 0; ; ++binCount) {                if ((e = p.next) == null) {                    p.next = newNode(hash, key, value, null);                    // 如果链表长度大于8的话则转换成红黑树                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                // 如果key已经存在的话，则使用已经存在的key的节点                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }        if (e != null) {  // 如果key存在的话则修改值，并返回旧值            V oldValue = e.value;            // 判断是否要修改            if (!onlyIfAbsent || oldValue == null)                e.value = value;            // 设置节点的值后回调            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;    // 如果键值对个数超过阈值，则扩容    if (++size > threshold)        resize();    // 插入节点后回调    afterNodeInsertion(evict);    return null;}
       
      
     
    

/** * resize() 方法用于初始化数组或数组扩容， * 每次扩容后，容量为原来的 2 倍， * 并进行数据迁移。 */final Node
    
     [] resize() {    Node
     
      [] oldTab = table;    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    if (oldCap > 0) {        if (oldCap >= MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return oldTab;        }        // 将数组大小扩大一倍        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)            newThr = oldThr << 1; // double threshold    }    else if (oldThr > 0) // initial capacity was placed in threshold        newCap = oldThr;    else {               // zero initial threshold signifies using defaults        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }    if (newThr == 0) {        float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    threshold = newThr;    @SuppressWarnings({"rawtypes","unchecked"})        Node
      
       [] newTab = (Node
       
        [])new Node[newCap];    table = newTab;//如果是第一次创建数组 到这里就结束了    if (oldTab != null) {        //开始移动数组        for (int j = 0; j < oldCap; ++j) {            Node
        
          e;            if ((e = oldTab[j]) != null) {                oldTab[j] = null;                if (e.next == null)//如果该数组位置没有链表和红黑树，简单移动即可                    newTab[e.hash & (newCap - 1)] = e;                else if (e instanceof TreeNode)//红黑树移动                    ((TreeNode
         
          )e).split(this, newTab, j, oldCap); else { // preserve order // 这块是处理链表的情况， // 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序 // loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表， Node
          
            loHead = null, loTail = null; Node
           
             hiHead = null, hiTail = null; Node
            
              next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;}
            
           
          
         
        
       
      
     
    

}