133 并发容器类 map

HashMap:

jdk1.7

   底层存储 entry数组

    查询使用hash表算法

    h&(lenght-1) --- 取模计算数组下标

    下标相同,组成链表,顺序查找

     k,v总数超过一定比例 引发数组扩容 负载因子*length

     扩容方法 transfor 遍历全部元素 重新取模 放入数组

      扩容中无法保证数据问题 线程不安全。

 

jdk 1.8:

    链表长度超过8转换红黑树----低于8 此时红黑树插入慢 查找差不多。

    

concurrentHashMap:

   

jdk1.7:

   segment---特定的hashtable数组

   segment数组本身不扩容,segment自身扩容。

   传入 segment数组 大小---并发度

   分段锁方式(segment)

 

jdk1.8:

     抛弃了分段锁,类似hashmap的结构:

     cas操作+synchronized保证线程安全,

      null--直接cas,成功赋值,失败自旋。

     不为null--synchronized 加锁操作,锁住链表表头

      由于链表结构数据量相对少,锁粒度小,并发度高,性能好。

 

concurrentSkipListMap :

key值有排序

headindex入口 插入时随机生成索引,查询时跳过部分元素 加速查询

索引可以出现粒度更大的高级索引 

删除节点时节点上的索引同步删除 同时影响headindex上的索引层级。

   

    

上一篇:133、Java获取main主函数参数


下一篇:[LeetCode] 133. Clone Graph