Java集合篇

Java集合篇

概念

JAVA中的集合

List

List是有序的collection,主体为数组

  • ArrayList，扩容原理是，将原来的数组复制到新的数组。查询快，插入删除慢。
  • LinkedList 是双向链表，查询慢，插入删除快。

Set

set不允许重复的元素，set中是无序的。

  • HashSet 是通过HashMap实现的，（所有Key都是用相同的Value，一个名为PRESENT的Object类型常量）。
    因为基于HashMap，所以线程不安全。
  • LinkedHashSet继承HashSet，使用双向链表维护插入顺序。
  • TreeSet通过TreeMap实现。有序

Map

Map是键值对集合。

  • HashMap 数组+链表。当链表长度大于8，表容量>=64，桶内变为红黑树。
  • LinkedHashMap 基于HashMap，双向链表。
  • HashTable 数组+链表。加锁，颗粒度粗。
  • TreeMap 红黑树
  • ConcurrentHashMap Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

List

ArrayList和Array和LinkedList

内存分布情况，和查询速率：

Array是数组，内存分布连续。查询速率O(1)

ArrayList是动态数组，内存分布也连续，但是可以扩容。默认10，扩容为原来的1.5倍。
扩容机制为，计算新的容量默认1.5倍，采用移位计算；创建新的数组；复制元素到新的数组；更改原ArrayList的索引指向新数组；完成扩容。查询速率O(1)

LinkedList是双向链表，内存随机分布。查询速率O(n)

删除时，删除效率：

ArrayList删除尾结点的元素，查询效率为O(1)；删除中间元素，因为要将后元素前移，所以查询速率为O(n)；

LinkedList删除头尾节点，可以直接修改指针，查询效率为O(1)；删除中间元素，要遍历到节点位置，查询速率为O(n)；

ArrayList和LinkedList区别？

  • 底层数据结构不同
  • 插入删除效率不同
  • 查询效率不同
  • 内存分布不同
  • 应用场景不同：ArrayList，查询多；LinkedList，插入删除多。

为什么ArrayList不是线程安全的？

  • 部分值为null 。例如：大小为10的ArrayList，两个线程同时在标9的位置进行add操作。这会导致size添加到11，然后标位10的位置是null。
  • 索引越界异常 。例如：线程1add，发现size为9，不用进行扩容，这时线程2进入，发现size为9,就进行add,size++。而这时线程1继续执行，添加坐标10的位置，但是此时没有扩容，就出现索引越界异常。
  • size与我们add的数量不符 例如：因为size与add操作不是原子性的，所以会发生。

ArrayList的线程安全实现

  • synchronizedList修饰ArrayList
    List synchronizedList = Collections.synchronizedList(arrayList);
  • CopyOnWriteArrayList
  • Vector

线程安全的集合

常见的。

  • Vector Java1.0以前 和ArrayList相似。但是每个方法都加入了scychronnized锁。

  • HashTable 给每个方法加synchronized锁

  • ConcurrentHashMap：它与 HashTable 的主要区别是二者加锁粒度的不同，在JDK1.7，ConcurrentHashMap加的是分段锁，也就是Segment锁，每个Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。
    在JDK 1.8 ，它取消了Segment字段，直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率。对于put操作，如果Key对应的数组元素为null，则通过CAS操作（Compare and Swap）将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。

  • CopyOnWriteArrayList：线程安全的ArrayList。具有较好的并发性能。因为List在进行删除或添加时，CopyOnWriteArrayList会创建一个新数组容量，将旧数组的值移到新数组。在并发环境中，写不影响读，具有较高性能。
    原理：通过violate字段修饰原数组，这样所有线程都可以看到原数组。用ReentranctLock锁来保证线程安全。但读是没有加锁的，如果是在复制前进行读操作，读的就是旧数组的数据，如果是在复制完后读取到数据，读取的就是新数组。

集合遍历的方法

  • for
  • 增强for循环(string element : List)
  • Iterator迭代器
  • ListIterator迭代器
  • forEach方法
  • Stream API

集合一边遍历一边修改

for循环可以做到，

增强for循环不行，因为是基于迭代器iterator，修改list元素可能会导致迭代器出错，抛出ConcurrentModificationException异常。

iterator，同上。

Map

img

