Java集合详解 – 小飞侠

HashSet
（无序，唯一）: 基于
HashMap
实现的，底层采用
HashMap
来保存元素
LinkedHashSet
：
LinkedHashSet
是
HashSet
的子类，并且其内部是通过
LinkedHashMap
来实现的。有点类似于我们之前说的
LinkedHashMap
其内部是基于
HashMap
实现一样，不过还是有一点点区别的
TreeSet
（有序，唯一）：红黑树(自平衡的排序二叉树)

再来看看
Map
接口下面的集合。

2.2.14.3. Map

HashMap
： JDK1.8 之前
HashMap
由数组+链表组成的，数组是
HashMap
的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap
：
LinkedHashMap
继承自
HashMap
，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，
LinkedHashMap
在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
Hashtable
：数组+链表组成的，数组是
HashMap
的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap
：红黑树（自平衡的排序二叉树）

2.ArrayList和LinkedList的底层实现和区别？

回答：ArrayList底层使用的是

Object

数组；LinkedList底层使用的是

双向

链表

数据结构。

ArrayList:增删慢、查询快，线程不安全，对元素必须连续存储。

LinkedList:增删快，查询慢，线程不安全。

内存空间占用：

ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

追问：说说ArrayList的扩容机制？

回答：通过阅读ArrayList的源码我们可以发现当以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个

空数组

。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为

10

。当插入的元素个数大于当前容量时，就需要进行扩容了，

ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右

。

3.HashMap的底层实现？扩容？是否线程安全？

回答：在jdk1.7之前

HashMap是基于数组和

链表

实现的，而且采用头插法。

而jdk1.8 之后在解决

哈希冲突时有了较大的变化，当

链表

长度大于阈值（默认为 8）（将

链表

转换成

红黑树

前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为

红黑树

）时，将

链表

转化为

红黑树

，以减少搜索时间。采用尾插法。

HashMap默认的初始化大小为 16。当HashMap中的

元素个数之和

大于负载因子*当前容量的时候就要进行扩充，容量变为原来的 2 倍。（这里注意不是数组中的个数，而且数组中和链/树中的所有元素个数之和！）

注意：我们还可以在预知存储数据量的情况下，提前设置初始容量（初始容量 = 预知数据量 / 加载因子）。这样做的好处是可以减少 resize() 操作，提高 HashMap 的效率

HashMap是

线程不安全

的，其主要体现：

1.在jdk1.7中，在多线程环境下，扩容时会造成

环形链

或数据丢失。

2.在jdk1.8中，在多线程环境下，会发生

数据覆盖

的情况。

详解：

在多线程环境下，如果线程 1 检查完了 hash 没有碰撞，要进行插入时， CPU 时间片使用完毕，此时它被挂起，线程 2 开始跑，此时线程 2 经过 hash 之后得到的值和线程 1 的 hash 值一样，线程 2 将值插入进去，线程 1 恢复运行，因为前面检查了 hash 碰撞，此时插入时不再做任何检查，直接将值插入，那么线程 2 插入的值就被覆盖掉了。

HashMap 之所以发生数据覆盖的问题，

最主要的原因在于它没有加锁，所以在多线程环境下会发生数据覆盖问题。

追问：HashMap扩容的时候长度为什么是2的n次幂？

回答：数组下标的计算方法是

（n-1）& hash，取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作

（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。并且

采用二进制位操作 &，相对于%能够提高运算效率

，这就解释了 HashMap 的长度为什么是2的幂次方。

为了

能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀

。数组下标的计算方法是“
(n - 1) & hash
”。（n代表数组长度）。扩容不需要全部重新进行定位，直接放入新hash表原来的位置即可。

追问：HashMap的put方法说一下。

回答：通过阅读源码，可以从jdk1.7和1.8两个方面来回答

1.根据key通过哈希

算法

与与运算得出数组下标

2.如果数组下标元素为空，则将key和value封装为Entry对象（JDK1.7是Entry对象，JDK1.8是Node对象）并放入该位置。

3.如果数组下标位置元素不为空，则要分情况

(i)如果是在JDK1.7，则

首先会判断是否需要扩容

，如果要扩容就进行扩容，如果不需要扩容就生成Entry对象，并使用

头插法

添加到当前

链表

中。

(ii)如果是在JDK1.8中，则会先判断当前位置上的TreeNode类型，看是

红黑树

还是

链表

Node

(a)如果是

红黑树

TreeNode，则将key和value封装为一个

红黑树

节点并添加到

红黑树

中去，在这个过程中会判断

