Java集合底层原理

主要属性：

//定义了一个HashMap类型的成员变量，即拥有HashMap的所有属性 private transient HashMap<E,Object> map;

特征：

1. 不可重复
2. 无序
3. 线程不安全
4. 集合元素可以是 null，但只能放入一个 null

使用场景：去重、不要求顺序

原理：底层使用 HashMap 的 key 不能重复机制来实现没有重复的 HashSet。

TreeSet

TreeSet 实现了 SortedSet 接口，意味着可以排序，它是一个有序并且没有重复的集合类，底层是通过 TreeMap 实现。TreeSet 并不是根据插入的顺序来排序，而是字典自然排序。线程不安全。

TreeSet 支持两种排序方式：自然升序排序和自定义排序。

特征：

1. 不可重复
2. 有序，默认自然升序排序
3. 线程不安全
4. 集合元素不可以为 null

原理：

TreeSet 底层是基于 treeMap（红黑树结构）实现的，可以自定义比较器对元素进行排序，或是使用元素的自然顺序。

使用场景：去重、要求排序

 LinkedHashSet

LinkedHashSet 是使用 HashSet 机制实现，它是一个可以保证插入顺序或是访问顺序，并且没有重复的集合类。线程不安全。

数据结构：数组 + 双向链表，Entry 结构：before|hash|key|value|next|after，before 和 after 用于维护整个双向链表。

特征：

1. 集合元素不可以为 null；
2. 线程不安全。

原理：

LinkedHashSet 底层使用了 LinkedHashMap 机制（比如 before 和 after），加上又继承了 HashSet，所以可以实现既可以保证迭代顺序，又可以达到不出现重复元素。

使用场景：去重、需要保证插入或者访问顺序

HashSet、TreeSet、LinkedHashSet 的区别

HashSet，TreeSet，LinkedHashSet 之间的区别：HashSet 只去重，TreeSet 去重并排序，LinkedHashSet 去重并保证迭代顺序。

Queue

主要属性：

• initialCapacity：初始容量，默认 16，2 的 N 次方。
• loadFactor：负载因子，默认 0.75，用于扩容。
• threshold：阈值，等于 initialCapacity * loadFactor，比如：16 * 0.75 = 12。
• size：存放元素的个数，非 Node 数组长度。
• Node

//存储元素的数组
transient Node<K,V>[] table;
//存放元素的个数，非Node数组长度
transient int size;
//记录结构性修改次数，用于快速失败
transient int modCount;
//阈值
int threshold;
//负载因子，默认0.75，用于扩容
final float loadFactor;

 /**
 * 静态内部类，存储数据的节点 
 */
static class Node<K,V> implements Map.Entry<K,V> {
    //节点的hash值
    final int hash;
    //节点的key值
    final K key;
    //节点的value值
    V value;
    //下一个节点的引用
    Node<K,V> next;
}

特征：

1. 只允许一个 key 为 Null（多个则覆盖），但允许多个 value 为 Null
2. 查询、插入、删除效率都高（集成了数组和单链表的特性）
3. 默认的初始化大小为 16，之后每次扩充为原来的 2 倍
4. 线程不安全

使用场景：

1. 快速增删改查
2. 随机存取
3. 缓存

哈希冲突的解决方案：

1. 开放定址法
2. 再散列函数法
3. 链地址法（拉链法，常用）

put() 存储的流程（Java 8）：

1. 计算待新增数据 key 的 hash 值；

2. 判断 Node[] 数组是否为空或者数据长度为 0 的情况，则需要进行初始化；

3. 根据 hash 值通过位运算定计算出 Node 数组的下标，判断该数组第一个 Node 节点是否有数据，如果没有数据，则插入新值；

4. 如果有数据，则根据具体情况进行操作，如下：

   • 如果该 Node 结点的 key（即链表头结点）与待新增的 key 相等（== 或者 equals），则直接覆盖值，最后返回旧值；
   • 如果该结构是树形，则按照树的方式插入新值；
   • 如果是链表结构，则判断链表长度是否大于阈值 8，如果 >=8 并且数组长度 >=64 才转为红黑树，如果 >=8 并且数组长度 < 64 则进行扩容；
   • 如果不需要转为红黑树，则遍历链表，如果找到 key 和 hash 值同时相等，则进行覆盖返回旧值，如果没有找到，则将新值插入到链表的最后面（尾插法）；
5. 判断数组长度是否大于阈值，如果是则进入扩容阶段。【最后在进行扩容】

remove() 删除的流程（Java 8）：

1. 根据 get() 方法的方式计算出数组的下标，即定位到存储删除元素的 Node 结点；
2. 如果待删结点是头节点，则用它的 next 结点顶替它作为头节点；
3. 如果待删结点是红黑树结点，则直接调用红黑树的删除方法进行删除；
4. 如果待删结点是链表中的一个节点，则用待删除结点的前一个节点的 next 属性指向它的 next 结点；
5. 如果删除成功则返回被删结点的 value，否则返回 null。

remove() 注意事项：删除单个 key，注意返回是的键值对中的 value。

为什么使用位运算（&）来代替取模运算（%）：

1. 效率高，位运算直接对内存数据进行操作，不需转成十进制，因此处理速度非常快；
2. 可以解决负数问题，比如：-17 % 10 = -7。

HashMap 在 Java 7 和 Java 8 中的区别：

1. 存放数据的结点名称不同，作用都一样，存的都是 hashcode、key、value、next 等数据：

   • Java 7：使用 Entry 存放数据
   • Java 8：改名为 Node

