Java集合

1.接口继承关系和实现

集合类存放于 Java.util 包中

1.Collection：Collection 是集合 List、Set、Queue 的最基本的接口。

2.Iterator：迭代器，可以通过迭代器遍历集合中的数据

3.Map：是映射表的基础接口

image-20240419205135647

2.集合

2.1.List

List 是有序的 Collection。Java List 一共三个实现类： 分别是 ArrayList、Vector 和 LinkedList。

ArrayList（数组）

ArrayList是个数组，实现List接口，主要用来存储数据，如果存储基本类型的数据，如int，long，boolean，short，byte，那只存储它们对应的包装类。它的特点是：

1.增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。

2.查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。

3.线程不安全

4.默认的数组大小 10，默认的构造方法，构造一个初始容量为10的空列表。

扩容：

使用无参构造函数初始化 ArrayList 后，它当时的数组容量为 0 。

后面调用add()进行添加操作时，将会给数组分配默认的初始容量为DEFAULT_CAPACITY = 10。

有参构造，若传参为0，add后变为1，然后下次add正常扩容

就是通过用户传入的大小然后开辟相应的空间，

通过add()添加元素时，发现数组满的时候进行扩容的，可以通过add()中看到。

发生在向ArrayList集合中添加元素的时候，通过add()方法添加单个元素时，会先检查容量，看是否需要扩容。如果容量不足需要扩容则调用grow()扩容方法，扩容后的大小等于扩容前大小的1.5倍，也就是10+10/2。比如说超过10个元素时，会重新定义一个长度为15的数组。然后把原数组的数据，原封不动的复制到新数组中，这个时候再把指向原数的地址换到新数组。

ArrayList<String> list = new ArrayList<>(20); 中的list扩充几次？

不需要扩容。当指明了需要多少空间时，会一次性分配这么多的空间，就不需要扩容了

插入或删除元素一定比LinkedList慢么?

取决于删除的元素离数组末端有多远，ArrayList拿来作为堆栈来用还是挺合适的，push和pop操作完全不涉及数据移动操作。

频繁扩容导致添加性能急剧下降？

new ArrayList(大小)构造方法来指定集合的大小，以减少扩容的次数，提高写入效率。

如何复制某个ArrayList到另一个ArrayList中去？

使用ArrayList构造方法： ArrayList<String> list1 = new ArrayList<>(list);

使用addAll方法 ：list1.addAll(list);

适合作队列吗

不，arraylist做队列 假设头删尾插，删除头节点时要移动后面的所有元素前移一位

不过数组挺适合作队列的，双指针维护头尾

数组和链表的优劣对比

数组优势是查找快，内部空间利用率高

缺点是增删慢，外部空间碎片多

链表：增删快，随机查找慢， 内部多了指针空间利用率低，但是能解决内存碎片问题；

Vector

数组实现

*2

不同的是它支持线程的同步，即某一时刻只有一 个线程能够写 Vector

LinkList（链表）

用链表结构存储数据

适合数据的动态插入和删除

随机访问和遍历速度比较 慢

可以当作堆 栈、队列和双向队列使用。

2.2.Set

该体系集合用于存储无序(存入和取出的顺序不一定相同)元素，值不能重 复

对象的相等性本质是对象 hashCode 值（java 是依据对象的内存地址计算出的此序号）判断 的

如果要对自定义实体类去重，要在实体类中override重写 equals()、hashCode() 方法

HashSet（Hash 表）

基于hash表实现

存储元素的顺序并不是按照存入时的顺序,而是按照哈希值来存的所以取数据也是按照哈希值取得。可以认为哈希值相 同的元素放在一个哈希桶中

HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法 如果 equls 结果为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是 同一个元素

TreeSet（二叉树)

使用二叉树（红黑树）的原理对新 add()的对象按照指定的顺序排序（升序、降序），每增 加一个对象都会进行排序，将对象插入的二叉树指定的位置

Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，自 己定义的类必须实现 Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使 用

LinkHashSet

它继承与 HashSet、又基于 LinkedHashMap 来实现的。

LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法 操作上又与 HashSet 相同

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

  • HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。

  • HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。

  • 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

2.3 Queue

Queue 与 Deque 的区别

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

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

Queue 接口

抛出异常

返回特殊值

插入队尾

add(E e)

offer(E e)

删除队首

remove()

poll()

查询队首元素

element()

peek()

Deque 是双端队列，在队列的两端均可以插入或删除元素。

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

Deque 接口

抛出异常

返回特殊值

插入队首

addFirst(E e)

offerFirst(E e)

插入队尾

addLast(E e)

offerLast(E e)

删除队首

removeFirst()

pollFirst()

删除队尾

removeLast()

pollLast()

查询队首元素

getFirst()

peekFirst()

查询队尾元素

getLast()

peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

l

2.4.Map

map foreach遍历

for(HashMap.Entry entry : map.entrySet()) {
    entry.getKey()
    entry.getValue()
}

hash遍历发生了什么：

HashIterator 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后，再继续寻找下一个包含链表节点引用的桶，找到继续遍历。找不到，则结束遍历。

插入

插入操作的入口方法是 put(K,V)，但核心逻辑在V putVal(int, K, V, boolean, boolean) 方法中。putVal 方法主要做了这么几件事情：

插入时发生了 什么：

  1. 当桶数组 table 为空时，通过扩容的方式初始化 table

  2. 查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值

  3. 如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树

  4. 判断键值对数量是否大于阈值，大于的话则进行扩容操作

扩容机制

1.为什么需要扩容

因为底层基于数组实现，数组的长度是固定的，无法知道该建多大的数组