线程不安全的Map:

  • HashMap，基于HashTable哈希表实现的。结构为：数组+链表+红黑树。Hashmap的put方法存在数据覆盖的问题。
  • LinkedHashMap，继承HashMap。底层为：数组+双向链表+红黑树.
  • TreeMap。结构红黑树。可以指定排序器来排序。

线程安全的Map：

  • HashTable，Java早期线程安全的HashMap。通过给方法加入synchronized锁实现。
  • ConcurrentHashMap。JDK1.8以前，将数据分为多个字段segment，进行插入删除等操作时，只需要拿到对应字段的锁就行，而不是整个Map的锁。JDK1.8以后，通过 volatile + CAS 或者 synchronized 来保证线程安全的。

Map的遍历方式

  • for-each和entrySet()
1
2
3
for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
  • for-each和KeySet()；拿key找value.
1
2
3
for (String key : map.keySet()) {
            System.out.println("Key: " + key + ", Value: " + map.get(key));
        }
  • Iterator
1
2
3
4
5
Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Entry<String, Integer> entry = iterator.next();
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
  • Lambda表达式和forEach方法
1
map.forEach((key, value) -> System.out.println("Key: " + key + ", Value: " + value));

Hash冲突的解决方式

  • 哈希桶中链表
  • 开放寻址法。找到数组别的可用位置放置。
  • Rehashing：用别的哈希函数计算键的哈希值，直到找到空槽来放置。
  • 哈希桶扩容：当哈希冲突过多时，动态扩大哈希桶的位置，重新分配键值对。
    默认当键值对>=负载因子0.75（默认）*数组大小，扩容为原来数组大小的两倍。

HashMap的get方法可能出现的错误

  • 空指针异常：初始化的HashMap使用null值作为键值允许。如果对未初始化的HashMap使用null值get，会出现空指针错误。
  • 线程安全：多线程同时读写可能会出现错误ConcurrentModificationException或读到错误结果。

HashMap为什么用String作为键值

因为String对象是不可变的，一旦创建好就不能被修改，确保了key的稳定性。

为什么HashMap要用红黑树而不是平衡二叉树

平衡二叉树追求的是一种 “完全平衡” 状态：左右字数高度差不会超过1，这导致我们插入或删除数据，几乎都会破坏树的结构，从而进行再平衡。

红黑树是一种观念**”弱平衡”**状态：不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整

为什么要同时重写equals重写HashCode

equals比较，会对key进行HashCode算法是否相等，相等再通过equals比较。
如果只重写equals方法，不重写HashCode算法。可能会出现，equals相同的对象存储在不同的桶中。

HashMap在多线程下可能出现的问题

  • JDk1.7以前，HashMap使用头插法，可能出现环形链表的额问题。JDK1.8后，使用尾插法，避免了这个问题。
  • 多线程进行put,如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。

HashMap的扩容机制

  1. 若size>threahold = LoadFactor(默认0.75)*capacity（默认16）,扩容
  2. 扩容到原来的2倍。
  3. 迁移元素：
    因为哈希bit位置，进行扩容的时候是位运算，新添加的可以看作随机的高位bit可能是0或1。所以不用重新哈希计算，在扩容中只用判断原来的 hash 值和左移动的一位（newtable 的值）按位与操作是 0 或 1 就行，0 的话索引不变，1 的话索引变成原索引加上扩容前数组。
  4. 如果容量小于64，链表长度大于等于8，先扩容。

ConcurrentHashMap怎么实现的

ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。

添加元素时首先会判断容器是否为空：

  • 如果为空，就使用violate+CAS初始化。
  • 如果容器不为空，则根据储存的元素计算该位置是否为空
    • 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
    • 如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

也就是说。 ConcurrentHashMap通过对头结点加锁来保证线程安全的。
JDK8 ConcurrentHashMap：数组+（链表/红黑树）；get 无锁（volatile 可见性），put 空桶 CAS，非空桶对首节点加锁*；

高位分流并行扩容（ForwardingNode 协作）；LongAdder 风格计数；迭代器弱一致；不允许 null。

Set

Set的特点

元素不重复。基于内存结构（如哈希表，红黑树）实现。

利用哈希结构储存。当储存元素时，调用equals方法无则添加，有则不会插入。

有序的Set

  • LinkeHashSet。基于红黑树实现.
#集合篇
Java集合篇
http://example.com/2025/08/19/Java集合篇/
作者
Luogic
发布于
2025年8月19日
许可协议