首页  思维导图  详情

JAVA数据存储

2024-01-15 11:55:16   0  举报





AI智能生成

整理java数据结构：基础数据类型、数组、链表、哈希表、二叉树、红黑树底层原理；整理java集合框架及其底层实现。

集合

集合框架

链表

二叉树

红黑树

作者其他创作

大纲/内容

其他

Unicode

它为每种语言中的每个字符设定了统一并且唯一的二进制编码,以满足跨语言、跨平台进行文本转换、处理的要求,(其中包含了 ASCII编码)。 Java编译器默认使用Unicode编码，因此2字节可以表示所有字符。

数组和集合的关系

数组

String[]、arr、int[]、object[]

数组缺点

长度确定（初始化固定），类型固定。

数组提供方法非常有限，增删修改操作不便，效率不高。

没有现成的属性方法可用，如获取实际元素个数。

存储特点：有序可重复，无法满足无序不重复的需求。

数组创建的两种方式

固定长度

Emp[] emps = new Emp[3];

向数组中添加

Emp emp = new Emp(null, "aaa", 12, "男");
Emp emp1 = new Emp(null, "bbb", 13, "女");
Emp emp2 = new Emp(null, "cccc", 14, "男");

Emp[] emps2 = {emp,emp1,emp2}

集合：可解决数组方面的弊端

数组和集合区别

长度

数组固定

集合会改变

内容区别

数组存储同一类型

集合不一定

使用方式

集合有提供的各种方法

基础数据结构

数组

内存连续

大小固定，查找迅速，增删复杂

容易产生碎片

底层原理

数组的基础使用

底层原理

在Java中，数组是通过Java虚拟机（JVM）来实现的。在底层，数组是一个对象，由数组的长度和元素类型组成。当我们创建一个数组时，JVM在堆内存中为数组分配一段连续的空间，每个数组元素在内存中占据一定的连续空间。这使得数组的随机访问变得很快，因为我们可以根据索引直接计算出元素在内存中的位置。

数组的长度决定了需要分配的空间大小，每个数组元素占据固定大小的内存空间。对于基本数据类型，元素的内存空间大小是固定的，而对于引用数据类型，每个元素实际上存储的是对象的引用，也占据固定大小的内存空间。

在内存中，数组的第一个元素被放置在数组的起始地址处，后续元素依次排列在前一个元素之后。通过索引计算，Java可以直接访问数组中的元素，而不需要遍历整个数组。

底层原理

Java实现自定义动态数组

链表

内存地址不连续

动态调整

增删迅速，查找较慢

不会造成碎片化

底层原理

动手编写-链表（Java实现）

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

哈希表基于数组，类似于key-value的存储形式，关键字值通过哈希函数映射为数组的下标，如果一个关键字哈希化到已占用的数组单元，这种情况称为冲突。用来解决冲突的有两种方法：开放地址法和链地址法。在开发地址法中，把冲突的数据项放在数组的其它位置；在链地址法中，每个单元都包含一个链表，把所有映射到同一数组下标的数据项都插入到这个链表中。

底层原理

二叉树

二叉树前奏

深入理解二叉树（超详细）

红黑树

参看下面HashMap的底层原理

存储

8大基本类型

int （4字节）

short （2字节）

long （8字节）

byte （1字节）

float (4字节)

double (8字节)

char (2字节)

boolean

字符串类型

String

String是final的，不可变的，如果是一个可变的字符串，请尝试使用Stringbuilder

StringBuilder

速度快线程不安全

StringBuffer

线程安全速度慢

包装类型

Intrger

Double

Float

Long

Boolean

Character

Short

集合类型

概览

Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；
另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

概述

存储引用类型的变量容器

每一个对象作为一个元素存在

提供的集合类位于java.util包中

继承关系

Collection

List

ArrayList

Vector

Stack

LinkedList

Set

HashSet

LinkedHashSet

TreeSet

Map

HashMap

LinkedHashMap

Properties

HashTable

TreeMap

框架图

虚线：实现；实线：继承
注：图中只列举了主要的继承派生关系，并没有列举所有关系。比方省略了AbstractList, NavigableSet等抽象类以及其他的一些辅助类

四者区别

List

(对付顺序的好帮手): 存储的元素是有序的、可重复的。

Set

(注重独一无二的性质): 存储的元素是无序的、不可重复的。

Queue