流程：

0 当 HashMap 中的键值对数量超过阈值时，进行扩容。（阈值大小为桶数组长度与负载因子的乘积。）

1 计算新桶数组的容量 newCap 和新阈值 newThr。HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍

计算newcap和newThr：

1.oldcap>0 桶数组已经被初始化，正常计算扩容即可（阈值和容量都2）*

2.oldThr>0 oldCap==0 意思是threshold>0，通过有参构造 hashmap。但桶数组并未初始化，此情况下newcap=oldThr ，然后用 capacity 和 loadFactor 计算新表的真正 threshold 值。

3.oldCap==0 oldThr==0 意思是桶数组未被初始化，且thrshold为0，是通过无参构造的， put后会讲容量赋为默认容量，阈值赋为默认容量与默认loadFactor之积

2 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的 3 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

总结

  1. 增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：1）拿到 key 的 hashCode 值；2）重哈希，为了将 hashCode 的高位参与运算，也为了增加hash复杂度减少散列冲突，重新计算 hash 值（右移n位，n为容量二进制表示长度，高位低位异或，异或结果与长度按位与）；3）将计算出来的 hash 值与 “table.length - 1” 进行 & 运算。

    （ hash%length==hash&（len-1）在len是2的n次方的情况成立，这是hashmap扩容2倍的原因）

  2. HashMap 在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash 分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity 为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。

    设容量大小对应的二进制位（16对应4位）为n位

    已知节点的索引位置是根据倒数后n位的取值来决定的

    如果两个节点在老表的索引位置相同（rehash时在老表索引位置肯定相同），则新表的索引位置只取决于节点hash值倒数第5位的值（新加的那一位的值），而此位置的值只可能是0，1，此时节点在新表的索引位置只有两种情况：“原索引位置” 和 “原索引 + oldCap位置”，在此例中即为 10 和 10 + 16 = 26。

  3. HashMap 有 threshold 属性和 loadFactor 属性，但是没有 capacity 属性。初始化时，如果传了初始化容量值，该值是存在 threshold 变量，并且 Node 数组是在第一次 put 时才会进行初始化，初始化时会将此时的 threshold 值作为新表的 capacity 值，然后用 capacity 和 loadFactor 计算新表的真正 threshold 值。

HashMap（数组+链表+红黑树）

由于时间有限，优先看hashmap的源码，其他的稍微看看arraylist扩容机制就行

HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快 的访问速度，但遍历顺序却是不确定的。

HashMap 最多只允许一条记录的键为 null，允许多条记 录的值为 null。

HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导 致数据的不一致。

可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。

HashMap和HashTable的区别

俩都是哈希表实现的

1.hashtable线程安全

2.hashtable不可以存储key为null的键值

3.hashmap在1.8加入了红黑树

优缺点

优点：

  • 方便存入kv型数据

  • O1查找效率

缺点：

  • 无序性：HashMap不保证元素的顺序，即插入顺序与遍历顺序可能不一致

  • 基于数组，扩容过程复杂消耗大

  • 长度必须是2*n（至少HashMap是这样的）

HashMap 为什么线程不安全？

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

数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在，这里以 JDK 1.8 为例进行介绍。

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

比如hashmap索引到同一个桶，线程a执行完hash冲突后拿着尾节点准备加个节点存入数据前发生线程切换，

线程b也执行完hash冲突，拿着同一个尾节点准备加个节点，此时就冲突了

举个例子：

  • 两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。

  • 不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。

  • 随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。

JAVA7 实现

大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色 的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

  1. capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。

  2. loadFactor：负载因子，默认为 0.75。填入表中的元素个数 / 散列表的长度

加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大了；

加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。

冲突的机会越大，说明需要查找的数据还需要通过另一个途径查找，这样查找的成本就越高。因此，必须在“冲突的机会”与“空间利用率”之间，寻找一种平衡与折衷。

  1. threshold：扩容的阈值，等于 capacity * loadFactor

JAVA8 实现

最大的不同就是利用了红黑树，所以其由 数组+链表+红黑 树 组成

我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的 具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决 于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，如果数组容量大于64 会将链表转换为红黑树，否则扩容数组，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)

ConcurrentHashMap
Segment 段

与hashmap不同的是,他支持并发操作

整个 ConcurrentHashMap 由一个个 Segment 组成，Segment 代表”部分“或”一段“的 意思，所以很多地方都会将其描述为分段锁。

线程安全（Segment 继承 ReentrantLock 加锁

ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每 个 Segment 是线程安全的，也就实现了全局的线程安全

并行度（默认 16）

concurrencyLevel：并行级别、并发数、Segment 数，。默认是 16， 也就是说 ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支 持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时 候设置为其他值，但是一旦初始化以后，它是不可以扩容的。再具体到每个 Segment 内部，其实 每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全，所以处理起来要麻烦些

Java8 实现 （引入了红黑树）

Java8 对 ConcurrentHashMap 进行了比较大的改动,Java8 也引入了红黑树。

HashTable（线程安全）

基于synchronized实现线程安全。任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap， 因为 ConcurrentHashMap 引入了分段锁。

有上位了:需要线程安全用 ConcurrentHashMap,不需要用hashmap

TreeMap（可排序）

TreeMap（ 底层采用红黑树实现） 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序， 也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。

LinkHashMap（记录插入顺序）
LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。

LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

待：源码分析

ConcurrentHashMap

image-20231126234533396

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升

插入流程：

根据 key 计算出 hashcode 。

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

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

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

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

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

CAS在当前Node没有数据时 写入使用

当前node有数据时用sync 写入