1.HashMap之JDK1.7

• 数据结构 数组+链表

  
  image.png

• put实现原理:
  (1).先检测table是否为null，如果为null,就初始化table,默认容量为16，阈值为16*0.75=12,然后
  (2)判断key是否为null,如果key为null,table【0】位置Entry对象是否为null，如果为null,直接插入，如果不为null，新值替换旧值。
  (3).如果key不为null,把key通过hash算法【右移，异或运算，提高hash值的散列性】得到hash值，然后根据(hash&table.length-1)得到table下标index，判断table[index]是否为null,如果为空，直接插入，如果不为null,遍历Entry链表的每一个节点，通过比对key和hash值是否相等，如果相等，新值替换旧值，如果不相等，直接在头插法插入一个Entry节点。

    public V put(Key key,V value){
     
    if (table == EMPTY_TABLE) {
      /*初始化阈值和table：根据传入的容量大小获取大于该值的最小的二次幂值，并确定其扩容阈值,
如果是10的话，大于该值的最小二次幂值为16*/
            inflateTable(threshold);
            if(key==null){
                 return putForNullKey(value);
             }
            int hash=hash(key);
            int 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);
            rerurn null;
        }
    }
    statci int hash(Object k){
       int h=hash Seed;
       h=h ^ k.hashCode();
       h=h^(h>>>20)^(h>>>12);
   /*h各种右移，然后和自身进行异或运算，目的是使得到的hash值散列的更加均匀，减少hash冲突，从而减少单链表的长度，提高get("key")获取元素的效率*/
      return h^(h>>>7)^(h>>>4);
    }
   //获取table[]数组下标
   static int indexFor(int h,int length){
       return h&(legth-1);
   }

    private V putForNullKey(V value){
          // 一样的，新旧值替换
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
            if (e.key == null) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        modCount++;  
        // 插入到数组下标为0位置
        addEntry(0, null, value, 0);  
        return null;  
   }
 //先检查是否需要扩容，然后插入.
    void addEntry(int hash,K key ,V value,int bucketIndex){
             if((size>=threshold)&&(table[bucketIndex])){
                   resize(2*table.length);
                   hash=(key!=null)？hash(key):0;
                   bucketIndex=indexFor(hash,table.length);
             }
           createEntry(hash, key, value, bucketIndex);
     }
 void createEntry(int hash, K key, V value, int bucketIndex) {
 /*头插法：获取头结点，创建一个Entry对象他的next指针指向头结点，之后将它移动到数组中的首节点上*/
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;//每次创建一个Entry对象，size就会+1，当size>=threshold时，就会触发扩容
    }

• hashMap扩容条件,当HashMap从16扩容到32时，threshold的值会基于新的容量（32）和负载因子（通常是0.75）重新算,如果初始化hashmap时不传initialCapacity，默认的数组容量是16，threshold阈值是12，当超过12时，会触发扩容机制，如果initialCapacity=10，会通过计算获取大于该值的最小的二次幂值即16.【threshold = new_capacity * loadFactor】

• Get方法实现原理 : 如果key=null,直接table[0]拿到Entry节点，getValue得到值即可，如果key!=null,那么
  计算hash值，然后hash&table.length-1得到index索引值，然后遍历table[index] 如果table[index].next等于null，表示当前节点是单节点，检测key和hash是否相等，如果相等直接返回e.value即可，table[index].next！=null，表示链表，直接遍历上的每一个Entry，比较key和hash值是否相等，如果相等，返回当前Entry的值，否则就是返回null.

public V get(Object key) {
    // 键为null时，调用getForNullKey
    if (key == null)
        return getForNullKey();
    // 计算hash值  
    int hash = hash(key.hashCode());
    // 计算数组下标索引，遍历链表
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        // key相同，返回对应value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    // 没有该键，返回null
    return null;
}

• 扩容机制

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(),将元素移到新数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 指向新创建的数组
    table = newTable;
    // 阈值重新计算
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

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;
            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;
        }
    }
}

2.HashMap之JDK1.8

• 数据结构 数组+链表+红黑树
• put实现原理:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table数组未初始化或长度为0，初始化、扩容（resize()既初始化又扩容）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算数组索引下标，如果为null直接插入（写的太简洁了。。。）
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 当hash一致,键一致，说明该键在table中已存在，使用e保存（后边会实现新旧值替换逻辑）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 键不存在，并且如果为红黑树节点，插入红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 键不存在，并且如果为链表，插入链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 使用尾插法：将元素插入到链表末尾
                    /* 为什么1.7用头插法，1.8用尾插法？
                    我想应该是在1.8中引入了红黑树，在判断是否树化时有一个链表长度阈值，这个长度要一个个遍历，既然是要一个个遍历的话，就直接在尾部插入就好。而在1.7中他是不需要走到链表尾部的，采用头插法效率更高
                    */
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度达到树化阈值，转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果遍历链表时，发现链表中存在该键，退出（后边会实现新旧值替换逻辑）
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 新旧值替换逻辑，和1.7一样
        if (e != null) { // existing mapping for 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;
}

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

• Get方法实现原理

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 赋值，获取数组下标索引对应节点first
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // table[index]节点刚好就是要找的
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 不是table[index]对应元素，遍历其链表或树
        if ((e = first.next) != null) {
            // 首节点是tree类型，遍历树
            if (first instanceof TreeNode)
                // 找到返回树节点
                return ((TreeNode<K,V>)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);
        }
    }
    // 找不到，返回null
    return null;
}

• 【如果链表的长度大于8且数组长度大于64的时候，就会把链表转换成红黑二叉树】