美文网首页
java基础知识6-map

java基础知识6-map

作者: liwsh | 来源:发表于2021-04-12 21:39 被阅读0次

    1.map类图

    image.png

    2.hashtable,hashmap,treemap区别

    hashtable线程安全,key和value不能为空,concurrenthashmapkey和value也不能为空
    hashmap线程不安全,key和value可为空
    treemap基于红黑树实现的有序map
    linkedhashmap:基于put的顺序排序,场景:我们构建一个空间占用敏感的资源池,希望可 以自动将最不常被访问的对象释放掉,这就可以利用LinkedHashMap 提供的机制来实现。

    3. hashmap数据结构

    1. 数组+链表,链表长度超过8变成树
    2. hashmap如何确认hash桶位置
      key的hashCode值、高位运算、取模运算
      2.1 取模运算是(h & (length-1))HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率
      2.2 高位运算:这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,参考文章:https://tech.meituan.com/2016/06/24/java-hashmap.html
    3. put操作流程


      image.png

      4.扩容动作
      1.7 扩容,重新计算索引位置,移动元素。元素都插入在链表表头,链表的元素扩容后会倒序
      1.8扩容,过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”

    4. hashmap为什么会死循环
      该方法实现的机制就是将每个链表转化到新链表,并且链表中的位置发生反转,而这在多线程情况下是很容易造成链表回路,从而发生 get() 死循环。所以只要保证建新链时还是按照原来的顺序的话就不会产生循环(JDK 8 的改进)

    4. FAQ

    4.1 知道jdk1.8中hashmap改了啥
    由数组+链表的结构改为数组+链表+红黑树。
    优化了高位运算的hash算法:h^(h>>>16)
    扩容后,元素要么是在原位置,要么是在原位置再移动2次幂的位置,且链表顺序不变
    4.2 为什么在解决hash冲突的时候,不直接用红黑树?而选择先用链表,再转红黑树
    因为红黑树需要进行左旋,右旋,变色这些操作来保持平衡,而单链表不需要。 当元素小于8个当时候,此时做查询操作,链表结构已经能保证查询性能。当元素大于8个的时候,此时需要红黑树来加快查询速度,但是新增节点的效率变慢了
    4.3 我不用红黑树,用二叉查找树可以么
    可以。但是二叉查找树在特殊情况下会变成一条线性结构
    红黑树说明:https://tech.meituan.com/2016/12/02/redblack-tree.html
    https://blog.csdn.net/chen_zhang_yu/article/details/52415077
    参考:https://zhuanlan.zhihu.com/p/76735726

    4. concurrentHashmap

    1. 1.7采用segment分离锁,1.8采取CAS+synchronize模式(initTable用CAS控制只有一个线程初始化,put先通过volitale拿到node数组对应的元素,然后synchronize锁住这个元素进行操作链表)
    2. size方法,1.7先尝试统计每个segement的大小,如果中间发生了变化,加锁重新计算size。 1.8 put方法和remove方法都会通过addCount方法维护Map的size。size方法通过sumCount获取由addCount方法维护的Map的size
    3. 扩容
      参考:http://zhouqing86.github.io/2019/06/01/java-ConcurrentHashMap/

    相关文章

      网友评论

          本文标题:java基础知识6-map

          本文链接:https://www.haomeiwen.com/subject/vmcxlltx.html