怎么做卡盟网站免费,网站开发分为前端和后台,php .net做网站哪个好,广东省网站免备案前言 HashMap 本身不是线程安全的. 在多线程环境下使用哈希表可以使用: Hashtable#xff08;不推荐使用#xff09;ConcurrentHashMap#xff08;推荐使用#xff09; HashMap HashMap数据结构
根本#xff1a; 数组 链表#xff08;jdk1.7#xff09;/数组链表红黑…前言 HashMap 本身不是线程安全的. 在多线程环境下使用哈希表可以使用: Hashtable不推荐使用ConcurrentHashMap推荐使用 HashMap HashMap数据结构
根本 数组 链表jdk1.7/数组链表红黑树jdk1.8当链表长度超过阈值8将链表转为红黑树 时间复杂度降低为O(logn)
基本概念 容量capacity 默认16 一个桶中的容量 加载因子load factor 默认0.75 即桶中的可利用大小 HashMap时间复杂度 若美好的状态下没有hash冲突 每个桶只有一个元素时间复杂度 O(1) 最差是O(n) 红黑树则是O(logn)。
为什么HashMap非线程安全 1 put()时若两个线程都put了同样的key则值会被覆盖 已被修复 当A线程put()数据时都发现空间不够执行resize()时而同时B线程也put()数据也发现空间不够执行resize()有可能在A线程rehash()生成新表时节点i-k而B线程rehash()生成新表时又将节点k-j导致生成了死循环i.nextk;k.nexti;当一旦进入这个链表就会导致死循环。 扩容造成死循环和数据丢失 假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作 正常扩容后的结果是下面这样的 但是当线程A执行到上面transfer函数的第11行代码时CPU时间片耗尽线程A被挂起。即如下图中位置所示 此时线程A中e3、next7、e.nextnull 当线程A的时间片耗尽后CPU开始执行线程B并在线程B中成功的完成了数据迁移 重点来了根据Java内存模式可知线程B执行完数据迁移后此时主内存中newTable和table都是最新的也就是说7.next3、3.nextnull。 随后线程A获得CPU时间片继续执行newTable[i] e将3放入新数组对应的位置执行完此轮循环后线程A的情况如下 接着继续执行下一轮循环此时e7从主内存中读取e.next时发现主内存中7.next3此时next3并将7采用头插法的方式放入新数组中并继续执行完此轮循环结果如下 此时没任何问题。 上轮next3e3执行下一次循环可以发现3.nextnull所以此轮循环将会是最后一轮循环。 接下来当执行完e.nextnewTable[i]即3.next7后3和7之间就相互连接了当执行完newTable[i]e后3被头插法重新插入到链表中执行结果如下图所示 上面说了此时e.nextnull即nextnull当执行完enull后将不会进行下一轮循环。到此线程A、B的扩容操作完成很明显当线程A执行完后HashMap中出现了环形结构当在以后对该HashMap进行操作时会出现死循环。 并且从上图可以发现元素5在扩容期间被莫名的丢失了这就发生了数据丢失的问题。 其中第六行代码是判断是否出现hash碰撞假设两个线程A、B都在进行put操作并且hash函数计算出的插入下标是相同的当线程A执行完第六行代码后由于时间片耗尽导致被挂起而线程B得到时间片后在该下标处插入了元素完成了正常的插入然后线程A获得时间片由于之前已经进行了hash碰撞的判断所有此时不会再进行判断而是直接进行插入这就导致了线程B插入的数据被线程A覆盖了从而线程不安全。 除此之前还有就是代码的第38行处有个size我们这样想还是线程A、B这两个线程同时进行put操作时假设当前HashMap的zise大小为10当线程A执行到第38行代码时从主内存中获得size的值为10后准备进行1操作但是由于时间片耗尽只好让出CPU线程B快乐的拿到CPU还是从主内存中拿到size的值10进行1操作完成了put操作并将size11写回主内存然后线程A再次拿到CPU并继续执行(此时size的值仍为10)当执行完put操作后还是将size11写回内存此时线程A、B都执行了一次put操作但是size的值只增加了1所有说还是由于数据覆盖又导致了线程不安全。 具体 首先HashMap本身线程不安全其次HashMap的key值可以为空 下面是HashMap的hash方法可以看出如果key值为空hash方法的返回值为0 HashMap 扩容是等某一次 put 后发现负载因子不达标后开始扩容, 新建一个表, 重新将元素哈希(具体细节有机会再讲) HashTable
Hashtable源码中的put方法中的key如果为空hashCode方法会抛出空指针异常 2.1**HashTable的线程安全只是简单的把关键方法加上了 synchronized 关键字. ** 相当于直接针对 Hashtable 对象本身加锁.如果多线程访问同一个 Hashtable 就会直接造成锁冲突.size 属性也是通过 synchronized 来控制同步, 也是比较慢的.一旦触发扩容, 就由该线程完成整个扩容过程. 这个过程会涉及到大量的元素拷贝, 效率会非常低. 一个Hashtable只有一把锁两个线程访问Hashtable中的任意数据都会出现锁竞争就如上图有两个线程要操作这两个元素由于是一把大锁就会产生竞争但是仔细分析这两操作在不同的哈希桶上不牵扯修改同一个变量因此就不会发生线程安全所以上面的锁竞争是没有必要的。如果两个修改落到同一个哈希桶上有线程安全风险 ConcurrentHashMap
相比之下ConcurrentHashMap就做出了重大的改进把锁的粒度细化了 读操作没有加锁(但是使用了 volatile 保证从内存读取结果), 只对写操作进行加锁. 加锁的方式仍然 是是用 synchronized, 但是不是锁整个对象, 而是 “锁桶” (用每个链表的头结点作为锁对象), 大大降 低了锁冲突的概率.充分利用 CAS 特性. 比如 size 属性通过 CAS 来更新. 避免出现重量级锁的情况.优化了扩容方式: 化整为零 「 发现需要扩容的线程, 只需要创建一个新的数组, 同时只搬几个元素过去. 扩容期间, 新老数组同时存在. 后续每个来操作 ConcurrentHashMap 的线程, 都会参与搬家的过程. 每个操作负责搬运一小 部分元素. 搬完最后一个元素再把老数组删掉. 这个期间, 插入只往新数组加. 这个期间, 查找需要同时查新数组和老数组 」 此时一个哈希表上面的桶的个数可能会非常多导致出现锁冲突的概率大大降低了 扩容申请更大的内存搬运元素搬运元素过程肯定要重新哈希 上面讲的都是基于Java 8里的在Java1.7里ConcurrentHashMap不是每个桶一个锁而是“分段锁”一个锁管若干个桶 ConcurrenHashMap的key也不可以为空看下面的源码中的put方法如果keynull则会抛出空指针异常 总结 HashMap: 线程不安全. key 允许为 nullHashtable: 线程安全. 使用 synchronized 锁 Hashtable 对象, 就是一把大锁锁冲突极高效率较低. key 不允许为 null.ConcurrentHashMap: 线程安全. 使用 synchronized 锁每个链表头结点, 锁冲突概率低, 充分利用 CAS 机制. 优化了扩容方式. key 不允许为 null
