首页 > 编程学习 > 9.12每日一考

9.12每日一考

发布时间:2022/9/12 20:50:44

set集合如何保证元素不重复 3

1.在set集合添加元素时,会首先调用该对象的hashcode方法计算哈希值

2.将计算出的哈希值去哈希表中查询,如果不存在该值,则添加成功,否则调用对象的equals方法比较对象的内存地址,如果内存地址也相同,则是重复的对象,该对象添加失败。如果equals返回的是false,则说明两个对象不是同一个对象。则该对象就会添加到已有对象链表的末尾。该种情况称为hash碰撞。

目的:如果直接调用equals方法,当数据量过大时,么此调用一次equals方法,效率低,用hashCode方法比较减少对象比较次数,提高查找效率。

注意:哈希值相同的对象不一定相同,但内存地址相同的对象哈希值一定相同(如Aa和BB,Bb和CC,Cc和DD的哈希值就相同)

HashMap是如何快速定位到数据的 3

简说:时间换空间,空间换时间,它内部通过空间换时间的方法,用一个大数组存储所有的value ,并根据key直接计算出value应该存储在那个索引

细说:由于HashMap底层数据结构是数组加链表or红黑树的实现,所以进行定位时,先利用哈希值定位到数据元素,再便利该元素链表,找出对应元素。通过原始哈希值,二次哈希值,桶下标(二次哈希值%16)来存方数据,可以实现集合中元素的快速查找。

二次哈希原因:为了让最后计算的索引分布的足够均匀,防止某个链表过长出现红黑树树化

常见的Map集合

  1. HashMap:数组+链表存储数据,线程不安全,1.8后数组+(链表|红黑树)
  2. ConcurrentHashMap:JDK1.7采用分段🔒的思想,1.8中弃用Segment分段🔒,改用Synchroized+CAS实现线程安全,并也引入红黑树。
  3. HashTable:线程安全,与HashMap类似,继承自Dictionary类,并发性没有ConcurrentHashMap好
  4. TreeMap:基于二叉树数据结构存储数据,实现了SortedMap接口,保障了顺序存储,默认按值的升序排序,也可自定义。
  5. LinkedHashMap:继承HashMap,内部使用链表保存元素的插入顺序,当通过Iterator遍历LinkedHashMap时,会按照元素的插入顺序访问

HashMap为什么在JDK1.8中引入红黑树

简说:正常业务下,主要是防止DoS攻击,其次是防止链表过长性能下降(一般情况下,链表长度在6左右)

细说:

  • 树化条件: 同下表重复较多,链表长度超过树化阈值8,数组长度>64
  • 红黑树特性: 父节点左侧都是比他小的元素,父节点右侧都是比他大的元素
  • 设置阈值原因:链表较短的情况下,链表的性能是优于红黑树的,而且树化后,占用内存会大大增多。
  • 树化退化:在扩容时如果拆分树时,树元素个数 <= 6 则会退化链表,remove 树节点时,若 root、root.left、root.right、root.left.left 有一个为 null ,也会退化为链表

说说HashMap中的索引

计算方法

  • 首先,计算对象的 hashCode()
  • 再进行调用 HashMap 的 hash() 方法进行二次哈希
  • 二次 hash() 是为了综合高位数据,让哈希分布更为均匀
    & (capacity – 1)前提capacity是2的n次幂
  • 最后 & (capacity – 1) 得到索引

数组容量为何是 2 的 n 次幂

  1. 计算索引时效率更高:如果是 2 的 n 次幂可以使用位与运算代替取模
  2. 扩容时重新计算索引效率更高: hash & oldCap == 0 的元素留在原来位置 ,否则新位置 = 旧位置 + oldCap

注意

  • 二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提,如果 hash 表的容量不是 2 的 n 次幂,则不必二次 hash
  • 容量是 2 的 n 次幂** 这一设计计算索引效率更好,但 hash 的分散性就不好,需要二次 hash 来作为补偿,没有采用这一设计的典型例子是 Hashtable**
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号