- 一、List,Set,Map三者的区别
- 二、Arraylist 与 LinkedList 区别
- 三、ArrayList 与 Vector 区别呢?为什么要⽤Arraylist取代Vector呢
- 四、HashMap 和 Hashtable 的区别
- 五、HashMap 和 HashSet区别
- 六、HashMap的底层实现
- 七、ConcurrentHashMap 和 Hashtable 的区别
| 修订记录 | 版本 | 是否发布 |
|---|---|---|
| 2020-01-05 | v1.0 | 是 |
一、List,Set,Map三者的区别
- List(对付顺序的好帮⼿)： List接⼝存储⼀组不唯⼀（可以有多个元素引⽤相同的对象），有
序的对象 - Set(注重独⼀⽆⼆的性质): 不允许重复的集合。不会有多个元素引⽤相同的对象。
- Map(⽤Key来搜索的专家): 使⽤键值对存储。Map会维护与Key有关联的值。两个Key可以引⽤相
同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。
二、Arraylist 与 LinkedList 区别
- 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安
全； - 底层数据结构： Arraylist 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是
双向链表数据结构（JDK1.6之前为双向循环链表，JDK1.7取消了循环。注意双向链表和双向循环链
表的区别，下⾯有介绍到！） - 插⼊和删除是否受元素位置的影响： ① ArrayList 采⽤数组存储，所以插⼊和删除元素
的时间复杂度受元素位置的影响。 - 是否⽀持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀
持。 - 内存空间占⽤： ArrayList的空 间浪费主要体现在在list列表的结尾会预留⼀定的容量空
间，⽽LinkedList的空间花费则体现在它的每⼀个元素都需要消耗⽐ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。
三、ArrayList 与 Vector 区别呢?为什么要⽤Arraylist取代Vector呢
- Vector 类的所有⽅法都是同步的。可以由两个线程安全地访问⼀个Vector对象、但是⼀个线程访问
Vector的话代码要在同步操作上耗费⼤量的时间。 - Arraylist 不是同步的，所以在不需要保证线程安全时建议使⽤Arraylist。
四、HashMap 和 Hashtable 的区别
- 线程是否安全： HashMap 是⾮线程安全的，HashTable 是线程安全的；HashTable 内部的⽅法
基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使⽤ ConcurrentHashMap
吧！）； - 效率： 因为线程安全的问题，HashMap 要⽐ HashTable 效率⾼⼀点。另外，HashTable 基本被
淘汰，不要在代码中使⽤它； - 对Null key 和Null value的⽀持： HashMap 中，null 可以作为键，这样的键只有⼀个，可以
有⼀个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有⼀个 null，
直接抛出 NullPointerException。 - 初始容量⼤⼩和每次扩充容量⼤⼩的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认
的初始⼤⼩为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化⼤⼩为16。之后
每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使⽤
你给定的⼤⼩，⽽ HashMap 会将其扩充为2的幂次⽅⼤⼩（HashMap 中的 tableSizeFor() ⽅
法保证，下⾯给出了源代码）。也就是说 HashMap 总是使⽤2的幂作为哈希表的⼤⼩,后⾯会介
绍到为什么是2的幂次⽅。 - 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了⼤的变化，当链表⻓度⼤于
阈值（默认为8）时，将链表转化为红⿊树，以减少搜索时间。Hashtable 没有这样的机制。
五、HashMap 和 HashSet区别
| HashMap | HashSet |
|---|---|
| 实现了Map接⼝ | 实现Set接⼝ |
| 存储键值对 | 仅存储对象 |
| 调⽤ put()向map中添加元素 | 调⽤ add()⽅法向Set中添加元素 |
| HashMap使⽤键（Key）计算Hashcode | HashSet使⽤成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()⽅法⽤来判断对象的相等性 |
六、HashMap的底层实现
JDK1.8之前
JDK1.8 之前 HashMap 底层是 数组和链表 结合在⼀起使⽤也就是链表散列。HashMap 通过 key 的
hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置
（这⾥的 n 指的是数组的⻓度），如果当前位置存在元素的话，就判断该元素与要存⼊的元素的 hash
值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash ⽅法。使⽤ hash ⽅法也就是扰动函数是为了防⽌⼀些实现
⽐较差的 hashCode() ⽅法 换句话说使⽤扰动函数之后可以减少碰撞。
JDK1.8之后
相⽐于之前的版本， JDK1.8之后在解决哈希冲突时有了⼤的变化，当链表⻓度⼤于阈值（默认为8）
时，将链表转化为红⿊树，以减少搜索时间。
TreeMap、TreeSet以及JDK1.8之后的HashMap底层都⽤到了红⿊树。红⿊树就是为了解决⼆叉查找树
的缺陷，因为⼆叉查找树在某些情况下会退化成⼀个线性结构。
七、ConcurrentHashMap 和 Hashtable 的区别
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的⽅式上不同。
- 底层数据结构： JDK1.7的 ConcurrentHashMap 底层采⽤ 分段的数组+链表 实现，JDK1.8 采⽤
的数据结构跟HashMap1.8的结构⼀样，数组+链表/红⿊⼆叉树。Hashtable 和 JDK1.8 之前的
HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是 HashMap 的主体，链表则是
主要为了解决哈希冲突⽽存在的； - 实现线程安全的⽅式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶
数组进⾏了分割分段(Segment)，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数
据段的数据，就不会存在锁竞争，提⾼并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的
概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，并发控制使⽤ synchronized 和
CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线
程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只
是为了兼容旧版本；② Hashtable(同⼀把锁) :使⽤ synchronized 来保证线程安全，效率⾮常
低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如
使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤ get，竞争会越来越激烈
效率越低。