JAVA数据存储
2024-01-15 11:55:16 0 举报AI智能生成
![[SSO] Cookie存储](https://po-img.processon.com/chart_image/thumb/55f6df21e4b0a8c6faeb8b5d.png)
整理java数据结构：基础数据类型、数组、链表、哈希表、二叉树、红黑树底层原理； 整理java集合框架及其底层实现。
作者其他创作
大纲/内容
Unicode
String[]、arr、int[]、object[]
长度确定（初始化固定），类型固定。
数组提供方法非常有限，增删修改操作不便，效率不高。
没有现成的属性方法可用，如获取实际元素个数。
存储特点：有序可重复，无法满足无序不重复的需求。
数组缺点
Emp[] emps = new Emp[3];
固定长度
向数组中添加
数组创建的两种方式
数组
集合：可解决数组方面的弊端
数组固定
集合会改变
长度
数组存储同一类型
集合不一定
内容区别
集合有提供的各种方法
使用方式
数组和集合区别
数组和集合的关系
内存连续
大小固定，查找迅速，增删复杂
容易产生碎片
数组的基础使用
底层原理
在Java中，数组是通过Java虚拟机（JVM）来实现的。在底层，数组是一个对象，由数组的长度和元素类型组成。当我们创建一个数组时，JVM在堆内存中为数组分配一段连续的空间，每个数组元素在内存中占据一定的连续空间。这使得数组的随机访问变得很快，因为我们可以根据索引直接计算出元素在内存中的位置。
数组的长度决定了需要分配的空间大小，每个数组元素占据固定大小的内存空间。对于基本数据类型，元素的内存空间大小是固定的，而对于引用数据类型，每个元素实际上存储的是对象的引用，也占据固定大小的内存空间。
在内存中，数组的第一个元素被放置在数组的起始地址处，后续元素依次排列在前一个元素之后。通过索引计算，Java可以直接访问数组中的元素，而不需要遍历整个数组。
Java实现自定义动态数组
内存地址不连续
动态调整
增删迅速，查找较慢
不会造成碎片化
动手编写-链表（Java实现）
链表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。
哈希表基于数组，类似于key-value的存储形式，关键字值通过哈希函数映射为数组的下标，如果一个关键字哈希化到已占用的数组单元，这种情况称为冲突。用来解决冲突的有两种方法：开放地址法和链地址法。在开发地址法中，把冲突的数据项放在数组的其它位置；在链地址法中，每个单元都包含一个链表，把所有映射到同一数组下标的数据项都插入到这个链表中。
哈希表
二叉树前奏
深入理解二叉树（超详细）
二叉树
红黑树
参看下面HashMap的底层原理
基础数据结构
其他
int（4字节）
short（2字节）
long（8字节）
byte（1字节）
float(4字节)
double(8字节)
char(2字节)
boolean
8大基本类型
在java中这两种的基本类型的精度存在问题。如果需要涉及到精确的计算（如：金融类）。请使用BigDeimal类
不建议在程序中使用char类型，除非确实需要对UTF-16代码单元进行操作
String是final的，不可变的，如果是一个可变的字符串，请尝试使用Stringbuilder
String
速度快线程不安全
StringBuilder
需要可变字符串，单线程下使用
线程安全速度慢
StringBuffer
可变字符串，多线程下使用
字符串类型
Intrger
Double
Float
Long
Boolean
Character
Short
包装类型
Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。
存储引用类型的变量容器
每一个对象作为一个元素存在
提供的集合类位于java.util包中
概述
概览
ArrayList
Stack
Vector
LinkedList
List
LinkedHashSet
HashSet
TreeSet
Set
Collection
LinkedHashMap
Properties
HashMap
HashTable
TreeMap
Map
框架图
(对付顺序的好帮手): 存储的元素是有序的、可重复的。
(注重独一无二的性质): 存储的元素是无序的、不可重复的。
(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Queue
(用 key 来搜索的专家): 使用键值对（key-value）存储，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
四者区别
外框
继承关系
见设计模式的迭代器模式
hasNext()、next()、remove()
迭代器 Iterator
有序，不唯一
适用于频繁的查找工作，线程不安全
底层数据结构：Object[ ] 数组，不过是数组队列，所以可以动态的插入和删除。
private transient Object[] elementData;
ArrayList 实现了 Serializable 接口
transient ：不希望 elementData 数组被序列化，重写了 writeObject 实现
每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。
为什么 ArrayList 的 elementData 加上 transient 修饰？
ArrayList list = new ArrayList();
JDK7：底层创建了长度为10的Object[]数组
JDK8：底层Object[] elementData初始化为{}，在使用时才会通过grow方法创建一个大小为10的数组。
默认初始化方法
指定容量的构造方法
指定collection元素列表
构造方法
特性：动态数组（区别于数组的固定长度）
JDK7：int newCapacity = (oldCapacity * 3)/2 + 1;
JDK8：int newCapacity = oldCapacity + (oldCapacity >> 1);
扩容1.5倍，扩容带来新数组的重新拷贝
初始化如果不指定大小，则数组的大小为0当大小为0时，第一次添加，则大小扩容至10后续，再次扩容，则增加1.5倍的方式增加
初始化数组为0
第一次添加扩容到10
之后1.5倍扩容
无参构造
初始化为指定容量大小
不够时，1.5倍扩容
有参构造
扩容机制
默认初始容量为 10，可以在创建 ArrayList 对象时指定容量
每次扩容之后容量都会变为原来的 1.5 倍左右，左右是因为扩容公式为：新容量 = 原容量 + (原容量 >> 1)，当原容量是奇数时，会向下取整。
add末尾添加
IndexOutOfBoundsException异常
边界判定
长度不足进行扩容
参数：原数组，原数组开始下标，新数组，新数组下标，原数组长度3；
将当前位于该位置的元素以及所有后续元素右移一个位置。
add指定位置添加
增
list.remove(new Integer(2));
需要删除元素，要装箱成对象
remove(Object obj)
list.remove(2);
按索引删除 不会装箱生成对象
remove(int index)
时间复杂度O(n)
删
改
get(int index)
查
可插入null
插入
size()/indexOf()/lastIndexOf()
常用方法
底层数组实现(Object[] elementData)随机访问模式，实现 RandomAccess 接口查找速度快O(1)
快速随机访问就是通过元素的序号快速获取元素对象（对应于 get(int index) 方法）。
支持快速随机访问
优点
ArrayList 采用数组存储，所以插入/删除元素的时间复杂度受元素位置的影响。 比如：执行 add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入/删除元素的话（font color=\"#4caf50\
插入/删除受元素位置影响
插入删除需要移动后面的所有元素，O(n)
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));}
Collections 的 synchronizedList 方法将ArrayList转换成线程安全的
线程不安全
ArrayList 的空间浪费主要体现在 list 列表的结尾会预留一定的容量空间
内存空间占用
缺点
说一下 ArrayList 的优缺点
适合查询
增删不适合
应用
Object[] arr = coll.toArray();for(int i = 0;i < arr.length;i++){ System.out.println(arr[i]);}
集合 --->数组：toArray()
List<String> list = Arrays.asList(new String[]{\"AA\
数组 --->集合:调用Arrays类的静态方法asList(T ... t)
集合与数组之间的转换
ArrayList 底层源码
底层源码分析：
底层数据结构：双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）
对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储
LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性，默认值为null
扩容机制：由于是双向链表，所以不存在容量问题，不需要扩容
LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），时间复杂度为 O(1)；如果是要在指定位置 i 插入和删除元素的话（font color=\"#4caf50\
插入/删除不受元素位置影响
不支持快速随机访问
LinkedList 的空间花费体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。
说一下 LinkedList的优缺点
ArrayList 是动态数组
LinkedList 是双向链表
数据结构
ArrayList：O(1)
LindedList：O(n)
随机访问效率
ArrayList：O(n)
LindedList：O(1)
增加和删除效率
LinkedList多两个引用
都是线程不安全的
线程安全
ArrayList 和 LinkedList 的区别是什么？
在项目中一般是不会使用到 LinkedList，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好。
linkedList.addLast
生产者向链表尾部添加消息
linkedList.removeFirst()
消费者从链表头部取出消息
生产者消费者
在哪里可以用到LinkedList
作为List接口的古老实现类；线程安全的(synchronized修饰)，效率低；底层使用Object[] elementData存储
方法由synchronized的修饰，线程安全
底层数据结构：Object[ ] 数组
jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。在扩容方面，默认扩容为原来的数组长度的2倍。
初始化为10
之后2倍扩容
有参构造，之后2倍扩容
vector的子类，底层实现和vector一样
pop方法会直接移除最后一个元素
Vector线程安全的
因为加Synchronized锁，性能比ArrayList 低
性能
ArrayList扩容1.5倍
Vector扩容2倍
扩容
ArrayList 和 Vector 的区别是什么？
多线程
List接口
Set接口中没额外定义新的方法，使用的都是Collection中声明过的方法。
无序性：不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
不可重复性：添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 HashCode() 方法。
无序性和不可重复性的含义
无序，唯一
对于 HashSet 中保存的对象，请注意正确重写其 equals 和 hashCode 方法，以保证放入对象的唯一性。
底层数据结构：哈希表（基于HashMap实现）
底层实现：HashMap，key为set元素，value为空的Object对象。
当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。
如何检查重复
可以存放一个null值，但是只能有一个
应用场景：不需要保证元素插入和取出顺序的场景
实现Set接口
value使用PRESENT占位（Dummy）
仅存储对象
调用add（）方法向Set中添加元素，调用HashMap的put
源代码：同HashMap
HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject() 是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。
实现了Map接口
存储键值对
调用put（）向map中添加元素
HashSet与HashMap的区别
如果两个对象相等，则hashcode一定也是相同的
两个对象有相同的hashcode值，它们也不一定是相等的
综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）
hashCode（）与equals（）的相关规定
==，基本数据类型比较 “值”是否相等；引用类型比较的是所指向的对象的地址
equals方法，注意：equals方法不能作用于基本数据类型的变量，equals继承Object类，比较是否是同一个对象如果没有对equals方法进行重写，则比较的是引用类型的变量所指向的对象的地址；诸如String、Date等类对equals方法进行了重写，比较的是所指向的对象的内容。
==与equals的区别
有序（添加），唯一
HashSet的子类
底层实现：LinkedHashMap
保证插入读出顺序一致
底层数据结构：链表+哈希表，元素的插入和取出满足FIFO
遍历可以按照添加的顺序遍历
添加数据时，需要记录此数据前一个数据和后一个数据的引用
对于频繁的遍历操作，LinkedHashSet效率高于HashSet。
应用场景：保证元素的插入和取出顺序满足 FIFO 的场景
默认
有序（升序），唯一
红黑树(平衡的排序二叉树)
底层数据结构：红黑树，元素有序，排序方式有自然排序和定制排序
必须实现Comparable或Comparator接口
可以照添加对象的指定属性，进行排序。
应用场景：支持对元素自定义排序规则的场景
Set接口
ArrayDeque
Deque（Interface）
Queue是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循FIFO。
Queue扩展了Collection的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
Deque是双端队列，在队列的两端均可插入或删除元素Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。
Deque
操作失败后的处理方式
Queue和Deque的区别
ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？
ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。
ArrayDeque和LinkedList的区别
PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。
PriorityQueue的典型例题包括堆排序、求第K大的数、带权图的遍历等
PriorityQueue（Class）
BlockingQueue
作用：操作Collection和Map的工具类
查找、替换
reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素升序排序
sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
排序
Collections 提供了多个 font color=\"#4caf50\
synchronizedList
使用Collections集合工具的内部类
装饰器模式
通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；
synchronizedMap
使用Collections的方法修饰
最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。
同步控制（不推荐使用，线程安全集合使用JUC）
面试题：Collection 和 Collections的区别？
Collections工具类
都继承自Collection 接口
存储特点：存储有序、可重复数据、可存多个null值
和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，会引起其他元素位置改变
无序性≠随机性
存储特点：存储无序、不可重复的数据、只可以存一个null值
检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List 和 Set 的区别
collection接口
单列集合有序集合(是否会按照插入的先后顺序来存储)有索引元素可以重复遍历方式三种 迭代器 普通for 增强for
无序没有索引不存储相同元素遍历方式 使用迭代器 使用增强for循环底层判重机制 先判断hashCode然后判断equals
一个键值对：key-value构成了一个Entry对象。
Map中的entry:无序的、不可重复的，使用Set存储所有的entry
Map中的value:无序的、可重复的，使用Collection存储value
Map中的key：无序的、不可重复的，使用Set存储的key
value所在的类要重写equals()
key所在的类要重写equals()和hashCode()
存储key-value对数据，类似函数y=f(x)
插入慢，查询效率高
因为线程安全问题，HashMap效率比Hashtable高
可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个
key，value 都允许为 null
自定义类作为key时，key所在的类要重写equals()和hashCode()
删除：remove(Object key)
时间复杂度由链表长度决定
查询：get(Object key)
长度：size()
foreach
idea：iter
遍历：keySet() / values() / entrySet()
JDK7：调用构造器时产生默认长度、加载因子的哈希表，while方式产生
JDK8：默认为空，在第一次添加数据时进行初始化。位运算方式产生
哈希表默认长度16，加载因子0.75（数组长度达到3/4进行扩容）
无参构造器HashMap map = new HashMap()；
传入的值为k，初始化会是大于k的2的整数次方。如传入10，产生16的容量大小
创建时不指定容量：不指定容量时，不会初始化容量，只会初始化一个加载因子 loadFactor；当执行插入方法时，才会初始化容量，默认大小为 16；之后 每次扩容时容量为原来的 2 倍
创建时指定容量：HashMap会将其扩充为 2 的幂次方大小若指定容量不是 2 的幂次方，则会向上寻找里的最近的 2 的幂次方大小的数）
初始容量
至于为什么每次扩容到原来的 2 倍，一因为要 维持容量为 2 的幂次方（原因在下）。
二是因为 在扩容后进行 rehash（重新计算旧数组元素在新数组地址） 时可以尽可能的减少元素位置的移动。从下面一个简单的扩容示例可以看出，数组初始长度为 2 的幂次方，随后以 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
HashMap 的长度为什么是 2 的幂次方
初始容量和扩容大小
loadFactor 加载因子是 控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。
loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。
loadFactor 加载因子
threshold = capacity * loadFactor，当 Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。
threshold
扩容后，会重新计算每个元素的 hash 值，使每个元素尽量放在原本的位置上。所以扩容会遍历所有元素，十分耗时。
不管是链表还是红黑树，都会进行 rehash，相当于重新 put 进 Map 中，该形成链表形成链表，该转为红黑树转为红黑树。
何时扩容
首先判断数组是否为空或者长度是否为 0，是则先进行初始的扩容，默认大小为 16。
然后定位到的数组位置，若没有元素则直接插入。
如果定位到的数组位置有元素，则有如下步骤：如果 key 相同，说明是更新元素，则直接覆盖；如果 key 不同，说明哈希冲突了，则判断 p 是否为一个树节点；如果是则将元素添加到红黑树上；如果不是则遍历链表，插入到链表尾部；
详细的过程如下图：
put 过程
首先根据 hash 方法获取到 key 的 hash 值，然后通过 hash & (len - 1) 获取 key 所对应的 Node 数组下标
首先判断此结点是否为空，是则返回空；是否就是要找的值，若是则直接返回该值；否则进入第二个结点。
接着判断第二个结点是否为空，是则返回空，不是则判断此时数据结构是链表还是红黑树
链表结构进行顺序遍历查找操作，满足条件则直接返回该结点。链表遍历完都没有找到则返回空。
红黑树结构执行相应的 getTreeNode( ) 查找操作。
get 过程
HashMap 底层源码
初始化
数组+链表
JDK7：流程分析
JDK1.7
数组+链表+红黑树
节省空间
JDK7new的时候创建长度为16的数组，JDK8在首次调用put()方法时，底层创建长度为16的数组
为防止发生hash冲突，链表长度过长，将时间复杂度由O(n)降为O(logn)
当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的链表改为红黑树存储。树节点个数<6时再转换成链表。防止徘徊发生频繁转换。
jdk7底层结构：数组+链表。jdk8底层结构：数组+链表+红黑树。
JDK7可能产生死链（环）
JDK8可能产生数据丢失问题
并发环境下
形成链表时，（七上八下）头插法jdk7：新的元素指向旧的元素。尾插法jdk8：旧的元素指向新的元素。
扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
HashMap在jdk8中相较于jdk7在底层实现方面的不同（为什么做这几点优化）
JDK8：源码分析
JDK1.8
进行了四次异或操作
JDK7
为什么HashMap的容量会小于数组长度？
一定要尽可能降低hash碰撞，越分散越好；
只用key的hashcode占用内存过大
(n - 1) & hash，如果与n正好是2的幂次，n-1满足全1，不满足全1，有零位相与始终为零，增加了碰撞概率。
为什么这么设计？
首先获得key的hashcode是int型共32位，用hashcode的高16位和低16位进行异或操作（^），(n - 1) & hash 通过hash值与容量-1相与操作来定位hash值在table哈希表中的位置。
JDK8
hashcode函数设计
图片流程
补：java中的位运算
HashMap底层典型属性说明
底层实现
JDK1.8 之前的 HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。
“拉链法”：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
JDK 1.7：数组+链表
JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。因为红黑树是一颗自平衡的二叉查找树，查找效率高。由于平衡二叉树不能自平衡，调整所需的次数比红黑树多，所以采用红黑树；
当hash表的一条链表长度 > 8 && 数组(hash表)的长度 >= 64链表会转化为红黑树(树化)
若hash表的一条链表长度 > 8 && 数组(hash表)长度 > 64数组(hash表)将扩容值原来的两倍
若当一个红黑树中的节点 <= 6 时 会转回链表。(剪枝)
JDK 1.8：数组+链表+红黑树
当一个桶中的元素>8并且哈希桶桶的个数>=64
什么时候链表会变成红黑树
当红黑树中的节点<=6时会转换成链表
移除节点时会判断是否需要转换成链表
扩容时，移动到新的桶时会判断是否需要转换成链表
调用位置
什么时候红黑树会变成链表
2-3-4 树是阶数为 4 的 B树（Balance Tree），这种结构主要用于查找，可以把搜索元素均分，从而达到 O(log n) 的复杂度。
2-3-4 树是一颗阶数为 4 的 B树，所以它会存在：2节点、3节点、4节点。
从 2-3-4 树说起
span style=\
我们研究的主体是 2-3树（原因会在后文给出），并且是2-3树中较为特殊的一种转化--左倾红黑树。顾名思义，左倾红黑树限制了如果在树中出现了 红色节点，那么这个节点 必须是左儿子。
对于红黑树转2-3树，只需要把 左倾红黑树中的红色节点顺时针旋转45°，使其与父节点平行，然后再将它们看作一个整体即可：
所以，红黑树其实就是对概念模型2-3树（或者2-3-4树）的一种实现
2-3-4 树到红黑树的转化
红黑树有五条定义：节点颜色有红色和黑色；根节点必须为黑色；所有叶子节点都是黑色；任意节点到叶子节点经过的黑色节点数量相同；不会有连续的红色节点；
情况一：待插入元素比黑父大，插在了黑父的右边，而黑父左边是红色儿子。这种情况会导致在红黑树中 出现右倾红节点。这时需要进行调整，将原本红色的左右儿子染黑，再将黑父染红。
情况二：待插入元素比红父小，且红父自身就是左倾。这时红父和待插入元素同时靠在了左边，形成了 连续的红节点。这种情况我们需要用两步来调整。由于我们插入的是红色节点，其实 不会破坏黑色完美平衡，所以要注意的是 在旋转和染色的过程种继续保持这种完美黑色平衡。首先对红父的父亲进行一次右旋，这次右旋不会破坏黑色平衡，但是也没有解决连续红色的问题。接下来 将12所在节点与15所在节点交换颜色，为了消除连续红色，并且这个操作依旧维持了黑色平衡。现在我们已经得到了情况一的场景，直接按情况一处理即可。
情况三：待插入元素比红父大，且红父自身就是左倾。这时插入的节点 形成了一个右倾的红节点。这只需要将红父进行一次左旋，就能使得右倾红节点变为左倾，现在出现了连续的左倾红节点，按情况二处理即可。
对于左倾红黑树的插入一共有三种情况
可以看到，左倾红黑树的插入 最多只需要操作三次即可将红黑树调整平衡，效率是很高的。
左倾红黑树的插入
什么是红黑树
底层数据结构
第一次添加：哈希桶（hash表）初始化为16负载因子默认值为0.75
后续扩容当增加的节点数 >= 当前的hash表长 * 0.75(该节点不一定是添加在数组上，也可以是链表上)就扩容值原来的两倍
JDK8-在多线程的情况下，红黑树的节点r=r.parent.parent所以查找根节点死循环
JDK7-多线程情况下，两个HashMap扩容最后会导致链成循环的，造成死循环
hashMap的死循环问题
HashMap底层
通过遍历keySet获取key的集合，从而获取对应的vlues值
通过迭代器去遍历keySet
通过遍历entrySet获取key或value
通过迭代器去遍历entrySet
通过遍历Values获得所有value的集合
通过迭代器去遍历Vaules
遍历方式
非线程安全
LinkedHashMap内部提供了Entry
HashMap+LinkedList
在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
保证在遍历map元素时，可以照添加的顺序实现遍历。
哈希+双向链表
底层结构
对于频繁的遍历操作，此类执行效率高于HashMap。
有序（升序，唯一）
底层数据结构：红黑树
按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。
key必须实现comparable接口，否则会抛出异常
key所属的类实现Comparable接口
TreeMap 和 HashMap 都继承自AbstractMap ，但是需要注意的是 TreeMap 它还实现了 NavigableMap 接口和 SortedMap 接口。实现 NavigableMap 接口让 TreeMap 有了 对集合内元素的搜索的能力。例如：返回集合中小于大于某一值的元素等类似操作。实现 SortedMap 接口让 TreeMap 有了 对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器（自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。）。
使用 synchronized 来保证线程安全，因为是全局锁，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大；
实现线程安全的方式
线程安全（方法都经过 synchronized 修饰），效率低；
任何非null对象均可作为key或value，Hashtable 不允许有 null 键和 null 值，编译不报错，运行时会报异常NullPointerException
不能存储null的key和value
链表解决hash冲突
底层数据结构：数组+链表
初始化容量为11
之后每次table扩容为原来的2n+1
创建时不指定容量：默认大小为11，之后每次扩容时容量为原来的2n+1创建时指定容量：Hashtable直接使用给定的大小
基本被淘汰，不要在代码中使用
hashTable的子类，线程安全
常用来处理配置文件。key和value都是String类型
注意点：key和value 都不能为空
Hashtable
假设 ConcurrentHashMap 允许插入 null，那么此时会有二义性问题：value 没在集合中，所以返回 null；value 本身就是 null，所以返回它本身的 null 值；
这就是 ConcurrentHashMap 的二义性问题，那为什么 HashMap 就不怕二义性问题呢？
二义性问题
HashMap 的设计是给单线程使用的，所以如果查询到了 null 值，我们可以通过 containsKey(key) 方法来区分这个 null 值是集合中没有这个 key，还是这个 key 的 value 就是 null：若 containsKey 返回 false，那说明集合中没有这个 key；若 containsKey 返回 true，则说明这个 key 的 value 就是 null；
这样 HashMap 的二义性就通过 containsKey() 方法得到了解决。
可证伪的 HashMap
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
key，value 都不允许为 null
ConcurrentHashMap 实现线程安全通过 synchronized 和 CAS 来保证
例如在初始化容量、判断桶是否为空都是通过 CAS 实现，不用加锁，效率高；
在需要操作链表或红黑树时，使用 synchronized 加锁，不过也只是锁某个桶，只要不发生哈希冲突，就不会阻塞；
ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。
底层具体实现：
JDK 1.7
摒弃了 Segment 的概念，不再是之前的 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要转为 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。
并发控制使用 synchronized 和 CAS 来操作。在初始化容量、判断桶是否为空等都是通过 CAS 实现，不用加锁，效率高；在需要操作链表或红黑树时，使用 synchronized 加锁，不过也只是锁某个桶，只要不发生哈希冲突，就不会阻塞；
synchronized 只锁定当前链表或红黑树的首节点，这样只要 hash 不冲突，就不会产生影响其他操作，效率提高了很多。
JDK 1.8
通过分段锁+可重入所实现线程安全
结构为：数组+链表
一个segments里面是一个小的hashMap，内置自己的计数器每一个线程对hashmap操作，会锁住segments，所以叫做分段锁并发度一定后，会对segments内置的小HashMap进行扩容
结构
有多少并发量，创建多少个segments
使用可重入锁对segments上锁
内部机制
jdk1.7
JDK 1.7：(Segment)分段数组+链表
通过volatile+synchronized锁节点+CAS操作实现线程安全
底层结构：数组+链表+红黑树
添加元素通过对每一个桶的头结点加锁桶的个数，说明了他的并发量计数，通过baseCount+counterCells数组实现——为了提供并发量
内部结构
jdk1.8
JDK 1.8：(Node)数组+链表+红黑树
JDK7HashMap出现的多线程死链问题（环）
JDK8改进JDK7由头插法改为尾插法，多线程场景下存在数据丢失问题
提高HashMap的并发安全性
见：读操作get为什么是线程安全的
解决
说说ConcurrentHashMap解决了什么问题
哈希桶数组包含多个segment，一个segment包含多个HashEntry（桶）
segment上锁不影响其他segment操作
segment继承ReentrantLock
segment分段锁
访问可见性
value值volatile修饰
底层用数组+链表实现
根据 key 计算出 hash 值定位到具体的 Segment ，再根据 hash 值获取定位 HashEntry 对象，并对 HashEntry 对象进行链表遍历，找到对应元素。
volatile 可以保证内存可见性，所以不会读取到过期数据
get操作
key 已存在看是否覆盖value
key不存在头插法插入
遍历链表内容
定位分段内的桶下标
获取对象锁成功
循环式的判断对象锁是否能够被成功获取，直到获取到锁才会退出循环，防止执行 put 操作的线程频繁阻塞
尝试自旋获取锁
重试的次数达到一定次数改为阻塞锁
尝试获取锁失败
先定位到相应的 Segment
put操作
过大，可以在一个segment内访问，变成两个segment，命中效率降低
过小，容易产生锁竞争
JDK7里是segment的数量
JDK8里并发度等于数组的大小
程序不产生锁竞争的最大线程数
ConcurrentHashMap 的并发度是什么？
JDK7中的ConcurrentHashMap
采用更细粒度的锁，锁住桶数组中桶节点
JDK8对Sychronized做大量优化后相对ReentrantLock可以减少内存开销 。
因为只对桶下标进行上锁。ReentrantLock对每个节点都需要通过继承 AQS 来获得同步支持
使用CAS+Synchronized方式，保证线程并发安全
提升查询效率
底层使用数组+链表+红黑树实现
尾插法的优势
数据添加：由JDK7的头插法改为尾插法
饿汉式创建非常消耗资源
初始化：由饿汉式改为懒汉式
get，无锁操作（仅需要保证可见性，除Treebin的读写锁），扩容过程中 get 操作拿到的是 ForwardingNode 它会让 get 操作在新table 进行搜索
返回null
根据 key 计算出 hash 值，判断哈希表table为空
如果读取的bin头节点为null
如果是链表结构，就到链表中查询
如果是红黑树结构，就从红黑树里面查询
get 流程
读操作一般不加锁(TreeBin的读写锁除外)，读写操作可并行；因为C13Map的写操作都要获取bin头部的syncronized互斥锁，能保证最多只有一个线程在做更新，单线程写、多线程读的并发安全性的问题。
如果正在发生链表向红黑树的treeify工作，因为treeify本身并不破坏旧的链表bin的结构，只是在全部treeify完成后将头节点一次性替换为新创建的TreeBin，可以放心读取。
正在迁移的hash桶
迁移形成的链是复制的，而非移动，复制不影响原数组的遍历，不会阻塞get操作
扩容前，扩容中可以访问原数组
头结点的hash 为负数表示整个数组在扩容
头结点标记为ForwardNode
转发到新数组进行查询
扩容完成的
扩容期间hash桶查询数据会发生什么？
如果正在发生resize且当前bin正在被transfer，因为transfer本身并不破坏旧的链表bin的结构，只是在全部transfer完成后将头节点一次性替换为ForwardingNode，可以放心读取。
如果是add操作，因为链表的节点新增从JDK8以后都采用了尾插法，会多遍历或者少遍历一个tailNode。
如果是remove操作，存在遍历到某个Node时，正好有其它线程将其remove，导致其孤立于整个链表之外；但因为其next引用未变，整个链表并没有断开，还是可以照常遍历链表直到tailNode。
不能保证happen before
如果是replace操作，链表的结构未变，只是某个Node的value发生了变化，没有安全问题。
如果其它线程正在操作链表，在当前线程遍历链表的任意一个时间点，都有可能同时在发生add/replace/remove操作。ConcurrentHashMap 弱一致性
结论：链表线性数据结构，单线程写且插入操作尾插法，并发读取是安全的；不会存在误读、链表断开导致的漏读、读到环状链表等问题。
如果正在发生红黑树向链表的untreeify操作，因为untreeify本身并不破坏旧的红黑树结构，只是在全部untreeify完成后将头节点一次性替换为新创建的普通Node，可以放心读取。
如果正在发生resize且当前bin正在被transfer，因为transfer本身并不破坏旧的红黑树结构，只是在全部transfer完成后将头节点一次性替换为ForwardingNode，可以放心读取。
如果其他线程在操作红黑树，在当前线程遍历红黑树的任意一个时间点，都可能有单个的其它线程发生add/replace/remove/红黑树的翻转等操作，参考红黑树的读写锁实现。
如果读取的bin是一个红黑树，说明头节点是TreeBin节点。
读操作get为什么是线程安全的
ConCurrentHashMap：if (key == null || value == null) throw new NullPointerException();如果key或者value其中一个null，就报空指针异常
HashMap：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)HashMap允许存入key为null
null区别
在并发的情况下带来二义性
map.get(key)方法得到值为null
map.contains(key)方法来判断不存在还是值为null
HashMap中
两次调用值可能被改变
ConcurrentHashMap中
为什么ConcurrentHashMap不能存null
spread(key.hashCode())保证为正数
计算key的hash值
首先会判断 key、value 是否为空，如果为空就抛异常！
当前线程正在创建另一个线程等待
JDK8仅计算size容量，懒惰式创建
JDK7直接创建数组，占用内存
创建方式区别
判断桶数组为空，创建桶数组
cas操作保证线程安全，若同时有两个线程进行同一个位置的数据添加，只有一个会成功，失败的线程进入下一次for循环。
更细粒度的锁，cas只会对hash表的一个链表头结点上锁，不影响其他链表头的操作（一个位置一把锁）
取代分段锁思想
要创建链表头节点
判断当前数组下标是否第一次插入，为空，使用casTabAt创建Node头结点
hash值为-1，说明为ForwardingNode，有线程正在扩容，当前线程帮忙扩容
已扩容
如果允许更新，进行value值的更新
找到相同的 key
链表尾部进行添加操作（JDK8的尾插法）
链表长度大于8且table长度大于64，进行树化操作
没有找到
是链表，用链表方式插入
是红黑树，用红黑树方式插入
其他线程无法获得锁，被阻塞，不能操作正在迁移的hash桶
synchronized锁住桶下标，doubleCheck检测是否变化
正在扩容的头结点
可直接插入
未扩容
扩容期间hash桶插入数据会发生什么？
最后判断是否进行扩容操作
put流程
addCount：在调用 addCount 方法增加集合元素计数后发现当前集合元素个数到达扩容阈值时就会触发扩容
helpTransfer：扩容状态下其他线程对集合进行插入、修改、删除、合并、compute 等操作时遇到 ForwardingNode 节点会触发扩容
tryPresize：putAll 批量插入或者插入节点后发现存在链表长度达到 8 个或以上，但数组长度为 64 以下时会触发扩容
什么时候触发扩容？（transfer）
hash值MOVED=-1 ，ForwardingNode存在表示集合正在扩容状态，nextTable 指向扩容后的数组。
get遍历到旧table，如果头结点标识为ForwardingNode，则到新表中get遍历，不会阻塞查询操作（转发功能）
ForwardingNode
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) +1));this.sizeCtl = cap;
记录集合在实际创建时应该使用的大小
sizeCtl值为2的幂次
新建而未初始化时
将 sizeCtl 值设置为 -1 表示集合正在初始化
其他线程发现该值为 -1 时会让出CPU资源以便初始化操作尽快完成 。
初始化过程中
sc = n - (n >>> 2);sizeCtl = sc;
记录下一次扩容的阈值
初始化完成后
第一条扩容线程设置的某个特定基数
后续线程加入扩容大军时每次加 1
线程扩容完毕退出扩容操作时每次减 1
此时 sizeCtl 的值为：((rs << RESIZE_STAMP_SHIFT) + 2) + (正在扩容的线程数) ，并且该状态下 sizeCtl < 0 。
sizeCtl 用于记录当前扩容的并发线程数情况
正在扩容时
sizeCtl 属性在各个阶段的作用
从源码中可以发现 ConcurrentHashMap 的初始化是通过 自旋和 CAS 操作完成的。里面需要注意的是变量 sizeCtl ，它的值决定着当前的初始化状态：-1 说明正在初始化-N 说明有N-1个线程正在进行扩容表示 table 初始化大小，如果 table 没有初始化表示 table 容量，如果 table 已经初始化。
初始化 initTable
直接过一遍 put 源码。
流程：根据 key 计算出 hashcode 。判断是否需要进行初始化。即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。如果当前位置的 hashcode == MOVED == -1，则需要进行扩容。如果都不满足，则利用 synchronized 锁写入数据，锁首节点 Node。如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度 ≥ 64 时才会将链表转换为红黑树。
put
get 流程比较简单，直接过一遍源码。
总结一下 get 过程：根据 hash 值计算位置。查找到指定位置，如果头节点就是要找的，直接返回它的 value.如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，使用 find() 查找之。如果是链表，遍历查找之。
get
ConcurrentHashMap 1.8 底层源码分析
JDK8中的ConcurrentHashMap
ConcurrentHashMap
Map接口
线程不安全集合（ArrayList、HashMap）
当前线程遍历时，结构上被另一个线程修改，抛出ConcurrentModificationException异常，不再继续遍历
原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
CopyOnWriteArrayList
使用JUC包下的集合
如何解决
说说什么是fail-fast
Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。
怎么确保一个集合不能被修改？
面试题
《阿里巴巴 Java 开发手册》的描述如下：判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式。这是因为 isEmpty() 方法的可读性更好，并且时间复杂度为 O(1)。
绝大部分我们使用的集合的 size() 方法的时间复杂度也是 O(1)，不过，也有很多复杂度不是 O(1) 的，比如 java.util.concurrent 包下的某些集合（ConcurrentLinkedQueue 、ConcurrentHashMap...）。
集合判空
《阿里巴巴 Java 开发手册》的描述如下：在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。
首先，我们来看 java.util.stream.Collectors 类的 toMap() 方法 ，可以看到其内部调用了 Map 接口的 merge() 方法。
Map 接口的 merge() 方法如下，这个方法是接口中的默认实现。
merge() 方法会先调用 Objects.requireNonNull() 方法判断 value 是否为空，为空则抛出异常。
原因
集合转 Map
《阿里巴巴 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 开始，可以使用 font color=\"#4caf50\
集合遍历
《阿里巴巴 Java 开发手册》的描述如下：可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。
HashSet 的 contains() 方法底部依赖 HashMap 的 containsKey() 方法，时间复杂度接近 O(1)（未出现哈希冲突时）。当我们有 N 个元素插入 Set 时，时间复杂度就接近 O(n) 。
ArrayList 的 contains() 方法是通过遍历所有元素的方法来做的，时间复杂度接近是 O(n)。当我们有 n 个元素插入 List 时，时间复杂度就接近 O(n^2) 。
以 HashSet 和 ArrayList 为例，两者的核心差别在于 contains() 方法的实现。
集合去重
《阿里巴巴 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 异常。
当传入一个原生数据类型数组时，Arrays.asList() 的真正得到的参数就不是数组中的元素，而是数组对象本身！此时 List 的唯一元素就是这个数组，这也就解释了上面的代码。我们使用包装类型数组就可以解决这个问题。
1. Arrays.asList() 是泛型方法，传递的数组必须是对象数组，而不是基本类型。
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 了。
2. 使用集合的修改方法: add()、remove()、clear() 会抛出异常。
（1）手动实现工具类
（2）最简便的方法，直接使用 ArrayList 的构造方法创建 ArrayList
（3）使用 Java8 的 Stream (推荐)
（4）使用 Java9 的 List.of() 方法
3. 如何正确的将数组转为 ArrayList
数组转集合
使用注意事项
ArrayList 的底层是 数组队列，相当于 动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；
Vector 是 List 的古老实现类，底层使用 Object[ ]存储，线程安全的。几乎所有方法都加了 Synchronized，所以 效率很低。
ArrayList 和 Vector 的区别？
是否保证线程安全： 都不保证线程安全；
底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间；而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。
ArrayList 和 LinkedList 的区别？
简介
（JDK8）ArrayList 有三种方式来初始化，构造方法源码如下：
以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。
先从 ArrayList 的构造函数说起
当添加元素时，如果元素个数+1> 当前数组长度 【size + 1 > elementData.length】时，进行扩容，扩容后的数组大小是： oldCapacity + (oldCapacity >> 1)。
注意：扩容并不是严格的1.5倍，当 oldCapacity 为奇数时，会向下取整。
扩容因子的大小选择，需要考虑如下情况：扩容容量不能太小，防止频繁扩容，频繁申请内存空间 + 数组频繁复制扩容容量不能太大，需要充分利用空间，避免浪费过多空间；为了能充分使用之前分配的内存空间，最好把增长因子设为 1<k<2.
一步一步分析 ArrayList 扩容机制
上面
常用集合源码分析
集合类型
无序存储双列元素，key-valuekey不允许重复，可以为null，只有一个value允许重复，可以有多个null一对key-value存储在一个node中Node实现了Entry接口，一对key0value也是一个entry
存储
JAVA数据存储
0 条评论
回复 删除
下一页
