Java集合

#Java集合| 来源: 网络整理| 查看: 265

文章目录 1. 有哪些常见集合？List2. ArrayList 和 LinkedList 的区别？3. ArrayList 的扩容机制4. ArrayList 是线程安全的吗？有哪些线程安全的 List ？ 5. CopyOnWriteArrayList 是什么？6. 快速失败(fail-fast)和安全失败(fail-safe)是什么？ Map7. HashMap 的数据结构8. 红黑树是什么？为什么不用二叉树/平衡树呢？9. 解决哈希冲突有哪些方法呢？

1. 有哪些常见集合？

集合就是一个容器，可以一次容纳多个对象。

java 中集合分为两大类：

一类是以单个方式存储元素：Collection

一类是以键值对的方式存储元素：Map

Collection 是集合 List 和 Set 的父接口。

List 集合的特点：存储的元素有序，可重复。Set 集合的特点：存储的元素无序，不可重复。在这里插入图片描述

List 2. ArrayList 和 LinkedList 的区别？

ArrayList和LinkedList的数据结构

（1）数据结构不同

ArrayList 基于数组。LinkedList 基于双向链表。

（2）从查找元素的效率来看

ArrayList 基于数组，所以它可以根据下标查找元素，时间复杂度为 O(1) 。LinkedList 基于双向链表，要沿着链表遍历元素，时间复杂度为 O(n) 。

（3）从增删元素的效率来看

ArrayList 在数组尾部增删元素，直接插入或者删除就可以了，时间复杂度为 O(1)。但是如果是在其他位置的话，就需要移动元素的位置，时间复杂度为 O(n)。LinkedList 头尾节点增删元素时间复杂度为 O(1)。其他位置都需要遍历链表，时间复杂度为 O(n)。

（4）从内存占用来看

ArrayList 基于数组，内存空间连续，省内存。数组满足局部性原理，可以提升相邻元素被访问的概率，性能好。LinkedList 基于双向链表，内存空间不连续，占内存。实际开发中一般不会使用 LinkedList ，用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且性能会更好。 3. ArrayList 的扩容机制

ArrayList 基于动态数组，初始容量为 0，当第一次添加数据的时候才会初始化容量为 10，再次扩容，容量是上次的 1.5 倍。

ArrayList的扩容是创建一个1.5倍的新数组，然后把原数组的值拷贝过去。

4. ArrayList 是线程安全的吗？有哪些线程安全的 List ？

ArrayList 不是线程安全的。

线程安全的 List：

Vector（Vector 已经被废弃了）synchronizedList （使用 Collections 的 synchronizedList 方法包装 ArrayList，然后操作包装后的 list）在这里插入图片描述

CopyOnWriteArrayList 5. CopyOnWriteArrayList 是什么？

它的名字叫 CopyOnWrite ——写时复制，已经说明了它的原理。

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

6. 快速失败(fail-fast)和安全失败(fail-safe)是什么？ ArrayList 是 fail-fast 的典型代表，表示遍历的同时不能修改，让它尽快失败，如果发现遍历的时候有人修改，就抛出并发修改异常。CopyOnWriteArrayList 是 fail-safe 的典型代表，表示遍历的同时可以修改，原理是读写分离，两个数组，一个数组用来读，一个数组用来写新元素。 Map 7. HashMap 的数据结构 1.7：数组 + 链表1.8 ：数组 + （链表 | 红黑树）

其中，数组是用来存储数据元素，链表是用来解决哈希冲突，红黑树是为了提高查询的效率。

数据元素通过映射关系，也就是散列函数，映射到数组对应下标的位置。如果发生冲突，就会从冲突的位置拉一个链表，插入冲突的元素。如果链表长度 > 8 并且数组容量 >= 64，链表就会转化为红黑树。如果红黑树节点个数 < 6 ，红黑树就会转化为链表。在这里插入图片描述

8. 红黑树是什么？为什么不用二叉树/平衡树呢？

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

每个节点要么是红色，要么是黑色；根节点永远是黑色的；所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；每个红色节点的两个子节点一定都是黑色；从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；在这里插入图片描述

之所以不用二叉树：

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的 O(n) 时间复杂度。

之所以不用平衡二叉树：

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

9. 解决哈希冲突有哪些方法呢？

HashMap 使用链表是为了解决哈希冲突，这种方法就是：

链地址法：在冲突的位置拉一个链表，把冲突的元素放进去。

除此之外，还有一些常见的解决冲突的办法：

开放定址法：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。

找到空闲位置的方法也有很多种：

线性探测法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置二次探测法: 从冲突的位置开始，第一次增加1^2个位置，第二次增加-(1^2)…，直至找到空闲的位置

再哈希法：换种哈希函数，重新计算冲突元素的地址。

【本文地址】

Java集合

Java集合

今日新闻

推荐新闻