(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。

Map

(用 key 来搜索的专家): 使用键值对（key-value）存储，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

collection接口

迭代器 Iterator

见设计模式的迭代器模式

hasNext()、next()、remove()

List接口

ArrayList

有序，不唯一

适用于频繁的查找工作，线程不安全

底层原理

底层数据结构：Object[ ] 数组，不过是数组队列，所以可以动态的插入和删除。

构造方法

默认初始化方法

ArrayList list = new ArrayList();

private transient Object[] elementData;

为什么 ArrayList 的 elementData 加上 transient 修饰？

ArrayList 实现了 Serializable 接口

transient ：不希望 elementData 数组被序列化，重写了 writeObject 实现

每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。

JDK7：底层创建了长度为10的Object[]数组

JDK8：底层Object[] elementData初始化为{}，在使用时才会通过grow方法创建一个大小为10的数组。

指定容量的构造方法

指定collection元素列表

扩容机制

特性：动态数组（区别于数组的固定长度）

扩容1.5倍，扩容带来新数组的重新拷贝

JDK7：int newCapacity = (oldCapacity * 3)/2 + 1;

JDK8：int newCapacity = oldCapacity + (oldCapacity >> 1);

初始化如果不指定大小，则数组的大小为0
当大小为0时，第一次添加，则大小扩容至10
后续，再次扩容，则增加1.5倍的方式增加

扩容机制

无参构造

初始化数组为0

第一次添加扩容到10

之后1.5倍扩容

有参构造

初始化为指定容量大小

不够时，1.5倍扩容

扩容机制

默认初始容量为 10，可以在创建 ArrayList 对象时指定容量

每次扩容之后容量都会变为原来的 1.5 倍左右，左右是因为扩容公式为：新容量 = 原容量 + (原容量 >> 1)，当原容量是奇数时，会向下取整。

常用方法

增

add末尾添加

add指定位置添加

边界判定

IndexOutOfBoundsException异常

长度不足进行扩容

将当前位于该位置的元素以及所有后续元素右移一个位置。

System.arraycopy(elementData, index, elementData, index + 1, size - index);

int[] arr ={0,1,2,3,4,5,6}; System.arraycopy(arr,0,arr,3,3); 结果为：{0,1,2,0,1,2,6};

参数：原数组，原数组开始下标，新数组，新数组下标，原数组长度3；

删

remove(Object obj)

list.remove(new Integer(2));

需要删除元素，要装箱成对象

remove(int index)

System.arraycopy(elementData, index+1, elementData, index, numMoved);

list.remove(2);

按索引删除不会装箱生成对象

时间复杂度O(n)

改

set(int index , Object obj)

查

get(int index)

插入

add(int index, Object ele)

可插入null

时间复杂度O(n)

size()/indexOf()/lastIndexOf()

说一下 ArrayList 的优缺点

优点

底层数组实现(Object[] elementData)
随机访问模式，实现 RandomAccess 接口
查找速度快O(1)

支持快速随机访问

快速随机访问就是通过元素的序号快速获取元素对象（对应于 get(int index) 方法）。

缺点

插入删除需要移动后面的所有元素，O(n)

插入/删除受元素位置影响

ArrayList 采用数组存储，所以插入/删除元素的时间复杂度受元素位置的影响。比如：执行 add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。
但是如果要在指定位置 i 插入/删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的（n-i）个元素都要执行向后位/向前移一位的操作。

线程不安全

Collections 的 synchronizedList 方法将ArrayList转换成线程安全的

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");

for (int i = 0; i < synchronizedList.size(); i++) {
System.out.println(synchronizedList.get(i));
}

内存空间占用

ArrayList 的空间浪费主要体现在 list 列表的结尾会预留一定的容量空间

应用

适合查询

增删不适合

集合与数组之间的转换

集合 --->数组：toArray()

Object[] arr = coll.toArray();
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}

数组 --->集合:调用Arrays类的静态方法asList(T ... t)

List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
System.out.println(list);

底层源码分析：

LinkedList

有序，不唯一

线程不安全

底层原理

底层数据结构：双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）

对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储

构造方法

LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性，默认值为null

扩容机制：由于是双向链表，所以不存在容量问题，不需要扩容

说一下 LinkedList的优缺点

优点

缺点

插入/删除不受元素位置影响

LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），时间复杂度为 O(1)；
如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o)），时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。

不支持快速随机访问

内存空间占用

LinkedList 的空间花费体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

ArrayList 和 LinkedList 的区别是什么？

数据结构

ArrayList 是动态数组

LinkedList 是双向链表

随机访问效率

ArrayList：O(1)

LindedList：O(n)

增加和删除效率

ArrayList：O(n)

LindedList：O(1)

内存空间占用

LinkedList多两个引用

线程安全

都是线程不安全的

应用

在项目中一般是不会使用到 LinkedList，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好。

在哪里可以用到LinkedList

生产者消费者

生产者向链表尾部添加消息

linkedList.addLast

消费者从链表头部取出消息

linkedList.removeFirst()

Vector

有序，不唯一

方法由synchronized的修饰，线程安全

~~作为List接口的古老实现类；线程安全的(synchronized修饰)，效率低；底层使用Object[] elementData存储~~

底层原理

底层数据结构：Object[ ] 数组

~~jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。在扩容方面，默认扩容为原来的数组长度的2倍。~~

构造方法

扩容机制：初始化大小为10，后续扩容默认为2倍。
也可通过构造方法Vector(int initialCapacity, int capacityIncrement)自定义初始化，以及扩容大小

扩容机制

无参构造

初始化为10

之后2倍扩容

有参构造，之后2倍扩容

Stack

vector的子类，底层实现和vector一样

pop方法会直接移除最后一个元素

ArrayList 和 Vector 的区别是什么？

线程安全

Vector线程安全的

性能

因为加Synchronized锁，性能比ArrayList 低

扩容

ArrayList扩容1.5倍

Vector扩容2倍

应用

多线程

适合查询

增删不适合

Set接口

Set接口中没额外定义新的方法，使用的都是Collection中声明过的方法。

无序性和不可重复性的含义

无序性：不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。

不可重复性：添加的元素按照 equals() 判断时，返回 false，需要同时重写 equals() 方法和 HashCode() 方法。

HashSet

无序，唯一

线程不安全

对于 HashSet 中保存的对象，请注意正确重写其 equals 和 hashCode 方法，以保证放入对象的唯一性。

底层原理

底层数据结构：哈希表（基于HashMap实现）

底层实现：HashMap，key为set元素，value为空的Object对象。

如何检查重复

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

可以存放一个null值，但是只能有一个

应用

应用场景：不需要保证元素插入和取出顺序的场景

HashSet与HashMap的区别

HashSet

实现Set接口

仅存储对象

value使用PRESENT占位（Dummy）

调用add（）方法向Set中添加元素，调用HashMap的put

源代码：同HashMap

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

HashMap

实现了Map接口

存储键值对

调用put（）向map中添加元素

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

如果两个对象相等，则hashcode一定也是相同的