红黑树

中是否存在当前key，如果存在则更新value。

(b)如果此位置上的Node对象是

链表

节点，则将key和value封装为一个Node并通过尾插法插入到

链表

的最后位置去，因为是尾插法，所以需要遍历

链表

，在遍历过程中会判断是否存在当前key，如果存在则更新其value，当遍历完

链表

后，将新的Node插入到

链表

中，插入到

链表

后，会看当前

链表

的节点个数，如果大于8，则会将

链表

转为

红黑树

(c)将key和value封装为Node插入到

链表

或

红黑树

后，在判断是否需要扩容，如果需要扩容，就结束put方法。

追问：HashMap源码中在计算hash值的时候为什么要右移16位？

回答：我的理解是让元素在HashMap中更加均匀的分布

HashMap和Hashtable的区别

回答：

（1）

线程是否安全：

HashMap
是非线程安全的，
HashTable
是线程安全的,因为
HashTable
内部的方法基本都经过
synchronized
修饰。（如果你要保证线程安全的话就使用
ConcurrentHashMap
吧！）；

（2）

对 Null key 和 Null value 的支持：

HashMap
可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出
NullPointerException
。

（3）

初始容量大小和每次扩充容量大小的不同：

① 创建时如果不指定容量初始值，
Hashtable
默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。
HashMap
默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而
HashMap
会将其扩充为 2 的幂次方大小（
HashMap
中的
tableSizeFor()
方法保证，下面给出了源代码）。也就是说
HashMap
总是使用 2 的幂作为

哈希表

的大小,后面会介绍到为什么是 2 的幂次方。

（4）

底层数据结构：

JDK1.8 以后的
HashMap
在解决哈希冲突时有了较大的变化，当

链表

长度大于阈值（默认为 8）（将

链表

转换成

红黑树

前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为

红黑树

）时，将

链表

转化为

红黑树

，以减少搜索时间。Hashtable 没有这样的机制。

（5）

效率：

因为线程安全的问题，
HashMap
要比
HashTable
效率高一点。另外，
HashTable
基本被淘汰，不要在代码中使用它；

HashMap和TreeMap的区别？

回答：

1、HashMap是通过hash值进行快速查找的；HashMap中的元素是没有顺序的；TreeMap中所有的元素都是有某一固定顺序的，如果需要得到一个有序的结果，就应该使用TreeMap；

2、HashMap和TreeMap都是线程不安全的；

3、HashMap继承AbstractMap类；覆盖了hashcode() 和equals() 方法，以确保两个相等的映射返回相同的哈希值；

TreeMap继承SortedMap类；他保持键的有序顺序；

4、HashMap：基于hash表实现的；使用HashMap要求添加的键类明确定义了hashcode() 和equals() （可以重写该方法）；为了优化HashMap的空间使用，可以调优初始容量和负载因子；

TreeMap：基于

红黑树

实现的；TreeMap就没有调优选项，因为

红黑树

总是处于平衡的状态；

5、HashMap：适用于Map插入，删除，定位元素；TreeMap：适用于按自然顺序或自定义顺序遍历键（key）

4.Java中线程安全的集合有哪些？

Vector：就比Arraylist多了个同步化机制（线程安全）。

Hashtable：就比Hashmap多了个线程安全。

ConcurrentHashMap:是一种高效但是线程安全的集合。

Stack：栈，也是线程安全的，继承于Vector。

追问：说一下ConcurrentHashMap的底层实现，它为什么是线程安全的？

回答：在jdk1.7是

分段的数组+

链表

，jdk1.8的时候跟HashMap1.8的时候一样都是基于数组+

链表

/

红黑树

。

ConcurrentHashMap是线程安全的

（1）在jdk1.7的时候是使用分段所segment，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。

（2）在jdk1.8的时候摒弃了 Segment的概念，而是直接用 Node 数组+

链表

+

红黑树

的数据结构来实现，并发控制使用

synchronized

和

CAS

来操作。synchronized只锁定当前

链表

或红黑

二叉树

的首节点。

如何选用集合?

当我们只需要存放元素值时，就选择实现
Collection
接口的集合，需要保证元素唯一时选择实现
Set
接口的集合比如
TreeSet
或
HashSet
，不需要就选择实现
List
接口的比如
ArrayList
或
LinkedList
，然后再根据实现这些接口的集合的特点来选用。

原文链接：https://blog.csdn.net/weixin_56638151/article/details/121172734

1.Java中的集合框架有哪些？

List,Set,Map三者的区别？

集合框架底层数据结构总结