realhuang
0%

Java集合框架

发表于 更新于 分类于 Valine：
本文字数： 3.6k 阅读时长 ≈ 3 分钟

1. 快速失败(fail-fast)和安全失败(fail-safe)

快速失败：是Java集合支持的一种快速的失败检测机制，不能在并发情况下使用

原理：在遍历过程中，如果集合内元素发生过修改，则modCount将被改变，而每次遍历将检测modCount的值，如果发生变化，将抛出异常。

场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如ArrayList 类。

安全失败：在遍历时，不是直接在集合上进行遍历的，而是实现拷贝原有集合内容，在拷贝的集合上进行遍历的。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。

场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如CopyOnWriteArrayList类。

2. 有哪些实现ArrayList线程安全的方法？

  • 使用CopyOnWriteArrayList代替。
  • 通过同步机制控制ArrayList的读写。
  • Vector：Vector是一个线程安全的List,但是它的线程安全实现方式是对所有操作都加上了synchronized关键字，这种方式严重影响效率.所以并不推荐使用Vector。
  • synchronizedList：示例如下
1
2
3
4
5
6
7
8
9
10
11
12
List<String> list = Collections.synchronizedList(new ArrayList<String>());
list.add("1");
list.add("2");
list.add("3");

synchronized (list) {
    Iterator i = list.iterator(); // Must be in synchronized block
    while (i.hasNext()) {
        //foo(i.next());
        System.out.println(i.next());
    }
}

3. CopyOnWriteArrayList的原理

CopyOnWriteArrayList就是线程安全版本的ArrayList。CopyOnWriteArrayList采用了一种读写分离的并发策略。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

4. HashMap的put流程

HashMap插入数据流程图

5. HashMap查找操作

HashMap查找流程图

  1. 使用扰动函数，获取新的哈希值

  2. 计算数组下标，获取节点

  3. 当前节点和key匹配，直接返回

  4. 否则，当前节点是否为树节点，查找红黑树

  5. 否则，遍历链表查找

6. HashMap的哈希/扰动函数是怎么设计的?

HashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。

1
2
3
4
5
static final int hash(Object key) {
        int h;
        // key的hashCode和key的hashCode右移16位做异或运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

让hashcode的高16位和低16位进行异或操作，目的是为了降低哈希碰撞的概率。

*7. 为什么哈希/扰动函数能降hash碰撞？

因为key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回的是int散列值，而int值的范围是随编译器的位数变化的，在32位和64位编译器中，范围是 -2^32 - 1 —— 2^32 -1 ，这样的映射空间范围太大，内存根本存不下。所以需要对数组长度取模运算，得到的余数用来访问数组下标。

哈希/扰动函数降低hash碰撞，是通过自身的高16位和低16位进行异或操作，混合原始哈希码的高位和低位，以此来加大低位的随机性，从而降低随机性。

关于详细说明，访问 https://tobebetterjavaer.com/sidebar/sanfene/collection.html#_14-%E4%B8%BA%E4%BB%80%E4%B9%88%E5%93%88%E5%B8%8C-%E6%89%B0%E5%8A%A8%E5%87%BD%E6%95%B0%E8%83%BD%E9%99%8Dhash%E7%A2%B0%E6%92%9E

8. 为什么HashMap的容量是2的倍数呢？

  • 为了方便哈希取余，这样做可以方便位运算，效率也比 % 取余高。
  • 在扩容的时候，因为扩容的是2的倍数，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞。

9. 为什么HashMap链表转换成红黑树的阈值为8？

因为和统计学相关，节点个数为8的情况，发生概率小。

至于红黑树回转成链表设置为6是因为，如果设置为8，那么如果发生碰撞，节点的增减恰好在8附近，那么链表和红黑树会不断相互转换，影响效率。

10. HashMap为什么扩容因子是0.75

这是一种折中的考虑设置。

如果扩容因子比较大，为1，那么空间利用率高了，但是时间成本就高了。

如果扩容因子比较小，为0.5，那么空间利用率就低了。

11. HashMap的扩容机制详解

https://tobebetterjavaer.com/sidebar/sanfene/collection.html#_21-%E9%82%A3%E6%89%A9%E5%AE%B9%E6%9C%BA%E5%88%B6%E4%BA%86%E8%A7%A3%E5%90%97

12. JDK1.8对HashMap做了哪些优化？

  • 数据结构由 数组 + 链表 改成 数组 + 链表 + 红黑树 ，时间复杂度由 o(n) 下降到 o(logn)
  • 链表由头插法改成尾插法。因为头插法在扩容时链表会发生反转，多线程环境下容易形成环。
  • 扩容rehash。1.7时需要重新hash计算位置，1.8则不用，新的位置不变或者使用索引+新增容量大小。

13. 手动实现一个HashMap

https://tobebetterjavaer.com/sidebar/sanfene/collection.html#_23-%E4%BD%A0%E8%83%BD%E8%87%AA%E5%B7%B1%E8%AE%BE%E8%AE%A1%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AAhashmap%E5%90%97

14. HashMap在多线程环境下会出现哪些问题？

  • 同时有get和put的时候，可能出现get为空。如果在put的时候，出现了扩容时，会导致rehash（1.7时重新计算位置，1.8时可能使用索引+新增容量）。
  • 在1.7时，链表的头插法可能在多线程环境下出现环形链表。
  • 同时put可能导致元素缺失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。

15. 如何解决HashMap线程不安全的问题？

  • 使用ConcurrentHashMap，是通过加synchronized 实现的，粒度比较粗。
  • Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
1
private Map map=Collections.synchronizedMap(new HashMap());
  • ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized

详解ConcurrentHashMap 在1.7和1.8的区别的原理：https://blog.csdn.net/m0_55611144/article/details/126223849

https://tobebetterjavaer.com/sidebar/sanfene/collection.html#_26-%E8%83%BD%E5%85%B7%E4%BD%93%E8%AF%B4%E4%B8%80%E4%B8%8Bconcurrenthashmap%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%90%97

16. HashMap 内部节点是有序的吗？

无序的。如果要有序，可以使用TreeMap或LinkedHashMap。

欢迎关注我的其它发布渠道