两个对象相等,对两个equals方法返回true

两个对象有相同的hashcode值，它们也不一定是相等的

综上，equals方法被覆盖过，则hashCode方法也必须被覆盖

hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）

==与equals的区别

==，基本数据类型比较 “值”是否相等；引用类型比较的是所指向的对象的地址

equals方法，注意：equals方法不能作用于基本数据类型的变量，equals继承Object类，比较是否是同一个对象
如果没有对equals方法进行重写，则比较的是引用类型的变量所指向的对象的地址；
诸如String、Date等类对equals方法进行了重写，比较的是所指向的对象的内容。

LinkedHashSet

有序（添加），唯一

线程不安全

底层原理

HashSet的子类

底层实现：LinkedHashMap

底层数据结构：链表+哈希表，元素的插入和取出满足FIFO

保证插入读出顺序一致

遍历可以按照添加的顺序遍历

添加数据时，需要记录此数据前一个数据和后一个数据的引用

对于频繁的遍历操作，LinkedHashSet效率高于HashSet。

应用场景：保证元素的插入和取出顺序满足 FIFO 的场景

TreeSet

有序（升序），唯一

默认

线程不安全

底层原理

TreeMap

红黑树(平衡的排序二叉树)

底层数据结构：红黑树，元素有序，排序方式有自然排序和定制排序

可以照添加对象的指定属性，进行排序。

必须实现Comparable或Comparator接口

应用场景：支持对元素自定义排序规则的场景

Queue

Deque（Interface）

ArrayDeque

Queue和Deque的区别

Queue是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循FIFO。

Queue扩展了Collection的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法:
一种在操作失败后会抛出异常，另一种则会返回特殊值。

Deque是双端队列，在队列的两端均可插入或删除元素
Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类

操作失败后的处理方式

Queue

Deque

ArrayDeque和LinkedList的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。

ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。

ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。

ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。
虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

PriorityQueue（Class）

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据

PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。

PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。

PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

PriorityQueue的典型例题包括堆排序、求第K大的数、带权图的遍历等

BlockingQueue

Collections工具类

作用：操作Collection和Map的工具类

常用方法

查找、替换

排序

reverse(List)：反转 List 中元素的顺序

shuffle(List)：对 List 集合元素进行随机排序

sort(List)：根据元素的自然顺序对指定 List 集合元素升序排序

sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序

swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

同步控制（不推荐使用，线程安全集合使用JUC）

Collections 提供了多个 synchronizedXxx() 方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。
我们知道 HashSet，TreeSet，ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

使用Collections的方法修饰

synchronizedList

synchronizedMap

使用Collections集合工具的内部类

装饰器模式

通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

面试题：Collection 和 Collections的区别？

List 和 Set 的区别

都继承自Collection 接口

List接口

存储特点：存储有序、可重复数据、可存多个null值

和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，会引起其他元素位置改变

Set接口

存储特点：存储无序、不可重复的数据、只可以存一个null值

无序性≠随机性

检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。

Map接口

存储key-value对数据，类似函数y=f(x)

Map中的key：无序的、不可重复的，使用Set存储的key

一个键值对：key-value构成了一个Entry对象。

Map中的entry:无序的、不可重复的，使用Set存储所有的entry

Map中的value:无序的、可重复的，使用Collection存储value

key所在的类要重写equals()和hashCode()

value所在的类要重写equals()

HashMap

无序，唯一

线程不安全

插入慢，查询效率高

因为线程安全问题，HashMap效率比Hashtable高

key，value 都允许为 null

可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个

自定义类作为key时，key所在的类要重写equals()和hashCode()

常用方法

添加：put(Object key,Object value)

删除：remove(Object key)

修改：put(Object key,Object value)

查询：get(Object key)

时间复杂度由链表长度决定

长度：size()

遍历：keySet() / values() / entrySet()

foreach

idea：iter

HashMap底层

初始化

无参构造器HashMap map = new HashMap()；

哈希表默认长度16，加载因子0.75（数组长度达到3/4进行扩容）

JDK7：调用构造器时产生默认长度、加载因子的哈希表，while方式产生

JDK8：默认为空，在第一次添加数据时进行初始化。位运算方式产生

