Java基础打卡-集合2025.05.22
集合接口
Collection接口：定义集合的基本操作
List接口：有序集合，允许null和重复
Set接口：去重集合，允许null但不允许重复
Map接口：键值对集合，键不允许重复
常用集合类
数组
内存连续的数据类型，查找时可以根据内存地址和下标偏移计算元素所在位置，实现O(1)的查找效率。
面试常见的类型如下：
线程不安全数组：ArrayList、LinkedList
线程安全数组：Vector、Collections.synchronizedList()、CopyOnWriteArrayList
ArrayList
部分源码
/*** The array buffer into which the elements of the ArrayList are stored.* The capacity of the ArrayList is the length of this array buffer. Any* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA* will be expanded to DEFAULT_CAPACITY when the first element is added.*/transient Object[] elementData; // non-private to simplify nested class access/*** The size of the ArrayList (the number of elements it contains).** @serial*/private int size;
ArrayList使用对象数组Object[] elementData存储元素，使用size记录真实元素个数，会有多余的空间占用，比如往数组中插入了5个对象，size=5，可能elementData.length = 10，可以理解为elementData的长度为数组容量，size为数组真实大小。
ArrayList扩容
ArrayList在插入元素或者集合前（调用ArrayList.add或者ArrayList.addAll）进行扩容。
举个例子：当前数组的长度和容量为10，即elementData.length=10，size=10，ArrayList并不是在插入第10个的时后进行扩容，而是在插入第11个元素前，也就是执行第11个add方法时，判断数组大小是否够用进行扩容。
- 扩容操作：扩大为原elementData.length的1.5倍
- 扩容源码
/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来1.5倍if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}ArrayList复杂度分析
插入单个元素，不指定下标：不进行扩容O(1)，进行扩容O(n)
插入单个元素，指定下标：O(n)
插入集合：O(n)
查询元素：O(1)
LinkedList
LinkedList使用双端队列存储，源码如下：
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{transient int size = 0;/*** Pointer to first node.* Invariant: (first == null && last == null) ||* (first.prev == null && first.item != null)*/transient Node<E> first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||* (last.next == null && last.item != null)*/transient Node<E> last;
元素的类型为Node，源码如下：
private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}
LinkedList是链表结构，不需要扩容。
LinkedList复杂度分析
插入单个元素：O(n)
插入集合：O(n)
查询元素：O(n)
一般代码中不会用到LinkedList，了解即可。
Vector
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{transient int size = 0;/*** Pointer to first node.* Invariant: (first == null && last == null) ||* (first.prev == null && first.item != null)*/transient Node<E> first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||* (last.next == null && last.item != null)*/transient Node<E> last;
元素的类型为Node，源码如下：
private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}
LinkedList是链表结构，不需要扩容。
LinkedList复杂度分析
插入单个元素：O(n)
插入集合：O(n)
查询元素：O(n)
一般代码中不会用到LinkedList，了解即可。
Vector&Collection.SynchronizedList
vector是jdk1.0提供的数组，用于解决多线程同步问题。不推荐使用，个人理解主要有以下几个原因：
- vector的扩容：扩容为原数组长度的2倍，或者自定义扩容固定步长；相比ArrayList存在更多的空间浪费；
源码如下：
private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity); // capacityIncrement可以由用户指定if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}
- vector实现线程同步使用了synchronized同步方法，相比于collection.SynchronizedList()的同步代码块，锁范围更大，耗时相对更大；
源码如下：
vector源码
/*** Appends the specified element to the end of this Vector.** @param e element to be appended to this Vector* @return {@code true} (as specified by {@link Collection#add})* @since 1.2*/public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}
collection.synchronizedList()源码：
public E get(int index) {synchronized (mutex) {return list.get(index);}}
3.相比于vector，Collection.synchronizedList()提供了更加通用代理模式，可以把任意List的数组转为线程安全的集合。
但是Collection.synchronizedList()并未对迭代器进行线程安全处理，使用时需要用户自己进行线程安全保证
public ListIterator<E> listIterator() {return list.listIterator(); // Must be manually synched by user}public ListIterator<E> listIterator(int index) {return list.listIterator(index); // Must be manually synched by user}
CopyOnWriteArrayList
CopyOnWriteArrayList采用写时复制的思想，读操作不加任何锁，在写入时先复制一份副本进行修改，修改时采用可重入锁ReentrantLock进行线程安全保证，完成后再写入原数组。
优缺点：
优点：有较高的读性能，适合读多写少的场景；
缺点：有较大的内存开销，写入时需要占用双份空间；
如果写比较多，会有性能和空间瓶颈；写后不是立马可见，有读写不一致的问题；
源码如下：
/*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return {@code true} (as specified by {@link Collection#add})*/public boolean add(E e) {final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;Object[] newElements = Arrays.copyOf(elements, len + 1);newElements[len] = e;setArray(newElements);return true;} finally {lock.unlock();}}
Map
HashMap
数组结构
hashmap使用Node<K,V>结构存储键值对元素，源码如下：
/*** Basic hash bin node, used for most entries. (See below for* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)*/static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;根据条件也可能是红黑树节点结构TreeNode，继承自Node，源码如下：
/*** Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn* extends Node) so can be used as extension of either regular or* linked node.*/static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;
hashmap存储方式采用数组+链表或数组+红黑树的结构，源码如下：
/*** The table, initialized on first use, and resized as* necessary. When allocated, length is always a power of two.* (We also tolerate length zero in some operations to allow* bootstrapping mechanics that are currently not needed.)*/transient Node<K,V>[] table;
hash方法
java1.8中，hash方法比较简单：
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
设计思路是：在不影响系统性能的前提下，将key的hashCode高位与低位异或，降低冲突的概率。
采用位运算的好处：
- 提高执行速度；
- 避免处理负数；
主要属性
1.负载因子：默认为0.75，代表了hashmap的稀疏程度；负载因子越大hashmap越密集，发生hash碰撞的概率越大，负载因子越小hashmap越稀疏，占用空间越大，发生碰撞的概率越小。
/*** The load factor for the hash table.** @serial*/final float loadFactor;
2.键值对数量：
/*** The number of key-value mappings contained in this map.*/transient int size;
3.阈值：
/*** The next size value at which to resize (capacity * load factor).** @serial*/// (The javadoc description is true upon serialization.// Additionally, if the table array has not been allocated, this// field holds the initial array capacity, or zero signifying// DEFAULT_INITIAL_CAPACITY.)int threshold;
往hashmap中添加元素的过程
往hashmap中添加单个键值对：
1.计算key的hash值。
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
- 如果hashmap中没有元素，初始化数组，执行resize()。
容量为16
阈值为16*0.75=12
数组长度为16 - 执行插入逻辑，具体流程如下：
hashMap扩容
扩容为原容量的2倍，初始化时默认容量为16。
/*** Initializes or doubles table size. If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.** @return the table*/final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}