Java集合2(补档)

Java
发布日期:   2022-11-09
更新日期:   2023-08-31
文章字数:   3.2k
阅读时长:   11 分
阅读次数:  

HashMap

说说HashMap底层的实现原理

HashMap是Java中的一个哈希表实现，用于存储键值对（key-value）数据。它是基于哈希算法实现的，可以快速进行插入、删除和查找操作。

HashMap的核心思想是将键通过哈希函数转换为数组的下标，然后将值存储在该下标位置上

JDK7和JDK8中HashMap的区别

  • JDK7中的HashMap，是基于数组+链表来实现的，它的底层维护一个Entry数组。
  • JDK8中的HashMap，是基于数组+链表+红黑树来实现的，它的底层维护一个Node数组

当链表上的元素个数超过 8 个并且数组长度 >= 64 时自动转化成红黑树，节点变成树节点，以提高搜索效率和插入效率到 O(logN)

Map put的过程

  1. 首次扩容： 先判断数组是否为空，若数组为空则进行第一次扩容（resize）；
  2. 计算索引： 对key的hashCode()做hash运算，计算数组中的index；
  3. 插入数据：
    • 如果当前位置元素为空，则直接插入数据；
    • 如果当前位置元素非空，且key已存在，则直接覆盖其value；
    • 如果当前位置元素非空，且key不存在，则将数据链到链表末端；
    • 若链表长度达到8，则将链表转换成红黑树，并将数据插入树中；
  4. 再次扩容 如果数组中元素个数（size）超过threshold，则再次进行扩容操作。

Map get的过程

  • 1.对key的hashCode()做hash运算，计算index;

  • 2.如果在bucket⾥的第⼀个节点⾥直接命中，则直接返回；

  • 3.如果有冲突，则通过key.equals(k)去查找对应的Entry;

  • 4.若为树，则在树中通过key.equals(k)查找，O(logn);

  • 5.若为链表，则在链表中通过key.equals(k)查找，O(n)。

HashMap的扩容机制

一些关键的值：

  • DEFAULT_INITIAL_CAPACITY Table数组的初始化长度： 16
  • DEFAULT_LOAD_FACTOR 负载因子：默认值为0.75。 当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容，扩容为原来的两倍
  • TREEIFY_THRESHOLD 链表树化阙值： 默认值为 8 。
  • UNTREEIFY_THRESHOLD 红黑树链化阈值： 默认值为 6 。
  • MIN_TREEIFY_CAPACITY = 64 最小树化阈值，当Table所有元素超过改值，才会进行树化（为了防止前期阶段频繁扩容和树化过程冲突）。

扩容过程：

  1. 数组的初始容量为16，而容量是以2的次方扩充的
  2. 数组是否需要扩充是通过负载因子判断的，如果当前元素个数为数组容量的0.75时，就会扩充数组。
  3. 为了解决碰撞，数组中的元素是单向链表类型。当链表长度到达一个阈值8，会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值6时（防止频繁转换），又会将红黑树转换回单向链表提高性能。
  4. 检查链表长度转换成红黑树之前，还会先检测当前数组是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组。

扩容后的元素处理：

元素在重新计算hash之后，n变为2倍，那么n-1的mask范围在高位多1bit，因此新的index就会发生这样的变化：

值新增的那个bit是0的，索引没变。是1，索引变成“原索引+oldCap”。

省去了重新计算hash值的时间，同时由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

为什么使用链表+数组

链表可以解决哈希冲突问题

⽤LinkedList代替数组结构可以吗？

在源码中

Entry[] table=new Entry[capacity];
// entry就是一个链表的节点

进行替换

List<Entry> table=new LinkedList<Entry>();

可以替换，但是数组效率最高。在HashMap中，定位节点的位置是利⽤元素的key的哈希值对数组⻓度取模得到。

ArrayList，底层也是数组，查找也快，为什么不⽤ArrayList?

因为采⽤基本数组结构，扩容机制可以⾃⼰定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率⾼。 ⽽ArrayList的扩容机制是1.5倍扩容。

为什么不一开始就使用红黑树

因为红⿊树需要进⾏左旋，右旋，变⾊这些操作来保持平衡，⽽单链表不需要。
当元素⼩于8个当时候，此时做查询操作，链表结构已经能保证查询性能。
当元素⼤于8个的时候，此时需要红⿊树来加快查询速度，但是新增节点的效率变慢了。

因此，如果⼀开始就⽤红⿊树结构，元素太少，新增效率⼜⽐较慢，影响性能。

HashMap为什么用红黑树而不用其他的树

相比于B/B+树

B/B+树多用于外存上时，B/B+也被成为一个磁盘友好的数据结构。

