目录
- Java 集合概览
- Java集合底层数据结构总结
- HashMap 和 Hashtable 的区别
- HashMap 和 HashSet 区别
- ConcurrentHashMap 和 Hashtable 区别
- 补充:Arraylist 与 LinkedList 区别
Java 集合概览
从下图可以看出,在 Java 中除了以 Map
结尾的类之外, 其他类都实现了 Collection
接口。并且,以 Map
结尾的类都实现了 Map
接口。
Java集合底层数据结构总结
1. List
存储的元素是有序的、可重复的。
-
Arraylist
: Object[]
数组
-
Vector
: Object[]
数组
-
LinkedList
: 双向链表(JDK1.6 之前为循环链表,JDK1.7 取消了循环)
2. Set
存储的元素是无序的、不可重复的。
-
HashSet
:无序,唯一,基于 HashMap
实现的,底层采用 HashMap
来保存元素
-
LinkedHashSet
: LinkedHashSet
是 HashSet
的子类,并且其内部是通过 LinkedHashMap
来实现的。有点类似于 LinkedHashMap
其内部是基于 HashMap
实现一样
-
TreeSet
:有序,唯一,红黑树
3. Map
-
HashMap
:JDK1.8之前 HashMap
由数组+链表组成的,数组是 HashMap
的主体,链表则是主要为了解决哈希冲突⽽存在的。JDK1.8以后在解决哈希冲突时有了变化, 当链表⻓度⼤于阈值(默认为8)时,将链表转化为红⿊树,以减少搜索时间
-
LinkedHashMap
: LinkedHashMap
继承⾃ HashMap
,所以它的底层仍然是基于数组和链表/红⿊树组成。另外, LinkedHashMap
在上面结构的基础上,增加了⼀条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。
-
Hashtable
: 数组+链表组成的,数组是 Hashtable
的主体,链表则是主要为了解决哈希冲突而存在的
-
TreeMap
: 红黑树
HashMap 和 Hashtable 的区别
1. 线程是否安全
HashMap
是非线程安全的。
HashTable
是线程安全的,因为 HashTable
内部的方法基本都经过 synchronized
修饰。
2. 效率
因为线程安全的问题, HashMap
要比 HashTable
效率高一点。另外, HashTable
基本被淘汰,不要在代码中使用它。
3. 对 Null key 和 Null value 的支持
HashMap
可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个。
HashTable
不允许有 null 键和 null 值,否则会抛出 NullPointerException
。
4. 初始容量大小
创建时如果不指定容量初始值
HashMap
默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。
Hashtable
默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。
5. 每次扩充容量大小
创建时如果给定了容量初始值
HashMap
会将其扩充为 2 的幂次方大小
Hashtable
会直接使用你给定的大小
6. 底层数据结构
JDK1.8以后的 HashMap
在解决哈希冲突时有了变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。
补充为什么默认值是8:在8的时候,红黑树的平均查找长度是log(N)=3,而链表的平均查找长度为8/2=4。
而 Hashtable
则没有这样的机制。
HashMap 和 HashSet 区别
HashSet
底层就是基于 HashMap
实现的。 HashSet
的源码非常非常少,因为除了 clone()
、 writeObject()
、 readObject()
是 HashSet
自己不得不实现之外,其他方法都是直接调用 HashMap
中的方法。
HashMap
HashSet
实现了 Map 接口
实现 Set 接口
存储键值对
仅存储对象
调用 put()向 map 中添加元素
调用 add()方法向 Set 中添加元素
HashMap 使用键(Key)计算 hashcode
HashSet 使用成员对象来计算 hashcode 值,对于两个对象来说 hashcode 可能相同,所以 equals()方法用来判断对象的相等性
ConcurrentHashMap 和 Hashtable 区别
ConcurrentHashMap
和 Hashtable
的区别主要体现在实现线程安全的方式上不同。
1. 底层数据结构
JDK1.7 的 ConcurrentHashMap
底层采用分段的数组+链表实现,JDK1.8 采用的数据结构跟 HashMap
1.8 的结构一样,是数组+链表/红黑二叉树。
Hashtable
和 JDK1.8 之前的 HashMap
的底层数据结构类似,都是采用数组+链表的形式。
2. 实现线程安全的方式
JDK1.7 的 ConcurrentHashMap
通过分段锁实现线程安全,先对整个桶数组进行分割分段,每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据就不会存在锁竞争,提高并发访问率。
JDK1.8 的 ConcurrentHashMap
摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized
和 CAS 来操作。 synchronized
只锁定当前链表或红黑树的首节点,整个看起来就像是优化过且线程安全的 HashMap
Hashtable
通过全表锁来实现线程安全,相当于给整个哈希表只加了一把锁, get
/ put
所有相关操作都是 synchronized
的。在多线程访问的时候,当一个线程访问或操作该对象,其他线程只能进入阻塞或轮询状态。比如某一线程使用 put
添加元素,那么其他线程不能使用 put
添加元素,也不能使用 get
,在并发场景中性能就会非常差。
补充:Arraylist 与 LinkedList 区别
1. 是否保证线程安全
ArrayList
和 LinkedList
都是不同步的,也就是不保证线程安全;
但是 Vector
是线程安全的。
2. 底层数据结构
Arraylist
底层使用的是 Object
数组
LinkedList
底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环)。
3. 插入和删除是否受元素位置的影响
ArrayList
采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行 add(E e)
方法的时候, ArrayList
会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话( add(int index, E element)
)时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
LinkedList
采用链表存储,所以对于 add(E e)
方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话( (add(int index, E element)
) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
4. 是否支持快速随机访问
ArrayList
支持快速随机访问。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index)
方法)。
而 LinkedList
不支持高效的随机元素访问。
5. 内存空间占用
ArrayList
的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间
LinkedList
的空间花费则体现在它的每一个元素都需要消耗比 ArrayList
更多的空间(因为要存放直接后继和直接前驱以及数据)。