有参构造器HashMap(int initialCapacity, float loadFactor）

传入的值为k，初始化会是大于k的2的整数次方。如传入10，产生16的容量大小

初始容量和扩容大小

初始容量

创建时不指定容量：

不指定容量时，不会初始化容量，只会初始化一个加载因子 loadFactor；
当执行插入方法时，才会初始化容量，默认大小为 16；
之后 每次扩容时容量为原来的 2 倍

创建时指定容量：

HashMap会将其扩充为 2 的幂次方大小
若指定容量不是 2 的幂次方，则会向上寻找里的最近的 2 的幂次方大小的数）

扩容大小

至于为什么每次扩容到原来的 2 倍，一因为要 维持容量为 2 的幂次方（原因在下）。

二是因为 在扩容后进行 rehash（重新计算旧数组元素在新数组地址）时可以尽可能的减少元素位置的移动。
‌从下面一个简单的扩容示例可以看出，数组初始长度为 2 的幂次方，随后以 2 倍扩容的方式扩容，元素在
‌新表中的位置要么不动，要么有规律的出现在新表中（二的幂次方偏移量），这样会使扩容的效率大大提高。

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

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

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

除了使用 & 更加高效外，最重要的是 使用（n - 1）& hash 得到的下标位置可以均匀的散布在数组中，减少哈希冲突。
‌n若是2的幂次方，则 n-1 的二进制就是 11111***111 这样的形式，那么 (n-1) 与 hash 进行位运算不仅效率很高，
‌而且能均匀的散列，因为 1 只有和 1 进行 & 运算时结果才为 1，所以只有哈希值的 1 的位置都相同时，才会出现哈希冲突。

我们画图位运算一下。就拿数组长度为4来说，4 - 1 = 3 的二进制为 011

何时扩容

loadFactor 加载因子

loadFactor 加载因子是 控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么数组中存放的数据(entry)也就越多，
也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。

loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12
就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

threshold

threshold = capacity * loadFactor，当 Size>=threshold的时候，那么就要考虑
对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。

扩容后，会重新计算每个元素的 hash 值，使每个元素尽量放在原本的位置上。所以扩容会遍历所有元素，十分耗时。

不管是链表还是红黑树，都会进行 rehash，相当于重新 put 进 Map 中，该形成链表形成链表，该转为红黑树转为红黑树。

put 过程

首先判断数组是否为空或者长度是否为 0，是则先进行初始的扩容，默认大小为 16。

然后定位到的数组位置，若没有元素则直接插入。

如果定位到的数组位置有元素，则有如下步骤：

如果 key 相同，说明是更新元素，则直接覆盖；
如果 key 不同，说明哈希冲突了，则判断 p 是否为一个树节点；

如果是则将元素添加到红黑树上；
如果不是则遍历链表，插入到链表尾部；

详细的过程如下图：

get 过程

首先根据 hash 方法获取到 key 的 hash 值，然后通过 hash & (len - 1) 获取 key 所对应的 Node 数组下标

首先判断此结点是否为空，是则返回空；是否就是要找的值，若是则直接返回该值；否则进入第二个结点。

接着判断第二个结点是否为空，是则返回空，不是则判断此时数据结构是链表还是红黑树

链表结构进行顺序遍历查找操作，满足条件则直接返回该结点。链表遍历完都没有找到则返回空。

红黑树结构执行相应的 getTreeNode( ) 查找操作。

底层源码分析：

底层实现

JDK1.7

数组+链表

JDK7：流程分析

JDK1.8

数组+链表+红黑树

JDK8：源码分析

HashMap在jdk8中相较于jdk7在底层实现方面的不同（为什么做这几点优化）

JDK7new的时候创建长度为16的数组，
JDK8在首次调用put()方法时，底层创建长度为16的数组

节省空间

jdk7底层结构：数组+链表。
jdk8底层结构：数组+链表+红黑树。

为防止发生hash冲突，链表长度过长，将时间复杂度由O(n)降为O(logn)

当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，
此时此索引位置上的链表改为红黑树存储。树节点个数<6时再转换成链表。防止徘徊发生频繁转换。

形成链表时，（七上八下）
头插法jdk7：新的元素指向旧的元素。
尾插法jdk8：旧的元素指向新的元素。

并发环境下

JDK7可能产生死链（环）

JDK8可能产生数据丢失问题

扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，
1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；

扩容前长度16，扩容后长度32，按位与操作，与15,1111和与31，11111；
分两种情况，hash值第五位为0，位置不变；
hash值第五位为1，hash&（n-1）后，多出第五位1，所以加上旧容量的大小。

hashcode函数设计

JDK7

进行了四次异或操作

JDK8

首先获得key的hashcode是int型共32位，
用hashcode的高16位和低16位进行异或操作（^），
(n - 1) & hash 通过hash值与容量-1相与操作来定位hash值在table哈希表中的位置。

为什么这么设计？

一定要尽可能降低hash碰撞，越分散越好；

为什么HashMap的容量会小于数组长度？

算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

只用key的hashcode占用内存过大

(n - 1) & hash，如果与n正好是2的幂次，n-1满足全1，不满足全1，有零位相与始终为零，增加了碰撞概率。

HashMap底层典型属性说明

补：java中的位运算

图片流程

底层数据结构

JDK 1.7：数组+链表

JDK1.8 之前的 HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。

“拉链法”：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK 1.8：数组+链表+红黑树

JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，
如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
因为红黑树是一颗自平衡的二叉查找树，查找效率高。由于平衡二叉树不能自平衡，调整所需的次数比红黑树多，所以采用红黑树；

当hash表的一条链表长度 > 8 && 数组(hash表)的长度 >= 64
链表会转化为红黑树(树化)

若hash表的一条链表长度 > 8 && 数组(hash表)长度 > 64
数组(hash表)将扩容值原来的两倍

若当一个红黑树中的节点 <= 6 时会转回链表。(剪枝)

什么时候链表会变成红黑树

当一个桶中的元素>8
并且哈希桶桶的个数>=64

什么时候红黑树会变成链表

当红黑树中的节点<=6时
会转换成链表

调用位置

移除节点时会判断是否需要转换成链表

扩容时，移动到新的桶时会判断是否需要转换成链表

什么是红黑树

从 2-3-4 树说起

2-3-4 树是阶数为 4 的 B树（Balance Tree），这种结构主要用于查找，可以把搜索元素均分，从而达到 O(log n) 的复杂度。

2-3-4 树是一颗阶数为 4 的 B树，所以它会存在：2节点、3节点、4节点。

2节点中存放着一个 key[x]，两个指针，分别指向小于 x 的子节点和大于 x 的子节点；
3节点中存放着两个 key[x, y]，三个指针，分别指向小于 x 的子节点，介于 x-y 之间的子节点和大于 y 的子节点；
4节点以此类推。

2-3-4 树到红黑树的转化

红黑树是对概念模型2-3-4树的一种实现，由于直接进行不同节点间的转化会造成较大的开销，
所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。

2-3-4树中的 2节点对应着红黑树中的黑色节点，而2-3-4树中的非2节点是以红节点+黑节点的方式存在，
红节点的意义是与黑色父节点结合，表达着2-3-4树中的 3，4节点。

先看2-3-4树到红黑树的节点转换。2节点直接转化为黑色节点；3节点这里可以有两种表现形式，
左倾红节点或者右倾红节点。而 4节点被强制要求转化为一个黑父带着左右两个红色儿子。

我们研究的主体是 2-3树（原因会在后文给出），并且是2-3树中较为特殊的一种转化--左倾红黑树。
顾名思义，左倾红黑树限制了如果在树中出现了 红色节点，那么这个节点 必须是左儿子。

对于红黑树转2-3树，只需要把 左倾红黑树中的红色节点顺时针旋转45°，
使其与父节点平行，然后再将它们看作一个整体即可：

所以，红黑树其实就是对概念模型2-3树（或者2-3-4树）的一种实现

红黑树

红黑树有五条定义：

节点颜色有红色和黑色；
根节点必须为黑色；
所有叶子节点都是黑色；
任意节点到叶子节点经过的黑色节点数量相同；
不会有连续的红色节点；

左倾红黑树的插入

对于左倾红黑树的插入一共有三种情况

情况一：待插入元素比黑父大，插在了黑父的右边，而黑父左边
是红色儿子。这种情况会导致在红黑树中 出现右倾红节点。

这时需要进行调整，将原本红色的左右儿子染黑，再将黑父染红。

情况二：待插入元素比红父小，且红父自身就是左倾。这时
红父和待插入元素同时靠在了左边，形成了 连续的红节点。

这种情况我们需要用两步来调整。由于我们插入的是红色节点，其实不会破坏黑色
完美平衡，所以要注意的是 在旋转和染色的过程种继续保持这种完美黑色平衡。

首先对红父的父亲进行一次右旋，这次右旋不会破坏黑色平衡，但是也没有解决连续红色的问题。
接下来 将12所在节点与15所在节点交换颜色，为了消除连续红色，并且这个操作依旧维持了黑色平衡。
现在我们已经得到了情况一的场景，直接按情况一处理即可。

情况三：待插入元素比红父大，且红父自身就是左倾。这时插入的节点 形成了一个右倾的红节点。
这只需要将红父进行一次左旋，就能使得右倾红节点变为左倾，现在出现了连续的左倾红节点，按情况二处理即可。

可以看到，左倾红黑树的插入 最多只需要操作三次即可将红黑树调整平衡，效率是很高的。

扩容机制

第一次添加：
哈希桶（hash表）初始化为16
负载因子默认值为0.75

后续扩容
当增加的节点数 >= 当前的hash表长 * 0.75
(该节点不一定是添加在数组上，也可以是链表上)
就扩容值原来的两倍

hashMap的死循环问题

JDK8-在多线程的情况下，红黑树的节点r=r.parent.parent
所以查找根节点死循环

JDK7-多线程情况下，两个HashMap扩容
最后会导致链成循环的，造成死循环

遍历方式

通过遍历keySet获取key的集合，从而获取对应的vlues值

通过迭代器去遍历keySet

通过遍历entrySet获取key或value

通过迭代器去遍历entrySet

通过遍历Values获得所有value的集合

通过迭代器去遍历Vaules

LinkedHashMap

有序（添加），唯一

非线程安全

底层结构

LinkedHashMap内部提供了Entry

HashMap+LinkedList

哈希+双向链表

在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。

保证在遍历map元素时，可以照添加的顺序实现遍历。

对于频繁的遍历操作，此类执行效率高于HashMap。

TreeMap

有序（升序，唯一）

非线程安全

底层数据结构：红黑树

按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。

key所属的类实现Comparable接口

key必须实现comparable接口，否则会抛出异常

TreeMap 和 HashMap 都继承自AbstractMap ，但是需要注意的是 TreeMap 它还实现了 NavigableMap 接口和 SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。例如：返回集合中小于大于某一值的元素等类似操作。
实现 SortedMap 接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器（自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。）。

Hashtable

无序，唯一

线程安全（方法都经过 synchronized 修饰），效率低；

实现线程安全的方式

使用 synchronized 来保证线程安全，因为是全局锁，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能
会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大；

不能存储null的key和value

任何非null对象均可作为key或value，Hashtable 不允许有 null 键和 null 值，编译不报错，运行时会报异常NullPointerException

底层数据结构：数组+链表

链表解决hash冲突

扩容机制

初始化容量为11

之后每次table扩容为原来的2n+1

创建时不指定容量：默认大小为11，之后每次扩容时容量为原来的2n+1
创建时指定容量：Hashtable直接使用给定的大小

基本被淘汰，不要在代码中使用

Properties

hashTable的子类，线程安全

常用来处理配置文件。key和value都是String类型

注意点：key和value 都不能为空

ConcurrentHashMap

无序，唯一

key，value 都不允许为 null

二义性问题

假设 ConcurrentHashMap 允许插入 null，那么此时会有二义性问题：

value 没在集合中，所以返回 null；
value 本身就是 null，所以返回它本身的 null 值；

这就是 ConcurrentHashMap 的二义性问题，那为什么 HashMap 就不怕二义性问题呢？

可证伪的 HashMap

HashMap 的设计是给单线程使用的，所以如果查询到了 null 值，我们可以通过 containsKey(key)
方法来区分这个 null 值是集合中没有这个 key，还是这个 key 的 value 就是 null：

若 containsKey 返回 false，那说明集合中没有这个 key；
若 containsKey 返回 true，则说明这个 key 的 value 就是 null；

这样 HashMap 的二义性就通过 containsKey() 方法得到了解决。

不可证伪的 ConcurrentHashMap

ConcurrentHashMap 就不一样了，因为它是设计在多线程下使用的，所以它的情况更加复杂。

假设 ConcurrentHashMap 可以存入 null 值，如果有一个线程 T1 查询到了 null 值，它也想通过
containsKey(key) 方法来判断这个值到底是哪种情况，我们来看看是否会有二义性问题。

因为 ConcurrentHashMap 是在并发场景下使用的，所以假设在 T1 调用 containsKey 方法后，
另一个线程 T2 立马插入了一个 key 为 null 的值，这样便使得 T1 的返回结果为 true。

发现问题了吗？T1 返回 true，那它会认为它之前读取到的 value 就是为 null，认为之前存在这个 key。

但实际上，在 T1 查询到 null 值的时候，这个 null 值还没被添加进去，正确的答案应该是：之前不存在这个 key 。

所以，并发场景下，如果 key、value 允许为 null，是存在二义性的。

线程安全

ConcurrentHashMap 实现线程安全通过 synchronized 和 CAS 来保证

例如在初始化容量、判断桶是否为空都是通过 CAS 实现，不用加锁，效率高；

在需要操作链表或红黑树时，使用 synchronized 加锁，不过也只是锁某个桶，只要不发生哈希冲突，就不会阻塞；

实现线程安全的方式

JDK 1.7

ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。
但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

底层具体实现：

JDK 1.8

摒弃了 Segment 的概念，不再是之前的 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。
不过，Node 只能用于链表的情况，红黑树的情况需要转为 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。

底层具体实现：

并发控制使用 synchronized 和 CAS 来操作。

在初始化容量、判断桶是否为空等都是通过 CAS 实现，不用加锁，效率高；

在需要操作链表或红黑树时，使用 synchronized 加锁，不过也只是锁某个桶，只要不发生哈希冲突，就不会阻塞；

synchronized 只锁定当前链表或红黑树的首节点，这样只要 hash 不冲突，就不会产生影响其他操作，效率提高了很多。

底层数据结构

JDK 1.7：(Segment)分段数组+链表

jdk1.7

通过分段锁+可重入所实现线程安全

结构为：数组+链表

结构

一个segments里面是一个小的hashMap，内置自己的计数器
每一个线程对hashmap操作，会锁住segments，所以叫做分段锁
并发度一定后，会对segments内置的小HashMap进行扩容

内部机制

有多少并发量，创建多少个segments

使用可重入锁对segments上锁

JDK 1.8：(Node)数组+链表+红黑树

jdk1.8

通过volatile+synchronized锁节点+CAS操作实现线程安全

底层结构：数组+链表+红黑树

内部结构

添加元素通过对每一个桶的头结点加锁
桶的个数，说明了他的并发量
计数，通过baseCount+counterCells数组实现——为了提供并发量

说说ConcurrentHashMap解决了什么问题

JDK7HashMap出现的多线程死链问题（环）

JDK8改进JDK7由头插法改为尾插法，多线程场景下存在数据丢失问题

提高HashMap的并发安全性

解决

见：读操作get为什么是线程安全的

JDK7中的ConcurrentHashMap

segment分段锁

哈希桶数组包含多个segment，一个segment包含多个HashEntry（桶）

segment上锁不影响其他segment操作

segment继承ReentrantLock

value值volatile修饰

访问可见性

底层用数组+链表实现

get操作

根据 key 计算出 hash 值定位到具体的 Segment ，再根据 hash 值获取定位 HashEntry 对象，并对 HashEntry 对象进行链表遍历，找到对应元素。

volatile 可以保证内存可见性，所以不会读取到过期数据

put操作

先定位到相应的 Segment

获取对象锁成功

定位分段内的桶下标

遍历链表内容

key 已存在看是否覆盖value

key不存在头插法插入

尝试获取锁失败

尝试自旋获取锁

循环式的判断对象锁是否能够被成功获取，直到获取到锁才会退出循环，防止执行 put 操作的线程频繁阻塞

重试的次数达到一定次数改为阻塞锁

ConcurrentHashMap 的并发度是什么？

程序不产生锁竞争的最大线程数

JDK7里是segment的数量

过大，可以在一个segment内访问，变成两个segment，命中效率降低

过小，容易产生锁竞争

JDK8里并发度等于数组的大小

JDK8中的ConcurrentHashMap

采用更细粒度的锁，锁住桶数组中桶节点

使用CAS+Synchronized方式，保证线程并发安全

JDK8对Sychronized做大量优化后相对ReentrantLock可以减少内存开销。

因为只对桶下标进行上锁。ReentrantLock对每个节点都需要通过继承 AQS 来获得同步支持

底层使用数组+链表+红黑树实现

提升查询效率

数据添加：由JDK7的头插法改为尾插法

尾插法的优势

初始化：由饿汉式改为懒汉式

饿汉式创建非常消耗资源

get操作

get，无锁操作（仅需要保证可见性，除Treebin的读写锁），扩容过程中 get 操作拿到的是 ForwardingNode 它会让 get 操作在新table 进行搜索

get 流程

根据 key 计算出 hash 值，判断哈希表table为空

返回null

如果读取的bin头节点为null

返回null

如果是链表结构，就到链表中查询

如果是红黑树结构，就从红黑树里面查询

读操作get为什么是线程安全的

读操作一般不加锁(TreeBin的读写锁除外)，读写操作可并行；因为C13Map的写操作都要获取bin头部的syncronized互斥锁，能保证最多只有一个线程在做更新，单线程写、多线程读的并发安全性的问题。

如果读取的bin是一个链表,
头节点是个普通Node

如果正在发生链表向红黑树的treeify工作，因为treeify本身并不破坏旧的链表bin的结构，
只是在全部treeify完成后将头节点一次性替换为新创建的TreeBin，可以放心读取。

如果正在发生resize且当前bin正在被transfer，因为transfer本身并不破坏旧的链表bin的结构，
只是在全部transfer完成后将头节点一次性替换为ForwardingNode，可以放心读取。

扩容期间hash桶查询数据会发生什么？

扩容前，扩容中可以访问原数组

正在迁移的hash桶

迁移形成的链是复制的，而非移动，复制不影响原数组的遍历，不会阻塞get操作

扩容完成的

头结点的hash 为负数表示整个数组在扩容

头结点标记为ForwardNode

转发到新数组进行查询

如果其它线程正在操作链表，在当前线程遍历链表的任意一个时间点，
都有可能同时在发生add/replace/remove操作。
ConcurrentHashMap 弱一致性

如果是add操作，因为链表的节点新增从JDK8以后都采用了尾插法，会多遍历或者少遍历一个tailNode。

如果是remove操作，存在遍历到某个Node时，正好有其它线程将其remove，导致其孤立于整个链表之外；
但因为其next引用未变，整个链表并没有断开，还是可以照常遍历链表直到tailNode。

如果是replace操作，链表的结构未变，只是某个Node的value发生了变化，没有安全问题。

不能保证happen before

结论：链表线性数据结构，单线程写且插入操作尾插法，并发读取是安全的；
不会存在误读、链表断开导致的漏读、读到环状链表等问题。

如果读取的bin是一个红黑树，
说明头节点是TreeBin节点。

如果正在发生红黑树向链表的untreeify操作，因为untreeify本身并不破坏旧的红黑树结构，
只是在全部untreeify完成后将头节点一次性替换为新创建的普通Node，可以放心读取。

如果正在发生resize且当前bin正在被transfer，因为transfer本身并不破坏旧的红黑树结构，
只是在全部transfer完成后将头节点一次性替换为ForwardingNode，可以放心读取。

如果其他线程在操作红黑树，在当前线程遍历红黑树的任意一个时间点，都可能有单个的其它线程发生add/replace/remove/红黑树的翻转等操作，参考红黑树的读写锁实现。

put流程

首先会判断 key、value 是否为空，如果为空就抛异常！

null区别

ConCurrentHashMap：if (key == null || value == null) throw new NullPointerException();
如果key或者value其中一个null，就报空指针异常

HashMap：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
HashMap允许存入key为null

为什么ConcurrentHashMap不能存null

在并发的情况下带来二义性

HashMap中

map.get(key)方法得到值为null

map.contains(key)方法来判断不存在还是值为null

ConcurrentHashMap中

两次调用值可能被改变

计算key的hash值

spread(key.hashCode())保证为正数

判断桶数组为空，创建桶数组

当前线程正在创建另一个线程等待

创建方式区别

JDK8仅计算size容量，懒惰式创建

JDK7直接创建数组，占用内存

判断当前数组下标是否第一次插入，为空，使用casTabAt创建Node头结点

要创建链表头节点

cas操作保证线程安全，若同时有两个线程进行同一个位置的数据添加，只有一个会成功，失败的线程进入下一次for循环。

取代分段锁思想

更细粒度的锁，cas只会对hash表的一个链表头结点上锁，不影响其他链表头的操作（一个位置一把锁）

扩容期间hash桶插入数据会发生什么？

已扩容

hash值为-1，说明为ForwardingNode，有线程正在扩容，当前线程帮忙扩容

正在扩容的头结点

synchronized锁住桶下标，doubleCheck检测是否变化

是链表，用链表方式插入

找到相同的 key

如果允许更新，进行value值的更新

没有找到

链表尾部进行添加操作（JDK8的尾插法）

链表长度大于8且table长度大于64，进行树化操作

是红黑树，用红黑树方式插入

其他线程无法获得锁，被阻塞，不能操作正在迁移的hash桶

未扩容

可直接插入

最后判断是否进行扩容操作

什么时候触发扩容？（transfer）

addCount：在调用 addCount 方法增加集合元素计数后发现当前集合元素个数到达扩容阈值时就会触发扩容

helpTransfer：扩容状态下其他线程对集合进行插入、修改、删除、合并、compute 等操作时遇到 ForwardingNode 节点会触发扩容

tryPresize：putAll 批量插入或者插入节点后发现存在链表长度达到 8 个或以上，但数组长度为 64 以下时会触发扩容

ForwardingNode

hash值MOVED=-1 ，ForwardingNode存在表示集合正在扩容状态，nextTable 指向扩容后的数组。

扩容时如果table某个bin（头结点）迁移完毕, 用 ForwardingNode 作为旧 table bin 的头结点（占位功能）

get遍历到旧table，如果头结点标识为ForwardingNode，则到新表中get遍历，不会阻塞查询操作（转发功能）

sizeCtl 属性在各个阶段的作用

新建而未初始化时

int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) +1));
this.sizeCtl = cap;

