hashMap结构

  • HashMap1.7：数组+链表
  • HashMap1.8：数组+链表+红黑树
    • 当链表长度大于等于8，或者数组容量大于等于64的时候，就会把链表转换成红黑树
    • 当红黑树的节点数量小于等于6，就会把红黑树重新转换成链表
  • HashMap1.7使用头插法
    • 我个人认为hashMap的作者觉得后来的元素大概率会先使用到，所以采用了头插
  • 1.8使用尾插法

    hash冲突和hash算法

  • 也叫做寻址算法
    • hashMap在存储数据的时候呢，就要用到hash算法，需要尽可能的让不同元素落到不同的位置上
    • 因为当元素落到同一个位置上，就会产生哈希冲突，形成链表挂上去，而链表的查询效率很低
  • 算法公式
    • ((key.hashCode=h)^(h>>>16)) & 2n（数组长度）-1= 数组的索引
  • 算法理解
    • key.hashCode的长度为32位，先用他自己的高16和低16位进行异或（相同为0，不同为1）,再用异或的结果和2n（数组长度）-1（一定是一个奇数）做与运算（与运算：有零则零）。
    • 这个算法做到了让32位的二进制尽可能的参与进来了，而且^（异或）这个符合是二进制运算中得到0，1平均概率最高的一个符号。
    • &(与)是所有二进制运算中运算速度最快的一个二进制，因为他获得操作系统底层的支持
    • 2n（数组长度）-1的结果一定是一个奇数，所以数组索引的奇偶就由key.hashCode的高低16位异或得到的结果决定，尽可能的让不同元素落到不同的位置上。
    • 而且采用&和数组长度-1可以保证当前算出来的索引得到的结果是在0~（数组长度-1）的这个范围中，也就不存在越界问题。
  1. 1.7版本扩容原理
    • （创建集合时，最好指定集合长度。否则会造成空间的浪费，当创建hashMap不指定数组长度时，默认长度为16，）当hashMap里存放的数据达到阈值（数组长度*0.75），就会自动进行扩容
    • 而每一次扩容，就需要重新计算一次地址，1.7的时候是完全重新计算，很浪费时间和性能。
  2. 1.8版本扩容原理
    • 1.8的时候就发生了很大改变，因为hashMap扩张的时候是按照原来长度的2倍扩张的
    • 在扩张的时候只需要计算oldcap的长度二进制的最高位那个1和hashCode高低16位异或算出来的那一位比较
    • 最后算出来的结果相同，位置不变，结果不同，只需要移动oldCap老数组的长度这么多位就行，这样就提高了效率

      hashMap和HashTable的区别

  • hashMap在jdk1.7使用头插法在多线程的情况下进行扩容时，可能会出现死循环问题，导致程序结束不了，而且多线程的时候容易丢数据
  • 1.8使用尾插法解决了1.7死循环的问题，但是多线程也不安全
  • 为了解决线程安全问题，首先考虑了HashTable ，HashTable 是线程安全的，但是他的键和值都不允许有null存在，HashMap 的键和值都是允许有 null 值存在的
  • 而且因为线程安全的问题，HashMap 效率就要比 HashTable 的要高，但是多线程的时候呢，也不建议使用hashTable，因为他是在方法上加了大量的syn锁，性能就会变的很低

  • 还有Collections.syncXXX 创建出来的集合也可以保证线程安全，但是内部也是加了大量的syn锁。所以多线程的情况下，我们一般都使用ConcurrentHashMap。

    ConcurrentHashMap

  • ConcurrentHashMap结构：

    • JDK1.7的时候，他的底层采用了segment分段式加锁的技术来保证线程安全的
    • 而jdk1.8时，concurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全的，底层数据结构和HashMap差不多，也是“数组+链表+红黑树”的结构
    • 他的synchronized只锁定当前链表或红黑二叉树的首节点，降低了锁粒度，这样只要hash不冲突，就不会产生并发，以较低的性能代价实现了线程安全 ```java 初始化数组或头节点时，ConcurrentHashMap并没有加锁，而是CAS的方式进行 原子替换（原子操作，基于Unsafe类的原子操作API）。他内部有一个while循环， 他会在循环中判断当前这个哈希表是否初始化好，没有就让多个线程去CAS抢锁， 抢到锁的线程独自去进行初始化，其他线程就进行线程礼让，让线程停止执行, 重新回到就绪状态等cpu调度，再竞争cpu的使用权，只是担心，持有锁得线程初始化失败

    //会有一个循环while —>一直让你多个线程同时来初始化 Sc = sizeCtl

while ((tab = table) == null || tab.length == 0) { 如果线程跑到这儿，其实都是false b线程抢锁失败，由于a线程还没有把这个数组创建好，所以说b线程还得进行while 当a进去之后，b就走到这儿，b就满足了，
Thread.yield（） 线程礼让 b 一直去进行Cas加锁 ，对于我们cpu得负担是挺大得，所以说，让这些没有抢锁成功得线程，进行线程得礼让，暂时放弃cpu执行权，等待cpu下次让他执行

b c, d, e

  1. if ((sc = sizeCtl) < 0)
  2.     Thread.yield(); // lost initialization race; just spin

//a b 有多个线程去竞争 Cas 抢锁 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //a线程 try { //再次检查double check 咱们单例设计模式 if ((tab = table) == null || tab.length == 0) { // n是计算数组长度 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings(“unchecked”) Node[] nt = (Node[])new Node<?,?>[16]; table = tab = nt; //属性得赋值 sc = n - (n >>> 2); n —>4 n % 4 = 4 n - 4 = 12 } } finally { sizeCtl = sc; } break; } }

  1. ```java
  2.  //利用unsafe去拿内存中对应索引 最新值
  3.    else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  4. //多个线程他去进行cas抢锁，其实只有一个人能够利用cas抢锁成功
  5. // 抢锁成功这哥们他就break;
  6. // 其他失败的线程继续CAS
  7.     if (casTabAt(tab, i, null,
  8.                  new Node<K,V>(hash, key, value, null)))
  9.         break;                   // no lock when adding to empty bin
  10.    }
  12. //如果不满足要插入元素位置是null
  13. //这个时候其实操作可能是个链表，也可能是一颗树
  14. else {
  15.     V oldVal = null;
  16. //这种操作链表或者树的逻辑就太复杂了，如果你要坚持使用cas那其实也行，但是毫无疑问，链表或者树过多，你对每一个元素都要cas，针对这种复杂逻辑，还不用直接上锁
  17. ，但是他也不瞎上锁，conucrrentHashMap他把这个分段式锁的思想体现淋漓尽致，他把要操作这个索引位置的对象，当锁对象，控制了锁的粒度--->在以后开发中我们式可以借鉴的.
  18.     synchronized (f) {
  19.         if (tabAt(tab, i) == f) {
  20.             if (fh >= 0) {
  21.                 binCount = 1;
  22. // 他要去遍历当前这个链表
  23.                 for (Node<K,V> e = f;; ++binCount) {
  25.                     K ek;
  26. //实际上就是去拿到链表中的每一个元素去比较他的hash和eqauls是否相等嘛
  27.                     if (e.hash == hash &&
  28.                         ((ek = e.key) == key ||
  29.                          (ek != null && key.equals(ek)))) {
  30.                         oldVal = e.val;
  31.                         if (!onlyIfAbsent)
  32.                             e.val = value;
  33.                         break;
  34.                     }
  35. //如果说都已经没有元素，OK了，尾插不得了呗
  36.                     Node<K,V> pred = e;
  37.                     if ((e = e.next) == null) {
  38.                         pred.next = new Node<K,V>(hash, key,
  39.                                                   value, null);
  40.                         break;
  41.                     }
  42.                 }
  43.             }
  44. //操作树的代码
  45.             else if (f instanceof TreeBin) {
  46.                 Node<K,V> p;
  47.                 binCount = 2;
  48.                 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  49.                                                value)) != null) {
  50.                     oldVal = p.val;
  51.                     if (!onlyIfAbsent)
  52.                         p.val = value;
  53.                 }
  54.             }
  55.         }
  56.     }
  57. //判读是否需要转换成一颗树
  58.     if (binCount != 0) {
  59.         if (binCount >= TREEIFY_THRESHOLD)
  60.             treeifyBin(tab, i);
  61.         if (oldVal != null)
  62.             return oldVal;
  63.         break;
  64.     }
  65. }
  • 原理：
    • 初始化数组或头节点时，ConcurrentHashMap并没有加锁，而是CAS的方式进行原子替换（原子操作，基于Unsafe类的原子操作API）。他内部有一个while循环，他会在循环中判断当前这个哈希表是否初始化好，没有就让多个线程去CAS抢锁，抢到锁的线程独自去进行初始化，其他线程就进行线程礼让，让线程停止执行,重新回到就绪状态等cpu调度，再竞争cpu的使用权，只是担心，持有锁得线程初始化失败
    • 他在插入数据时会进行加锁，但锁定的不是数组，而是槽中的头节点，所以，ConcurrentHashMap中锁的粒度是槽，不是整个数组，并发的性能很好
    • 扩容时也会进行加锁，锁定的也是头节点，而且可以让多个线程对他进行并发扩容，每个线程都需要先以CAS操作去抢任务，争抢一段数组的数据转移权，抢到任务后，该线程会锁定槽内的头节点，然后将链表或红黑树中的数据迁移到新的数组里
    • 查找数据不会加锁，而且扩容的时候，依然可以查询，那一段数据还没迁移到新数组，就从老数组中直接查，要是已经迁移了，但扩容还没完，就会创建一个转发节点到老数组中，到时候扩容完了 就根据转发节点去新的数组找。
    • ConcurrentHashMap实现线程安全的难点在于多线程并发扩容，即当一个线程在插入数据时，若发现数组正在扩容，那么它就会立即参与扩容操作，完成扩容后再插入数据到新数组。在扩容的时候，多个线程共同分担数据迁移任务，每个线程负责的迁移数量是 (数组长度 >>> 3) / CPU核心数。也就是说，为线程分配的迁移任务，是充分考虑了硬件的处理能力的。多个线程依据硬件的处理能力，平均分摊一部分槽的迁移工作。另外，如果计算出来的迁移数量小于16，则强制将其改为16，这是考虑到目前服务器领域主流的CPU运行速度，每次处理的任务过少，对于CPU的算力也是一种浪费。