整体框架图

Java容器

aHR0cHM6Ly9pLmxvbGkubmV0LzIwMjAvMDMvMjMvRGdsWm44THlTb0ZxY3Z3LnBuZw.png

Collection接口

知识点整理

List,Set,Map三者的区别？

List： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象
Set：不允许重复的集合。不会有多个元素引用相同的对象。
Map：使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

Arraylist 与 LinkedList 的区别 ?

线程安全性：

ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

底层数据结构：

Arraylist 底层使用的是 Object 数组；
LinkedList 底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环）

插入和删除是否受元素位置的影响：

① 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, element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。

是否支持快速随机访问：

LinkedList 不支持高效的随机元素访问， ArrayList 支持随机元素访问。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

内存空间占用：

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

ArrayList 与 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的幂作为哈希表的大小

底层数据结构：

HashMap 在JDK1.8 以后，解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。 Hashtable 没有这样的机制。

HashMap 和 HashSet 的区别？

HashSet 底层就是基于 HashMap 实现的。

除了 clone()、writeObject()、readObject()是 **HashSet** 自己不得不实现之外，其他方法都是直接调用 **HashMap** 中的方法。

注意： HashSet使用成员对象来计算hashcode值，对于对象来说 hashcode 可能相同，故用 equals() 来判断对象的相等性

`HashMap`	`HashSet`
实现Map接口	实现Set接口
存储键值对	仅存储对象
调用 `put（）`向map中添加元素	调用 `add（）`方法向Set中添加元素
HashMap使用键（Key）计算HashCode	> HashSet使用成员对象来计算Hashcode值

HashSet如何检查重复？

将对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。

**hashCode（）**与**equals（）**的相关规定：

两个对象相等，则hashcode一定相同。
两个对象相等，对两个equals方法返回true。
两个对象有相同的hashcode值，它们也不一定相等。
故而equals方法被覆盖过，则hashCode方法也必须被覆盖。
hashCode()的默认行为是对堆上的对象产生独特值。
- 若没重写hashCode()，则该class的两个对象一定不会相等（即使两个对象指向相同的数据）

**==**与**equals**的区别：
==判断地址equals判断内容

==是判断两个变量或实例是不是指向同一个内存空间，equals是判断两个变量或实例所指向的内存空间的值是不是相同
==是指对内存地址进行比较 equals()是对字符串的内容进行比较
==指引用是否相同 equals()指的是值是否相同

HashMap的底层实现？

JDK1.8之后在解决哈希冲突时，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
Java容器知识点整理 - 图3

HashMap 的长度为什么是2的幂次方？

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来大概 40亿 的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是" (n - 1) & hash "。（n代表数组长度）。

这个算法是如何设计的呢？
我们首先可能会想到采用%取余的操作来实现。但是，重点来了：”取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方）” 并且采用二进制位操作&，相对于%能够提高运算效率
这就解释了HashMap 的长度为什么是2的幂次方。

HashMap 多线程操作导致死循环问题

主要原因在于并发下的Rehash 会造成元素之间会形成一个循环链表。不过，Jdk 1.8后解决了这个问题。
但还是不建议多线程下使用 HashMap，因为还存在其他问题如数据丢失。并发环境下推荐ConcurrentHashMap

ConcurrentHashMap 和 Hashtable 的区别？

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构：
ConcurrentHashMap
JDK1.7时底层采用 分段的数组+链表 实现
JDK1.8 采用的数据结构跟 HashMap 1.8 的结构一样，数组+链表/红黑二叉树。
Hashtable
和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式
数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

实现线程安全的方式（重要）：
① ConcurrentHashMap（分段锁）：

     - JDK1.7的时候，对整个桶数组进行了分割分段(`Segment`)，每把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
     - JDK1.8 的时候已经`摒弃了Segment`的概念，而是直接用** Node 数组+链表+红黑树**的数据结构来  实现，并发控制使用 `synchronized `和 `CAS `来操作。

（JDK1.6以后对 synchronized锁做了很多优化）虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
② Hashtable(同一把锁) ：
使用 synchronized 来保证线程安全，效率非常低下。

           - 一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态

JDK1.7的ConcurrentHashMap

Java容器知识点整理 - 图4
JDK1.8的ConcurrentHashMap

Java容器知识点整理 - 图5

ConcurrentHashMap线程安全的具体实现方式/底层具体实现

JDK1.7（上面有示意图）

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
ConcurrentHashMap是由 Segment数组结构和 HashEntry数组结构组成。
Segment实现了 ReentrantLock， Segment是一种可重入锁，扮演锁角色。HashEntry存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap里包含一个 Segment数组。Segment的结构和HashMap类似，是一种数组和链表结构，一个 Segment包含一个 HashEntry数组，每个 HashEntry是一个链表结构的元素，每个 Segment守护着一个HashEntry数组里的元素，当对 HashEntry数组的数据进行修改时，必须首先获得对应的 Segment的锁。

JDK1.8 （上面有示意图）

ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。
数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。Java 8在链表长度超过一定阈值（8）时将链表转换为红黑树。
synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率提升

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

Collection

1. List

  - Arraylist： Object数组
  - Vector：    Object数组
  - LinkedList： 双向链表   (JDK1.6之前为循环链表，JDK1.7取消了循环)

2. Set

  - HashSet（无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素
  - LinkedHashSet： LinkedHashSet 继承于 HashSet，并且其内部是通过 LinkedHashMap 来实现的。
  - TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树)

Map

  - HashMap： 
     1. JDK1.8之前`HashMap`由数组+链表组成的，数组是`HashMap`的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。
     1. JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
  - LinkedHashMap：

LinkedHashMap继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》

  - Hashtable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在
  - TreeMap： 红黑树

如何选用集合 ?

主要根据集合的特点来选用

比如我们需要根据键值获取到元素值时就选用Map接口下的集合
- 需要排序时选择TreeMap
- 不需要排序时就选择HashMap
- 需要保证线程安全就选用ConcurrentHashMap
当我们只需要存放元素值时，就选择实现Collection接口的集合
- 需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet
- 不需要就选择实现List接口的比如ArrayList或LinkedList，再根据实现这些接口的特点来选用。

Java容器知识点整理