sizeCtl值为2的幂次

记录集合在实际创建时应该使用的大小

初始化过程中

U.compareAndSwapInt(this, SIZECTL, sc, -1)

将 sizeCtl 值设置为 -1 表示集合正在初始化

其他线程发现该值为 -1 时会让出CPU资源以便初始化操作尽快完成。

初始化完成后

sc = n - (n >>> 2);
sizeCtl = sc;

记录下一次扩容的阈值

正在扩容时

U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)

第一条扩容线程设置的某个特定基数

U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)

后续线程加入扩容大军时每次加 1

U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)

线程扩容完毕退出扩容操作时每次减 1

sizeCtl 用于记录当前扩容的并发线程数情况

此时 sizeCtl 的值为：((rs << RESIZE_STAMP_SHIFT) + 2) + (正在扩容的线程数) ，并且该状态下 sizeCtl < 0 。

ConcurrentHashMap 1.8 底层源码分析

初始化 initTable

从源码中可以发现 ConcurrentHashMap 的初始化是通过 自旋和 CAS 操作完成的。
里面需要注意的是变量 sizeCtl ，它的值决定着当前的初始化状态：

-1 说明正在初始化
-N 说明有N-1个线程正在进行扩容
表示 table 初始化大小，如果 table 没有初始化
表示 table 容量，如果 table 已经初始化。