如果用B/B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面，这个时候遍历效率就退化成了链表。

相比于AVL树

AVL树是一种高度平衡的二叉树，为了维持这种高度的平衡，每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。

红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价较大，所以效率不如红黑树。

HashMap 多线程操作导致死循环问题

JDK7中对链表采用头插法（效率高一些），多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8采用了尾插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。

并且尾插法将遍历链表，获取链表元素个数，方便判断是否应该树化

不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。
并发环境下，推荐使用 ConcurrentHashMap 。

HashMap 的 length 为什么是 2 的整数次方

  1. 当 length 为 2 的 n 次方时，计算bucket位置时h & (length – 1) 相当于对 length 取模，位运算效率高。
  2. 每次扩容时都是翻倍。
  3. 如果 length 为 2 的次幂，则 length – 1 转化为二进制必定是 11111……的形式，在与 h 的二进制进行与操作时效率会非常的快，而且空间不浪费。

一般用什么作为key值

⼀般⽤Integer、String。

String更好

  • String是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。
  • String很规范的覆写了hashCode()以及equals()⽅法。

解决哈希冲突的方法有哪些

开放定址法：我们在遇到哈希冲突时，去寻找一个新的空闲的哈希地址。

  • 线性探测法：当我们的所需要存放值的位置被占了，我们就往后面一直加1并对m取模直到存在一个空余的地址供我们存放值。
  • 平方探测法：当我们的所需要存放值的位置被占了，会前后寻找。

再哈希法：同时构造多个不同的哈希函数，等发生哈希冲突时就使用第二个、第三个……等其他的哈希函数计算地址，直到不发生冲突为止。

拉链法：将所有哈希地址相同的记录都链接在同一链表中。

实现一个自定义的class作为Hashmap的key

  1. 重写hashcode和equals方法
  2. 设计一个不变的类

HashMap 常见的遍历方式有哪些

HashMap 遍历从大的方向来说，可分为以下 4 类：

  1. 迭代器（Iterator）方式遍历；
  2. For Each 方式遍历；
  3. Lambda 表达式遍历（JDK 1.8+）;
  4. Streams API 遍历（JDK 1.8+）。

每种类型下又有不同的实现方式，因此具体的遍历方式又可以分为以下 7 种：

  1. 使用迭代器（Iterator）EntrySet 的方式进行遍历；
  2. 使用迭代器（Iterator）KeySet 的方式进行遍历；
  3. 使用 For Each EntrySet 的方式进行遍历；
  4. 使用 For Each KeySet 的方式进行遍历；
  5. 使用 Lambda 表达式的方式进行遍历；
  6. 使用 Streams API 单线程的方式进行遍历；
  7. 使用 Streams API 多线程的方式进行遍历。

HashMap和HashTable的区别是什么

  • 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。
  • 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。
  • 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值
  • 初始容量大小和每次扩充容量大小的不同 ： Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
  • 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 和 HashSet 区别是什么

HashSet 底层就是基于 HashMap 实现的。大部分方法是直接调用 HashMap 中的方法。

HashMap实现了Map接口，存储键值对。HashSet实现Set接口，存储对象。

HashMap 和 TreeMap 区别

TreeMap 和HashMap 都继承自AbstractMap 。

TreeMap基于红黑树实现，HashMap基于数组+链表+红黑树实现

TreeMap能对集合中的元素根据键排序，并且能对集合内元素搜索。

LinkedHashMap的实现原理

LinkedHashMap继承于HashMap，LinkedHashMap很多方法直接继承自HashMap

它在HashMap的基础上，定义了一条双向链表，保持遍历顺序和插入顺序一致的问题。

ConcurrentHashMap

说说ConcurrentHashMap的实现原理

JDK 1.7中

ConcurrentHashMap 是由 Segment 数据结构和 HashEntry 数组结构构成，采取分段锁来保证安全性。Segment 是 ReentrantLock 重入锁

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

JDK 1.8中

JDK1.8 的实现已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作

Java 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点

Hashtable和ConcurrentHashMap的区别

  • 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用数组+链表/红黑二叉树。
  • 实现线程安全的方式（重要）：
    • JDK1.7 ，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
    • JDK1.8 ，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。
    • Hashtable(同一把锁) :使用 synchronized 对整张 Hash 表上锁来保证线程安全，效率低下。

HashMap 与 ConcurrentHashMap 的区别是什么

HashMap来自 java.util.HashMap包，ConcurrentHashMap来自java.util.concurrent包。

HashMap 不是线程安全的，而 ConcurrentHashMap 是线程安全的。

文章作者: Aiaa
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Aiaa !
Java
  目录