HashMap和ConcurrentHashMap

Hashmap

26341ef9fe5caf66ba0b7c40bba264a5_hd.png

1.HashMap:
  它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,
  因而具有很快的访问速度,但遍历顺序却是不确定的.
  HashMap最多只允许一条记录的键(Key)为null,允许多条记录的值(Value)为null.
  HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致.
  如果需要满足线程安全,可以用 Collections.synchronizedMap(map)或者ConcurrentHashMap.

2.Hashtable:
  Hashtable继承自Dictionary类,是线程安全的,任一时间只有一个线程能写Hashtable,
  并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁.
  Hashtable不建议在新代码中使用,需要线程安全用ConcurrentHashMap,否则用Hashmap

3.LinkedHashMap:
  LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,
  先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

4.TreeMap:
  TreeMap实现SortedMap接口,能够把它保存的记录根据键(Key)排序,默认是按键值的升序排序,
  也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的.
  如果使用排序的映射,建议使用TreeMap.
  在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,
  否则会在运行时抛出java.lang.ClassCastException类型的异常.

HashMap - 存储结构
  Hashmap在JDK1.7中的结构是数组+链表
  Hashmap在JDK1.8中的结构是数组+链表+红黑树结构(当链表长度大于8时转换成红黑树)
 
HashMap - 重要字段
  int threshold;// 所能容纳的key-value对极限
    threshold = length(table的长度) * loadFactor
  final float loadFactor;// 负载因子,默认0.75
    loadFactor = 1//表示当所有的table位置都被使用后才进行扩容,等于 时间换空间
    loadFactor = 0.5//表示当table用了一半的位置,就进行扩容,等于 空间换时间
  int modCount;//HashMap结构变化的次数
    put一个已经存在的值,不属于结构改变
    put一个不存在的key-value,属于结构改变
  int size;//当前HashMap的实际的长度,不是table的长度
  
  transient Node<K,V>[] table;//Node桶数组,数据存放在这里
  默认 length(table的长度) = 16
  static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//Key的Hash值
        final K key;
        V value;
        Node<K,V> next;//链表上下一个值

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
  }

HashMap - Key位置确定
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  通过hashcode()方法获取对应Key的hashcode的值
    1111 1111 1111 1111 1111 0000 1110 1010 
    高16 = 1111 1111 1111 1111 
    低16 = 1111 0000 1110 1010 
    
    高16位不变 ,低16位异或高16位
    1111 1111 1111 1111 1111 0000 1110 1010
    0000 0000 0000 0000 1111 1111 1111 1111
    =
    1111 1111 1111 1111 0000 1111 0001 0101
    
    再与n-1进行与计算(n = hashmap的长度,-1是因为角标小1)
    0000 0000 0000 0000 0000 0000 0000 1111
    1111 1111 1111 1111 0000 1111 0001 0101
    =
    0000 0000 0000 0000 0000 0000 0000 0101 = 5(Key所在的位置)

HashMap - put流程(具体看源码)
  1.调用putVal()
  2.判断table == null || length== 0
    是:调用resize() 扩容
  3.通过Key的HashCode值,计算Key所在的数组位置
  4.判断table[i] == null
    是:调用newNode(),直接插入数据
  5.判断table[i] 链表上第一个元素是否等于当前的元素
    是:直接覆盖value
  6.判断table[i] 是不是treeNode类型
    是:红黑树直接插入数据
  7.开始遍历链表插入数据,链表长度是否大于8
    是:链表转换成红黑树,插入数据
  8.链表插入,若Key存在,直接覆盖value
    否则,默认放在第一位,next指向原来的第一位
  
  无效扩容问题:
    在putVal()中,最后会判断是否需要扩容:
    if (++size > threshold)
            resize();
    极端例子:这里判断扩容是根据size,而不是table.length,如果所有的key都放在数组的同一个位置
      会导致链表极大,size也会变大,此时数组其他空间虽然没有数据,但是还是会不断扩容
    