put

直接过一遍 put 源码。

流程：

根据 key 计算出 hashcode 。

判断是否需要进行初始化。

即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。

如果当前位置的 hashcode == MOVED == -1，则需要进行扩容。

如果都不满足，则利用 synchronized 锁写入数据，锁首节点 Node。

如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度 ≥ 64 时才会将链表转换为红黑树。

get

get 流程比较简单，直接过一遍源码。

总结一下 get 过程：

根据 hash 值计算位置。
查找到指定位置，如果头节点就是要找的，直接返回它的 value.
如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，使用 find() 查找之。
如果是链表，遍历查找之。

面试题

说说什么是fail-fast

线程不安全集合（ArrayList、HashMap）

当前线程遍历时，结构上被另一个线程修改，抛出ConcurrentModificationException异常，不再继续遍历

原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

如何解决

使用JUC包下的集合

ConcurrentHashMap

CopyOnWriteArrayList

怎么确保一个集合不能被修改？

Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，
这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

使用注意事项

集合判空

《阿里巴巴 Java 开发手册》的描述如下：
判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式。
这是因为 isEmpty() 方法的可读性更好，并且时间复杂度为 O(1)。

绝大部分我们使用的集合的 size() 方法的时间复杂度也是 O(1)，不过，也有很多复杂度不是 O(1) 的，
比如 java.util.concurrent 包下的某些集合（ConcurrentLinkedQueue 、ConcurrentHashMap...）。