2. 定位数组下标位置方法不同：

   • Java 7：计算 key 的 hash，将 hash 值进行了四次扰动，再进行取模得出；
   • Java 8：计算 key 的 hash，将 hash 值进行高 16 位异或低 16 位，再进行与运算得出。

3. 扩容算法不同：

   • Java 7：扩容要重新计算 hash
   • Java 8：不用重新计算

4. put 方法插入链表位置不同：

   • Java 7：头插法
   • Java 8：尾插法

5. Java 8 引入了红黑树，当链表长度 >=8 时，并且同时数组的长度 >=64 时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高 HashMap 的性能。

 HashTable

和 HashMap 一样，Hashtable 也是一个哈希散列表，Hashtable 继承于 Dictionary，使用重入锁 Synchronized 实现线程安全，key 和 value 都不允许为 Null。HashTable 已被高性能的 ConcurrentHashMap 代替。

主要属性：

• initialCapacity：初始容量，默认 11。
• loadFactor：负载因子，默认 0.75。
• threshold：阈值。
• modCount：记录结构性修改次数，用于快速失败。

/真正存储数据的数组
private transient Entry<?,?>[] table;
//存放元素的个数，非Entry数组长度
private transient int count;
//阈值
private int threshold;
//负载因子，默认0.75
private float loadFactor;
//记录结构性修改次数，用于快速失败
private transient int modCount = 0;

/**
* 静态内部类，存储数据的节点
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
    //节点的hash值
    final int hash;
    //节点的key值
    final K key;
    //节点的value值
    V value;
    //下一个节点的引用
    Entry<K,V> next;
}

//排序比较器
private final Comparator<? super K> comparator;
//红黑树根节点
private transient Entry<K,V> root;
//集合长度
private transient int size = 0;
//记录结构性修改次数，用于快速失败
private transient int modCount = 0;

//红黑树常量
private static final boolean RED   = false;
private static final boolean BLACK = true;

/**
* 实际存储数据的节点 
*/
static final class Entry<K,V> implements Map.Entry<K,V> {
    //节点的key值
    K key;
    //节点的value值
    V value;
    //左子树引用
    Entry<K,V> left;
    //右子树引用
    Entry<K,V> right;
    //父节点引用
    Entry<K,V> parent;
    //节点颜色（默认黑色）
    boolean color = BLACK;
}

数据结构：红黑树（高效的检索二叉树），Entry 结构：key|value|left|right|parent|color

特征：

1. key 不允许为 Null，但允许多个 value 为 Null
2. 线程不安全

put() 存储的流程：

主要分为两个步骤，构建排序二叉树和构建平衡二叉树。

构建排序二叉树，过程如下：

1. 从根节点 root 开始查找；
2. 如果 root 节点比待插入节点值小，则在 root 节点左子树查找，如果大于，则在右子树查找；
3. 递归循环步骤 2，找到合适的节点为止；
4. 把待插入节点与步骤 3 中找到的节点进行比较，如果待插入节点小于找到节点，则把待插入节点作为左子节点；否则作为右子节点。

LinkedHashMap 是使用 HashMap 机制实现。LinkedHashMap 在 HashMap 的基础上增加 before 和 after 两个属性来保证了迭代顺序。迭代顺序可以是插入顺序（默认），也可以是访问顺序。线程不安全。

主要属性：

/**
* 静态内部类，存储数据的节点
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

//头结点
transient LinkedHashMap.Entry<K,V> head;
//尾结点
transient LinkedHashMap.Entry<K,V> tail;
//排序标识，true访问顺序迭代； false插入顺序迭代（默认）
final boolean accessOrder;

特征：

1. 只允许一个 key 为 Null（多个则覆盖），允许多个 value 为 Null；
2. 线程不安全。

原理：

LinkedHashMap 继承了 HashMap，hash 算法也是跟 HashMap 一致。LinkedHashMap 在 Entry 中新增了 before 和 after 两个属性来维护双向链表的迭代顺序。Entry 的 next 属性是维护 Entry 连接顺序，而 after 是维护迭代顺序。LinkedHashMap 使用 LRU 算法实现访问顺序排序，比如 get() 操作后的元素会移动到链表末尾，从而实现按访问顺序迭代。

使用场景：保证插入和访问顺序

WeakHashMap

WeakHashMap 中的 Weak 是“弱”的含义，即弱化版的 HashMap。key 和 value 都允许为 null，线程不安全。

HashMap 与 Hashtable 的区别

1. HashMap 只允许一个 key 为 Null（多个则覆盖），允许多个 value 为 Null，HashTable 中的 key 和 value 都不允许为 null；
2. HashMap 线程不安全，效率高，HashTable 线程安全，效率低；
3. HashMap 和 Hashtable 二者都实现了 Map 接口，HashMap 是继承于 AbstractMap，HashTable 继承于 Dictionary 类；
4. 定位存储位置逻辑不一样，HashMap 是在 key.hashcode() 后使用位运算，HashTable 是在 key.hashcode() 后使用取模；
5. 判断扩容顺序不一样，HashMap 是 put() 之后扩容，HashTabel 是 put() 之前扩容；
6. 初始容量不一样，HashMap 默认 16，HashTabel 默认 11。

HashMap 与 TreeMap 的区别

1. 数据结构不一样，HashMap 基于“数组 + 单链表”实现（达到一定条件时转为红黑树），TreeMap 基于红黑树实现 ；
2. HashMap 随机存储，TreeMap 默认按 key 的字典升序排序；
3. HashMap 只允许一个 key 为 Null（多个则覆盖)，允许多个 value 为 Null，TreeMap 的 key 不允许为 Null，但允许多个 value 为 Null；
4. HashMap 效率高，TreeMap 效率低。