集合（容器） - 容器知识点总结 - 《Java 程序基础》

集合概述
Collection 子接口之 List
Collection 子接口之 Set
- Comparable 和 Comparator 的区别？
- 无序性和不可重复性的含义是什么？
Map 接口

集合概述

说说 List，Set，Map 三者的区别

List（对付顺序的好帮手）：存储的元素是有序的，可重复的
Set（注重独一无二的性质）：存储的元素是无序的、不可重复的
Map（用 Key 来搜索的专家）：存储的元素是 K-V 键值对数据，Key 是无序的、不可重复的，Value 是无序的、可重复的，每个键最多映射到一个值

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

List
ArrayList：Object[] 数组
Vector：Object[] 数组
LinkedList：双向链表（JDK 1.6 之前为循环链表，JDK 1.7 取消来循环）

Set
HashSet（无序，唯一）：基于 HashMap 实现，底层采用 HashMap 保存元素，Key 存储 Set 列表内容，Value 统一为空对象
LinkedHashSet：LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 实现
TreeSet（有序，唯一）：红黑树（自平衡的排序二叉树）

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

如何选用集合？
选用集合时要结合集合的特点有针对性的选择：
需要根据键值获取元素值时选用 Map 接口下的集合。需要排序时选择 TreeMap，不需要排序时选择 HashMap，需要保证线程安全选择 ConcurrentHashMap
仅需要存放元素值时选用 Collection 接口下的集合。需要保证元素唯一时选用实现 Set 接口的集合比如 HashSet 或 TreeSet（需要排序时），不需要时选用实现 List 接口的集合比如 ArrayList 或者 LinkedList

为什么要使用集合？
当需要保存一组类型相同的数据时应该用一个容器来保存，这个容器就是数组，但是使用数组存储对象有一定的弊端：
数组大小在初始化后不可更改
数组只能按顺序获取元素值
数组不能保存具有键值映射关系的数据

Collection 子接口之 List

ArrayList 和 Vector 的区别？
ArrayList 是 List 的主要实现类，采用哈希表数据结构实现，底层使用 Object[] 数组存储，适用于频繁的查找工作，但是线程不安全
Vector 是 List 的古老实现类，采用哈希表数据结构实现，底层使用 Object[] 数组存储，是线程安全的。其线程安全主要依靠 synchronized 关键字实现
ArrayList 和 LinkedList 的区别？
是否保证线程安全？
ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构有何区别？
ArrayList 底层使用的是 Object[] 数组；LinkedList 底层使用的是 双向链表 数据结构
插入和删除是否受元素位置的影响？

ArrayList 采用数组存储，插入和删除元素的时间复杂度受元素位置的影响。例如：指向 add(E e) 方法时，ArrayList 默认将指定元素追加到此列表的末尾，这种情况时间复杂度为 O(1)。但如果要在指定位置 i 处插入和删除元素时 add(int index,E e)，因为在执行上述操作时集合中第 i 和第 i 个元素之后的 n-i 个元素都要执行向后或向前位移一位的操作，时间复杂度为 O(n-i)。
LinkedList 采用链表存储，对于 add(E e) 方法的插入，删除元素时间复杂度不受元素位置的影响近似为 O(1)，如果是要在指定位置 i 插入和删除元素时 add(int index,E e) ，因为需要先移动到指定个位置后在插入，时间复杂度近似为 O(n)
是否支持快速随机访问？
快速随机访问是指通过元素的序号快速获取元素对于 get(int index) 方法。LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。
内存空间占用区别？
ArrayList 的空间浪费主要体现在 List 列表的尾部会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArayList中元素更多的空间，每个元素都要存放直接后继（后一个）和直接前驱（前一个）以及数据
双向链表和双向循环链表
双向链表
包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点

双向循环链表
最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环

🔗 参考链接：https://juejin.cn/post/6844903648154271757

RandomAccess 接口的作用

public interface RandomAccess {
}

RandomAccess 接口中并未定义方法，它本身是一个“标识”，标识实现这个接口的类具有随机访问功能

ArrayList 扩容机制

ArrayList 使用默认构造函数创建时，初识容量为 10，此时内部 Object[] 数组仍旧为一个空数组。当真正对数组进行添加元素操作时，才真正分配容量，即向集合中添加第一个元素时，数组容量扩为 10。

