jdk8 hashmap

jdk8的HashMap是桶+链表+红黑树实现的，由于加入了红黑树以及其他优化，HashMap的插入查找的性能提高了很多。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null，HashMap非线程安全。

得到hash值

存入时，对key使用hashcode方法获得哈希值ha，再把这个哈希值取高位和ha异
或运算得到hash，然后hash和（桶值-1）与运算代替效率低的取模运算，得到存 储位置的下标。

static final int hash(Object key) {   
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与异或运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put操作：

如果这个位置没有元素，直接放入，否则判断是链表还是红黑树再分别处理，若是链表的话，判断插入后结点个数是否超过阈值，超过就变为红黑树。在插入过程中如果发现key相同就覆盖。

public V put(K key, V value) {
      // 对key的hashCode()做hash
      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;
     // 步骤①：tab为空则创建
     if ((tab = table) == null || (n = tab.length) == 0)
         n = (tab = resize()).length;
     // 步骤②：计算index，并对null做处理 
     if ((p = tab[i = (n - 1) & hash]) == null) 
         tab[i] = newNode(hash, key, value, null);
     else {
         Node<K,V> e; K k;
         // 步骤③：节点key存在，直接覆盖value
         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) {
                     p.next = newNode(hash, key,value,null);
                       //链表长度大于8转换为红黑树进行处理
                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                         treeifyBin(tab, hash);
                     break;
                 }
                    // key已经存在直接覆盖value
                 if (e.hash == hash &&
                     ((k = e.key) == key || (key != null && key.equals(k))))                                          break;
                 p = e;
             }
         }
         
         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;
 }

扩容：

扩容就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素，方法是使用一个新的数组代替已有的容量小的数组。

Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。

我们在扩充HashMap迁移旧链表的时候，JDK1.7的实现是重新计算hash，但是由于容量是二次幂的扩大，重新计算位置还是hash和（n-1）与运算，得到的结果实际上要么是和原来索引一样，要么就是原索引再移动2次幂的位置，所以JDK8做了优化只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。JDK8的hashmap不会像之前那样旧链表迁移新链表的时候，如果在新表的数组索引位置相同，链表元素会倒置，JDK8是不会倒置的。

resize源码：

final Node<K,V>[] resize() {
     Node<K,V>[] 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;
         }
         // 没超过最大值，就扩充为原来的2倍
         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);
     }
     // 计算新的resize上限
     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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
     table = newTab;
     if (oldTab != null) {
         // 把每个bucket都移动到新的buckets中
         for (int j = 0; j < oldCap; ++j) {
             Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
                 else { // 链表优化重hash的代码块
                     Node<K,V> loHead = null, loTail = null;
                     Node<K,V> hiHead = null, hiTail = null;
                     Node<K,V> next;
                     do {
                         next = e.next;
                         // 原索引
                         if ((e.hash & oldCap) == 0) {
                             if (loTail == null)
                                 loHead = e;
                             else
                                 loTail.next = e;
                             loTail = e;
                         }
                         // 原索引+oldCap
                         else {
                             if (hiTail == null)
                                 hiHead = e;
                             else
                                 hiTail.next = e;
                             hiTail = e;
                         }
                     } while ((e = next) != null);
                     // 原索引放到bucket里
                     if (loTail != null) {
                         loTail.next = null;
                         newTab[j] = loHead;
                     }
                     // 原索引+oldCap放到bucket里
                     if (hiTail != null) {
                         hiTail.next = null;
                         newTab[j + oldCap] = hiHead;
                     }
                 }
             }
         }
     }
     return newTab;
 }

get方法：

public V get(Object key) {

    Node e;

    return (e = getNode(hash(key), key)) == null ? null : e.value;

}

final Node getNode(int hash, Object key) {

    Node[] tab; Node first, e; int n; K k;

    // 如果数组不等于空并且可以根据Hash值找到键值对在数组中的位置

    if ((tab = table) != null && (n = tab.length) > 0 &&

        (first = tab[(n - 1) & hash]) != null) {

        // 总是先检查第一个节点，找到则返回

        if (first.hash == hash && // always check first node

            ((k = first.key) == key || (key != null && key.equals(k))))

            return first;

        if ((e = first.next) != null) {

            // 如果是红黑树，则遍历红黑树，取节点Value值

            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;

}

final TreeNode getTreeNode(int h, Object k) {

    return ((parent != null) ? root() : this).find(h, k, null);

}

final TreeNode find(int h, Object k, Class kc) {

    TreeNode p = this;

    do {

        int ph, dir; K pk;

        TreeNode pl = p.left, pr = p.right, q;

        // 传入的Hash值小于当前节点的Hash值，进入左节点

        if ((ph = p.hash) > h)

            p = pl;

        // 大于当前节点Hash值，进入右节点

        else if (ph < h)

            p = pr;

        // 传入的Hash值与当前节点Hash值相等，并且Key相等，则返回当前节点

        else if ((pk = p.key) == k || (k != null && k.equals(pk)))

            return p;

        // 如果左节点为Null，则进入右节点

        else if (pl == null)

            p = pr;

        // 如果右节点为Null，则进入左节点

        else if (pr == null)

            p = pl;

        // 如果是按照比较器排序，则通过比较器返回值决定进入左节点还是右节点

        else if ((kc != null ||

                  (kc = comparableClassFor(k)) != null) &&

                (dir = compareComparables(kc, k, pk)) != 0)

            p = (dir < 0) ? pl : pr;

        // 如果右节点找到此关键字，直接返回

        else if ((q = pr.find(h, k, kc)) != null)

            return q;

        // 条件都不满足，则进入左节点

        else

            p = pl;

    } while (p != null);

    return null;

}

关于线程安全：

HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。

ConcurrentHashMap的锁分段技术

 HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，**首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。**

get方法里将要使用的共享变量都定义成volatile，定义成volatile的变量，能够在线程之间保持可见性，能够被多线程同时读，并且保证不会读到过期的值，但是只能被单线程写（有一种情况可以被多线程写，就是写入的值不依赖于原值）。

在get操作里只需要读不需要写共享变量count和value，所以可以不用加锁。之所以不会读到过期的值，是根据java内存模型的happen before原则，对volatile字段的写入操作先于读操作，即使两个线程同时修改和获取volatile变量，get操作也能拿到最新的值，这是用volatile替换锁的经典应用场景。

put方法里需要对共享变量进行写入操作，所以为了线程安全，在操作共享变量时必须得加锁。Put方法首先定位到Segment，然后在Segment里进行插入操作。插入操作需要经历两个步骤，第一步判断是否需要对Segment里的HashEntry数组进行扩容，第二步定位添加元素的位置然后放在HashEntry数组里。扩容的时候首先会创建一个两倍于原容量的数组，然后将原数组里的元素进行再hash后插入到新的数组里。为了高效ConcurrentHashMap不会对整个容器进行扩容，而只对某个segment进行扩容。