集合转 Map

《阿里巴巴 Java 开发手册》的描述如下：
在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。

原因

首先，我们来看 java.util.stream.Collectors 类的 toMap() 方法，可以看到其内部调用了 Map 接口的 merge() 方法。

Map 接口的 merge() 方法如下，这个方法是接口中的默认实现。

merge() 方法会先调用 Objects.requireNonNull() 方法判断 value 是否为空，为空则抛出异常。

集合遍历

《阿里巴巴 Java 开发手册》的描述如下：
不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

通过反编译你会发现 foreach 语法糖底层其实还是依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法。
这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast 机制。
fail-fast 机制：多个线程对 fail-fast 集合进行修改的时候，可能会抛出ConcurrentModificationException。即使是单线程下也有可能会出现这种情况，上面已经提到过。

Java8 开始，可以使用 Collection#removeIf() 方法删除满足特定条件的元素,如：

集合去重

《阿里巴巴 Java 开发手册》的描述如下：
可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。

以 HashSet 和 ArrayList 为例，两者的核心差别在于 contains() 方法的实现。

HashSet 的 contains() 方法底部依赖 HashMap 的 containsKey() 方法，时间复杂度接近 O(1)（未出现哈希冲突时）。
当我们有 N 个元素插入 Set 时，时间复杂度就接近 O(n) 。