当向集合中插入第 1 个元素时，执行 grow() 方法，并且满足判断条件将数组容量扩容为 10
当插入第 2 个元素时，数组大小已扩容为 10，不需要对数组进行扩容
插入第 3、4···到第 10 个元素时，依旧不进行扩容，数组容量都为 10

插入第 11 个元素时，数组容量无法满足使用，需要对数组进行扩容，扩容为原来的约 1.5 倍大小即 15 ```java public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { // 默认空元素 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认初识容量 private static final int DEFAULT_CAPACITY = 10; // 内部 Object[] 数组 transient Object[] elementData; // 集合大小 private int size; public ArrayList() {

  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

// 添加元素 private void add(E e, Object[] elementData, int s) {

  // 判断当前集合大小是否和数组大小相同，若相同则对数组进行扩容
  if (s == elementData.length)
      elementData = grow();
  // 扩容后在指定位置插入元素
  elementData[s] = e;
  // 插入完毕后集合大小+1
  size = s + 1;

}

// 对外提供的添加元素方法 public boolean add(E e) {

  modCount++;
  add(e, elementData, size);
  return true;

}

// 扩容 private Object[] grow(int minCapacity) {

  // 将数组内容拷贝到扩容后的新数组中
  return elementData = Arrays.copyOf(elementData,
                                     newCapacity(minCapacity));

}

// 默认扩容 1 位 private Object[] grow() {

  return grow(size + 1);

}

// 扩容是计算容量大小 private int newCapacity(int minCapacity) {

  // 当前数组大小
  int oldCapacity = elementData.length;
  // 新容量大小约为原大小的 1.5 倍
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 若原数组大小为空时进入判断
  if (newCapacity - minCapacity <= 0) {
      // 判断当前数组是空数组时扩容为默认大小 10
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
          return Math.max(DEFAULT_CAPACITY, minCapacity);
      if (minCapacity < 0) // overflow
          throw new OutOfMemoryError();
      return minCapacity;
  }
  // 若扩容后大小为超过 整型最大值-8 时直接返回，反之则扩容为整型最大值
  return (newCapacity - MAX_ARRAY_SIZE <= 0)
      ? newCapacity
      : hugeCapacity(minCapacity);

}

private static int hugeCapacity(int minCapacity) {

  if (minCapacity < 0) // overflow
      throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE)
      ? Integer.MAX_VALUE
      : MAX_ARRAY_SIZE;

}

} ```

Collection 子接口之 Set

Comparable 和 Comparator 的区别？

Comparable<T> 接口是出自 java.lang 包，它有一个 compareTo(T t) 方法用来排序
Comparator<T> 接口是出自 java.util 包，它有一个 compare(T o1, T o2) 方法用来排序

约定若 a>b，则返回 1，若 a<b，则返回 -1，若 a=b，则返回 0

无序性和不可重复性的含义是什么？

无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定
不可重复性是指添加的元素需经过 equals() 方法判断并返回 false

一般同时重写 equals() 方法和 hashCode() 方法

Map 接口

HashMap 的底层实现原理？

HashMap 底层是 数组+链表 结合在一起使用的。HashMap 计算 key 的 hashCode 值并再经过扰动函数处理后得到最终的 hash 值，然后通过 (n-1) & hash 判定当前元素存放的位置，如果当前位置存在元素，比较该元素与待存入的元素的 hash 值和 key 内容是否相同，如果相同则覆盖，如果不相同则通过拉链法解决冲突。

HashMap 和 Hashtable 的区别？

是否保证线程安全？

HashMap 是非线程安全的，而 Hashtable 是线程安全的。Hashtable 内部的方法基本都使用 synchronized 关键字修饰。但 Hashtable 是遗留的古老实现类，不推荐使用，建议使用同样保证线程安全的 ConcurrentHashMap

执行效率快慢？

因为线程安全的问题，HashMap 要比 Hashtable 效率高一些。

对 Null key 和 Null Value 的支持？

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

初识容量大小和每次扩容大小的不同？

