Java 集合框架概览

1.list

arraylist：动态数组、由于实现了RandomAccess标志性接口所以支持快速随机访问

vertor：动态数组，线程安全

linkedList:双向链表结构（1.6之前时循环链表）

(1).ArrayList

**默认初始容量是10：new ArrayList()**为0.初始化为10，也就是说初始其实是空数组当添加第一个元素的时候数组容量才变成10

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。

ArrayList扩容机制：每次1.5倍（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）

*扩容发生在add()方法

将oldCapacity 右移一位，其效果相当于oldCapacity /2，
// 我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);

然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，

这里补充一点比较重要，但是容易被忽视掉的知识点：

Java 中的 length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
Java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.
Java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!

`System.arraycopy()` 和 `Arrays.copyOf()`方法

阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法！

联系：

看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法

区别：

arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。

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

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

ArrayList 和 Vector 的区别?（了解即可）

ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全。
Vector 是 List 的古老实现类，底层使用Object[] 存储，线程安全。
插入和删除是否受元素位置的影响：
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口）支持。
内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

Arraylist 与 LinkedList 区别?

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构

2.map

HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间

LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构==可以保持键值对的插入顺序==。

treeMap：红黑树

(1).hashmap

1.数据结构:数组+链表+红黑树（当链表长度大于8并且数组长度大于64是，链表会转化为红黑树，主要是为了提升检索效率）

2.其中数组小于64时会进行扩容不会转化为红黑树。在移除数据时，当红黑树的节点移除到剩6个时，将红黑树转换成链表。(选择6个而不是8个，是为了避免频繁进行红黑树和链表的转换，造成性能的损耗。)

3.数组长度是2的n次幂：计算索引时效率更高

4.hashmap的寻址方法：

计算对象的hashcode()
调用hash()函数进行二次hash，然后右移动16位进行异或运算（让hash分布的更均匀）
最后（capocity-1）&hash 得到索引（hashmap的大小-1再&对象的hash）

5.HashMap的put操作过程：

 1. map.put(key, value)，首先计算key的hash，得到一个int值。
    2.如果Node数组为空则初始化Node数组。这里注意，Node数组的长度length始终应该是2的n次方，比如默认的16, 还有32,64等
    3.用 hash&(length-1) 运算得到数组下标，这里要提一句，其实正常我们最容易想到的，而且也是我之前很长一段时间以为的，这一步应该进行的是求模运算: hash % length ,这样得到的正好是0~length-1之间的值，可以作为数组的下标， 那么为何此处是位与运算呢？
    先说结论： 上面提到数组的长度length始终是2^n,在这个前提下，hash & (length-1) 与hash % length是等价的。 而位与运算更快。这里后面会另开一遍进行详解。
    4.  如果Node[hash&(length-1)]处为空，用传入的的key, value创建Node对象，直接放入该下标；如果该下标处不为空，且对象为TreeNode类型，证明此下标处的元素们是按照红黑树的结构存储的，将传入的key，value作为新的红黑树的节点插入到红黑树；否则，此处为链表，用next找到链表的末尾，将新的元素插入。如果在遍历链表的过程中发现链表的长度超过了8，此时如果数组长度<64则进行扩容，否则转红黑树。
    5. 如果key的hash和key本身都相等则将该key对应的value更新为新的value
    6. 需要扩容的话则进行扩容。
注意：
    1. 如果key是null则返回的hash为0，也就是key为null的元素一直被放在数组下标为0的位置。
    2. 在JDK 1.8以前，链表是采用的头部插入的方式，从1.8改成了在链表尾部插入新元素的方式。 这么做是为了防止在扩容的时候，多线程时出现循环链表死循环。具体会新开一遍进行详细演绎。

6.HashMap的get操作过程：

1. map.get(key). 首先计算key的hash。
2. 根据hash&(length-1)定位到Node数组中的一个下标。如果该下标的元素(也就是链表/红黑树的第一个元素)中 key的hash的key本身 都和传入的key相同，则证明找到了元素，直接返回即可。
3.如果第一个元素不是要找的，如果第一个元素的类型是TreeNode，则按照红黑树的查找方法查找元素，如果不是则证明是链表，按照next指针找下去，直到找到或者到达队尾。

7.hashmap 数组长度为2的n次幂：

7.1 计算索引时效率更高，%运算的速度并没有&的操作速度快。而&操作能代替%运算，必须满足一定的条件，也就是a%b=a&(b-1)仅当b是2的n次方的时候方能成立

7.2 扩容时重新计算索引的效率更高，hash & oldCap(旧容量) == 0的元素保留在原位置，否则新位置 = 旧位置 + oldCap(旧容量)

8.hashmap寻址方法：

8.1 计算对象的hashCode()

8.2 然后调用hash()进行二次哈希，然后右移16位进行异或运算，让哈希分布的均匀 3.0 最后 (capacity - 1) & hash 得到索引

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

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表

JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。

但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap

10.HashMap 为什么线程不安全？

JDK1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。

JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。

(2).ConcurrentHashMap

JDK1.7

Java 7 ConcurrentHashMap 存储结构

JDK1.8

Java8 ConcurrentHashMap 存储结构（图片来自 javadoop）

数据结构：数组+链表+红黑树

1.8之后采用cas控制数组节点的添加，synchronized锁定链表或者红黑树的首个节点。size在并发激烈的时候，采用数组形式.

怎么保证线程安全：

在jdk1.7版本前使用分段锁（segment）实现的，每次访问资源在不同分段
在jdk1.8版本后使用的是node+数组加红黑树,采用的是cas+synchronized,cas负责主要创建node节点，synchronized主要负责插入值。

ConcurrentHashMap 为什么 key 和 value 不能为 null？

ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性。null 是一个特殊的值，表示没有对象或没有引用。如果你用 null 作为键，那么你就无法区分这个键是否存在于 ConcurrentHashMap 中，还是根本没有这个键。同样，如果你用 null 作为值，那么你就无法区分这个值是否是真正存储在 ConcurrentHashMap 中的，还是因为找不到对应的键而返回的。

ConcurrentHashMap 能保证复合操作的原子性吗？

复合操作是指由多个基本操作(如put、get、remove、containsKey等)组成的操作，例如先判断某个键是否存在containsKey(key)，然后根据结果进行插入或更新put(key, value)。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。

如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge等

(3).other

HashMap与HashTable有什么区别？hashmap是线程不安全的，数组+链表+红黑树;hasttable是线程安全的，数组+链表，采用sync实现

fail-fast 机制：多个线程对 fail-fast 集合进行修改的时候，可能会抛出:

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。其实fail-fast机制并不是Java集合特有的机制，它是一个通用的系统设计思想。

通过反编译你会发现 foreach 语法底层其实还是依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法

这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast

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

(4).hashtable

hash表，线程安全的,

本文由 zzpp 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2024/09/12 09:06

JAVA集合