ArrayList 的 contains() 方法是通过遍历所有元素的方法来做的，时间复杂度接近是 O(n)。
当我们有 n 个元素插入 List 时，时间复杂度就接近 O(n^2) 。

集合转数组

《阿里巴巴 Java 开发手册》的描述如下：
使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的参数是类型完全一致、长度为 0 的空数组。

toArray(T[] array) 方法的参数是一个泛型数组，如果 toArray 方法中没有传递任何参数的话返回的是 Object 类型数组。
由于 JVM 优化，new String[0] 作为 Collection.toArray() 方法的参数现在使用更好，new String[0] 就是起一个模板的作用，
指定了返回数组的类型，0 是为了节省空间，因为它只是为了说明返回的类型。

数组转集合

《阿里巴巴 Java 开发手册》的描述如下：
使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法，它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。

1. Arrays.asList() 是泛型方法，传递的数组必须是对象数组，而不是基本类型。

当传入一个原生数据类型数组时，Arrays.asList() 的真正得到的参数就不是数组中的元素，而是数组对象本身！
此时 List 的唯一元素就是这个数组，这也就解释了上面的代码。
我们使用包装类型数组就可以解决这个问题。

2. 使用集合的修改方法: add()、remove()、clear() 会抛出异常。

Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类
java.util.Arrays$ArrayList，这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

java.util.Arrays$ArrayList 内部类继承了 AbstractList<E>，并没有重写add/remove/clear 方法，
再看看 java.util.AbstractList的 add/remove/clear 方法就知道为什么会抛出 UnsupportedOperationException 了。

3. 如何正确的将数组转为 ArrayList

（1）手动实现工具类

（2）最简便的方法，直接使用 ArrayList 的构造方法创建 ArrayList

（3）使用 Java8 的 Stream (推荐)

（4）使用 Java9 的 List.of() 方法

常用集合源码分析

ArrayList

简介

ArrayList 的底层是 数组队列，相当于 动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，
应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

ArrayList继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。
在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
ArrayList 实现了 Cloneable 接口，即覆盖了函数clone()，能被克隆。
ArrayList 实现了 java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

ArrayList 和 Vector 的区别？

ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；

Vector 是 List 的古老实现类，底层使用 Object[ ]存储，线程安全的。几乎所有方法都加了 Synchronized，所以 效率很低。

ArrayList 和 LinkedList 的区别？

是否保证线程安全：