HashMap - 链表存储顺序
  put -> 5,7,3(假设在数组同一个位置上)
  链表结构 -> 3(next -> 7(next -> 5)), 3,7,5的反序

HashMap - 扩容机制(JDK1.7,JDK1.8加入了红黑树,略有不同) 
  void resize(int newCapacity) {   //传入新的容量
     Entry[] oldTable = table;    //引用扩容前的Entry数组
     int oldCapacity = oldTable.length;   
     //扩容前的数组大小如果已经达到最大(2^30)了      
     if (oldCapacity == MAXIMUM_CAPACITY) { 
          //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
         threshold = Integer.MAX_VALUE; 
         return;
     }
      //初始化一个新的Entry数组
     Entry[] newTable = new Entry[newCapacity];  
      //！！将数据转移到新的Entry数组里
     transfer(newTable);                         
       //HashMap的table属性引用新的Entry数组
     table = newTable;                          
     threshold = (int)(newCapacity * loadFactor);//修改阈值
  }
  void transfer(Entry[] newTable) {
     Entry[] src = table;                   //src引用了旧的Entry数组
     int newCapacity = newTable.length;
     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
         Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
         if (e != null) {
              //释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
             src[j] = null;
             do {
                 Entry<K,V> next = e.next;
                  //！！重新计算每个元素在数组中的位置
                 int i = indexFor(e.hash, newCapacity); 
                 e.next = newTable[i]; //标记[1]
                 newTable[i] = e;      //将元素放在数组上
                 e = next;             //访问下一个Entry链上的元素
             } while (e != null);
         }
     }
   }

HashMap - 为什么table默认长度是16,每次是原来的两倍
  HashMap 每次扩容是2(n)
  在初始化中new HashMap(20),调用tableSizeFor()
  并在第一次put()时候进行resize():
    Node[].length(table.length) = 32, threshold = (int)(32*0.75)=24
  0 -> 1,1 -> 1,
  2 -> 2, 
  3 -> 4,4 -> 4
  5 -> 8,6 -> 8,7 -> 8,8 -> 8
  9 -> 16,10 -> 16,11 -> 16,12 -> 16,13 -> 16,14 -> 16,15 -> 16,16 -> 16
  17 -> 32
  
  table.length 总是 = 2(n),假设table.length = 16
  n = 16 - 1= 15
    0000 0000 0000 0000 0000 0000 0000 1111
  n = 32 -1 = 31
    0000 0000 0000 0000 0000 0000 0001 1111
  相当于每次扩容后length的二进制的值只是改变了1位
  重新计算Key所在的位置时更快:
  直接取出e.hash的值:
    0000 0000 0000 0000 0000 0000 0000 0101 = 5
    0000 0000 0000 0000 0000 0000 0001 1111
    
    0000 0000 0000 0000 0000 0000 0001 0101 = 21 = 5+16
    1.位置相当于在原来的基础上增加了扩容的值(而不会是随机值),计算快
    2.更好的随机分配数据所在的数组位置,劲量避免hash冲突

HashMap - 线程不安全
  在多线程的情况下存数据,如果刚好发生了resize(),此时需要重新计算位置
  有可能会造成链表死循环,即next互相指向对方

ConcurrentHashMap

存储 :
  key != null,value != null

put : 逻辑
  final V putVal(K key, V value, boolean onlyIfAbsent) {
        //判断key和value是否为null,抛出异常
        if (key == null || value == null) throw new NullPointerException();
        //计算hash值
        int hash = spread(key.hashCode());
        int binCount = 0;
        //对当前的table进行循环
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            //初始化table
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //通过hash值原子查询当前位置上数据是否==null,-1的二进制是32个1
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //通过cas对数据进行赋值
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            //多线程扩容时,帮助扩容
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                //当前数组上的hash值相同的Node,第一个元素作为锁,锁住整个链表
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                    //...操作
                        }
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }