• 八股文第七天


    时间:2022年7月28日

    第一题:Hashmap 的底层原理(高薪常问)

    HashMap 在 JDK1.8 之前的实现方式 数组+链表

    但是在 JDK1.8 后对 HashMap 进行了底层优化,改为了由 数组+链表或者数组+红黑树 实现,主要的目的是提高查找效率

    在这里插入图片描述
    那这里就有点疑问了,为啥元素个数大于8就转为红黑树,小于6就是单向链表,有两个帖子说的很清楚大家可以去看看

    在这里插入图片描述

    • Jdk8 数组+链表或者数组+红黑树实现,当链表中的元素超过了8个以后, 会将链表转换为红黑树,当红黑树节点小于等于6时又会退化为链表,在链表长度大于 8 的时候,将链表就会变成红黑树,提高查询的效率。

    • 当 new HashMap(): 底层没有创建数组,首次调用 put()方法时,底层创建长度为 16 的数组,jdk8 底层的数组是:Node[],而非 Entry[],用数组容量大小乘以加载因子得到一个值,一旦数组中存储的元素个数超过该值就会调用 rehash 方法将数组容量增加到原的两倍,专业术语叫做扩容,在做扩容的时候会生成一个新的数组,原来的所有数据需要重新计算哈希码值重新分配到新的数组,所以扩容的操作非常消耗性能。

      默认的负载因子大小为 0.75,数组大小为 16。也就是说,默认情况下,那么当 HashMap 中元素个数超过 160.75=12 的时候,就把数组的大小扩展为 216=32,即扩大一倍。

    • 在我们 Java 中任何对象都有 hashcode,hash 算法就是通过 hashcode 与自己进 行向右位移 16 的异或运算。这样做是为了计算出来的 hash 值足够随机,足够分散,还有 产生的数组下标足够随机,

    map.put(k,v)实现原理

    (1)首先将 k,v 封装到 Node 对象当中(节点)。

    (2)先调用 k 的 hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。

    (3)下标位置上如果没有任何元素,就把 Node 添加到这个位置上。如果说下标对应的位置上有链表。此时,就会拿着 k 和链表上每个节点的 k 进行 equal。如果所有的 equals 方 法返回都是 false,那么这个新的节点将被添加到链表的末尾。如其中有一个 equals 返回了 true,那么这个节点的 value 将会被覆盖。

    map.get(k)实现原理

    (1)、先调用 k 的 hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。

    (2)、在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有,则返回 null。如果这个位置上有单向链表,那么它就会拿着参数 K 和单向链表上的每一个节点 的 K 进行 equals,如果所有 equals 方法都返回 false,则 get 方法返回 null。如果其中一 个节点的 K 和参数 K 进行 equals 返回 true,那么此时该节点的 value 就是我们要找的 value 了,get 方法最终返回这个要找的 value

    Hash 冲突

    不同的对象算出来的数组下标是相同的这样就会产生 hash 冲突,当单线链表达到一定长度 后效率会非常低。

    第二题:Hashmap 和 hashtable ConcurrentHashMap 区别(高薪常问)

    区别对比一(HashMap 和 HashTable 区别):

    1、HashMap 是非线程安全的,HashTable 是线程安全的。

    2、HashMap 的键和值都允许有 null 值存在,而 HashTable 则不行。

    3、因为线程安全的问题,HashMap 效率比 HashTable 的要高。

    4、Hashtable 是同步的,而 HashMap 不是。因此,HashMap 更适合于单线 程环境,而 Hashtable 适合于多线程环境。一般现在不建议用 HashTable, ① 是 HashTable 是遗留类,内部实现很多没优化和冗余。②即使在多线程环境下, 现在也有同步的 ConcurrentHashMap 替代,没有必要因为是多线程而用 HashTable。

    区别对比二(HashTable 和 ConcurrentHashMap 区别):

    HashTable 使用的是 Synchronized 关键字修饰,ConcurrentHashMap 是 JDK1.7 使用了锁分段技术来保证线程安全的。JDK1.8ConcurrentHashMap 取消了 Segment 分段锁,采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似,数组+链表/红黑二叉树。 synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍。

  • 相关阅读:
    你晓得小程序的身世么?
    【数据库】索引
    防抖(debounce)和节流(throttle)
    Elasticsearch倒排索引(二)深入Term Index(待补图)
    第九章《搞懂算法:决策树是怎么回事》笔记
    “Can‘t open workbook - unsupported file type: XML“
    ArrayList常见面试题
    天启科技联创郭志强:趟遍教育行业信数化沟坎,创业智能赛道重塑行业生态
    windows系统一键开启和关闭虚拟化
    MyBaties存储和查询json格式的数据(实体存储查询版本)
  • 原文地址:https://blog.csdn.net/weixin_44233087/article/details/126026364