创建时如果不指定容量初识值，Hashtable 默认的初识大小为 11，之后每次补充，容量变为原来的 2n+1；HashMap 默认的初始化大小为 16，之后每次补充，容量是原来的 2 倍
创建是如果指定了容量初始值，那么 Hashtable 会直接使用指定大小容量，而 HashMap 会将其扩充为 2 的幂次方大小
HashMap 的长度为什么是 2 的幂次方
为了能让 HashMap 存取高效，尽量减少碰撞，让其内部数组分配更均匀。Hash 值的范围取值区间 -2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射的比较均匀松散，通常很难出现哈希碰撞。但问题是内存无法存储长度达 40 亿的数组，所以不会直接使用这么大的哈希散列值，解决方法是用之前先做对数组的长度取模运算，得到的余数才能用来表示要存放的位置；这个算法是 (n-1) & hash，其中 n 代表数组长度
HashMap 和 HashSet 的区别？
HashSet 的源代码非常非常少，它的底层是基于 HashMap 实现的。

HashMap	HashSet
实现了 `Map` 接口	实现了 `Set` 接口
存储键值对 `K-V`	仅存储对象
调用 `put()` 向 `map` 中添加元素	调用 `add()` 向 `Set` 中添加元素
`HashMap` 使用键值 `Key` 计算 `hashCode`	`HashSet` 使用成员对象计算 `hashCode` 值，对于两个对象 `hashCode` 可能相同，所以还需要 `equals()` 方法用来判断对象的相等性

HashMap 和 TreeMap 的区别？

TreeMap 和 HashMap 均继承自 AbstractMap ，但 TreeMap 还额外实现了 NavigableMap 接口和 SortedMap 接口，所以 TreeMap 比 HashMap 额外多了对集合中的元素根据键排序的能力和对集合内元素的搜索的能力

HashSet 如何检查元素重复？

当把对象加入 HashSet 时，HashSet 会先计算对象的 hashCode 值来判断对象加入的位置是否存在元素，同时也会与其他已加入的对象的 hashCode 值作比较，如果不存在相同的 hashCode，那么 HashSet 判定对象没有重复。但是如果发现存在相同的 hashCode 值的对象，再调用 equals() 方法来检查 hashCode 相等的两个对象是否真的相同，如果两者相同，那么 HashSet 判定此对象已存在，是重复添加的对象。

== 与 equals() 的区别？

对于基本类型：== 比较的是两者的值是否相等
对于引用类型：== 比较的是两个对象是否指向堆内存中的同一个对象地址
对于引用类型：如果没有重写 equals() 方法时，则和引用类型的 == 比较逻辑一致；如果重写了 equals() 方法，则比较两个对象中内容是否相同
ConcurrentHashMap 和 Hashtable 的区别？
底层数据结构的区别？
JDK1.8 ConcurrentHashMap 采用的数据结构和 HashMap 一致，都是 数组+链表/红黑树。而 Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似，采用 数组+链表 的方式，数组是 HashMap 的主体，链表则是为了解决哈希冲突而存在的
实现线程安全方式上的区别？
JDK1.8 ConcurrentHashMap 采用 Node 数组+链表/红黑数 的数据结构实现，并发控制使用 synchronized 关键字和 CAS 原理，其整体就是优化过线程安全的 HashMap。而 Hashtable 则完全依靠 synchronized 关键字实现，并发场景下，资源竞争激烈容易造成线程阻塞或进入轮训状态

容器知识点总结

集合概述

说说 List，Set，Map 三者的区别

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

List

Set

Map

如何选用集合？

为什么要使用集合？

Collection 子接口之 List

ArrayList 和 Vector 的区别？

ArrayList 和 LinkedList 的区别？

是否保证线程安全？

底层数据结构有何区别？

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

是否支持快速随机访问？

内存空间占用区别？

双向链表和双向循环链表

双向链表

双向循环链表

RandomAccess 接口的作用

ArrayList 扩容机制

Collection 子接口之 Set

Comparable 和 Comparator 的区别？

无序性和不可重复性的含义是什么？

Map 接口

HashMap 的底层实现原理？

HashMap 和 Hashtable 的区别？

是否保证线程安全？

执行效率快慢？

对 Null key 和 Null Value 的支持？

初识容量大小和每次扩容大小的不同？

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

HashMap 和 HashSet 的区别？

HashMap 和 TreeMap 的区别？

HashSet 如何检查元素重复？

== 与 equals() 的区别？

ConcurrentHashMap 和 Hashtable 的区别？

底层数据结构的区别？

实现线程安全方式上的区别？