集合篇(下)
TIP
难免会有大量源码的存在，但是这些详细内容其实多看看就明白了，背的时候主要背总结
v1.1 2024/10/12根据小林的改版
最近其实八股掌握了有七成，再接再厉，落实到代码实现就更好了
重新调整HashMap的大小存在什么问题
1. 性能影响
- 时间复杂度: 扩容操作的时间复杂度为 O(n)，因为需要重新计算所有键值对的哈希值并重新分配它们到新的桶数组中。尤其是在插入大量数据时，扩容可能导致短暂的性能下降。
- 阻塞操作: 在单线程环境中，扩容会阻塞其他操作（如查找、插入、删除），直到扩容完成。在多线程环境中，如果没有适当的同步机制，可能导致数据不一致。
2. 内存使用
- 临时内存消耗: 在扩容期间，HashMap会分配一个新的桶数组，同时保留旧的桶数组，直到重新哈希完成。这会导致内存消耗增加，尤其是在处理大规模数据时。
- 内存碎片: 频繁扩容会导致内存碎片化，降低内存利用效率。
3. 并发问题
- 线程安全: HashMap默认不是线程安全的。在多线程环境中，扩容期间进行插入或删除操作可能导致数据不一致甚至程序崩溃。使用
ConcurrentHashMap或外部同步可以解决此问题。 - 扩容期间数据一致性: 在多线程环境中，如果多个线程在扩容过程中进行读写操作，可能会导致数据不一致。因此，必须确保扩容操作是原子操作。
4. 负载因子选择
- 不合适的负载因子: 选择不合适的负载因子可能导致频繁扩容或性能下降。负载因子过低会增加扩容次数，增加内存消耗；负载因子过高会增加哈希碰撞，降低查找性能。
- 动态调整负载因子: 如果应用中的数据量波动较大，固定负载因子可能不适用，可能需要动态调整负载因子来平衡性能和内存使用。
5. 重新哈希的成本
- 哈希函数的复杂性: 重新哈希所有键值对需要调用哈希函数，如果哈希函数复杂，重新哈希的成本会更高。
- 哈希冲突处理: 在扩容过程中，处理哈希冲突（如链表或红黑树）也会带来额外的开销。
6. 应用层面的影响
- 实时性要求: 在对实时性要求较高的应用中，扩容可能导致短暂的性能下降，影响系统的响应时间。
- 数据一致性要求: 在数据一致性要求高的应用中，扩容可能导致短暂的数据不一致，需要额外的机制来确保一致性。
解决方案与优化
- 预估初始容量: 如果能预估数据量，可以在创建 HashMap 时设置合适的初始容量，减少扩容次数。
- 使用并发数据结构: 在多线程环境中，使用
ConcurrentHashMap替代HashMap，它采用分段锁机制，减少了扩容带来的并发问题。 - 动态调整负载因子: 根据应用需求动态调整负载因子，以适应数据量变化。
通过适当的优化和设计，HashMap的扩容影响可以得到有效缓解，从而提高系统的性能和稳定性。
讲讲HashMap扩容过程以及怎么解决哈希冲突
扩容触发条件:
- 如果当前数组为空，HashMap 会进行初始化，默认创建一个长度为 16 的数组，加载因子为 0.75。
- 当元素数量达到数组长度与加载因子的乘积时触发扩容。例如，长度为 16，加载因子 0.75，元素数量达到 12 时扩容。
- 扩容时，数组长度通常会翻倍，所有元素将被重新哈希并分配到新的数组中。
扩容过程:
- 扩容时，HashMap 重新计算每个元素的哈希值，基于新数组长度重新确定其索引位置。
- 由于数组长度翻倍，元素的位运算结果可能变化，导致在新数组中的位置不同。
哈希冲突解决:
- 链表法/红黑树：HashMap 中同一索引位置可存储链表，处理哈希冲突。在 Java 8 及之后，当链表长度达到 8 且数组长度大于 64 时，链表会转换为红黑树，优化性能。
- 哈希函数：HashMap 使用精心设计的哈希函数，通过位运算结合键对象的
hashCode来生成哈希值。该哈希函数确保哈希值分布均匀，减少冲突概率。 - 初始容量和加载因子：通过调整初始容量和加载因子，可以降低哈希冲突概率。较大的初始容量和较小的加载因子虽然能减少冲突，但会增加内存使用，需权衡。
性能与空间的权衡:
- 扩容的代价较高，因为重新哈希所有元素的时间复杂度为 O(n)，导致短暂的性能下降。
- 扩容需要同时保留旧桶和新桶数组，增加了临时内存消耗。
总的来说， HashMap 通过链表法(或红黑树)和精心设计的哈希函数来解决哈希冲突，并通过扩容和重新哈希来保持哈希表的性能和效率。
补充——HashMap的扩容机制
hashMap默认的负载因子是0.75，即如果hashmap中的元素个数超过了总容量75%，则会触发扩容，扩容分为两个步骤:
- 第1步是对哈希表长度的扩展(2倍)
- 第2步是将旧哈希表中的数据放到新的哈希表中。
因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，
所以元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置，
如我们从16扩展为32时，具体的变化如下:
因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化:
因此，我们在扩容HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。
可以看看下图为16扩充为32的resize示意图:
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了
为什么HashMap多线程会进入死循环
HashMap 在多线程环境中并非线程安全，可能导致死循环，主要原因是并发修改和扩容过程中的数据不一致。
并发修改导致的链表环问题:
在多线程环境下，多个线程同时对 HashMap 进行修改（插入或删除）时，链表结构可能被破坏，形成环形链表，导致遍历时陷入死循环。
原因是多个线程同时修改链表指针，导致指针错误更新，形成环形链表。
javaimport java.util.HashMap; import java.util.Map; public class HashMapInfiniteLoop { public static void main(String[] args) { final Map<Integer, Integer> map = new HashMap<>(); // 创建两个线程同时对 HashMap 进行插入操作 Thread t1 = new Thread(() -> { for (int i = 0; i < 18000; i++) { map.put(i, i); } }); Thread t2 = new Thread(() -> { for (int i = 10000; i < 20000; i++) { map.put(i, i); } }); t1.start(); t2.start(); try { t1.join(); t2.join(); } catch (InterruptedException e) { e.printStackTrace(); } // 遍历 HashMap，可能会陷入死循环 for (Map.Entry<Integer, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }扩容导致的并发问题:
HashMap 达到容量阈值时会扩容，创建新桶并重新哈希所有键值对。在扩容过程中，若有其他线程同时插入新键值对，可能导致旧桶和新桶数据不一致，进而引发死循环。
javaimport java.util.HashMap; import java.util.Map; public class HashMapResizeInfiniteLoop { public static void main(String[] args) { final Map<Integer, Integer> map = new HashMap<>(2); // 创建两个线程同时对 HashMap 进行插入操作 Thread t1 = new Thread(() -> { for (int i = 0; i < 10000; i++) { map.put(i, i); } }); Thread t2 = new Thread(() -> { for (int i = 10000; i < 20000; i++) { map.put(i, i); } }); t1.start(); t2.start(); try { t1.join(); t2.join(); } catch (InterruptedException e) { e.printStackTrace(); } // 遍历 HashMap，可能会陷入死循环 for (Map.Entry<Integer, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }解决方案:
使用线程安全的数据结构：在多线程环境中，使用
ConcurrentHashMap，它通过分段锁机制保证线程安全。外部同步：如果必须使用
HashMap，可以通过synchronized关键字进行同步，确保线程安全。
javaimport java.util.HashMap; import java.util.Map; public class SynchronizedHashMapExample { public static void main(String[] args) { final Map<Integer, Integer> map = new HashMap<>(); Thread t1 = new Thread(() -> { synchronized (map) { for (int i = 0; i < 10000; i++) { map.put(i, i); } } }); Thread t2 = new Thread(() -> { synchronized (map) { for (int i = 10000; i < 20000; i++) { map.put(i, i); } } }); t1.start(); t2.start(); try { t1.join(); t2.join(); } catch (InterruptedException e) { e.printStackTrace(); } synchronized (map) { for (Map.Entry<Integer, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } } }
JDK7中HashMap的实现
HashMap在JDK7中的实现主要依赖数组和链表。
- 数组：HashMap内部维护了一个数组，存储所有键值对，每个数组元素是一个链表的头节点。
- 链表：当发生哈希冲突时，不同的键值对会被存储在同一个数组位置的链表中。
存储和取值流程
- 存储键值对：当我们往HashMap放键值对时，会先根据键的
hashCode()计算哈希值，再根据哈希值决定键值对放入数组的哪个位置。如果该位置为空，则直接插入；若已有其他键值对（即发生哈希冲突），则新键值对被加入该位置的链表中。- 例如，存储键值对
("apple", 1)时，计算"apple"的哈希值后决定放在数组的某个位置，如果该位置已经有键值对("banana", 2)，则将("apple", 1)加到链表上。
- 例如，存储键值对
- 取值：取值时，HashMap会根据键的哈希值定位到数组中的位置，再沿着链表找到对应的键值对。
JDK7中的HashMap数据结构
数组（table）：存储HashMap的核心数据结构。数组中的每个元素对应一个链表的头节点。
链表（Entry类）：当哈希冲突时，链表用于存储同一哈希位置的多个键值对。
Entry类（JDK7中的实现）
在JDK7中，HashMap的每个元素是一个
Entry对象，它存储键值对，并通过链表连接多个具有相同哈希位置的元素。Entry类的主要字段有：K key: 键V value: 值Entry<K,V> next: 指向下一个链表节点int hash: 存储哈希值
通过链表法解决冲突时，多个键值对可以通过
next字段连接成链表。
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
final int hash;
Entry(int h, K k, V v, Entry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
}JDK7中HashMap的put过程
当我们向HashMap存储键值对时，步骤如下：
- 计算哈希值：调用键的
hashCode()方法，计算其哈希值，并通过某些位运算减少冲突。 - 定位数组索引：根据哈希值决定键值对应存放在数组中的哪个位置。
- 插入节点：若该位置为空，直接插入
Entry节点；若不为空，发生哈希冲突，通过链表法将新Entry插入到链表头部。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
addEntry(hash, key, value, i);
return null;
}扩容与哈希冲突
- 扩容：当HashMap中的元素数量达到一定阈值时，会进行扩容（数组长度翻倍），并重新哈希所有键值对。
- 哈希冲突：通过链表法解决，当多个键映射到同一个位置时，这些键值对将被存储在该位置的链表中。
线程安全问题
HashMap在多线程环境下并不安全，可能导致如链表环形结构形成等问题，因此建议在多线程环境下使用ConcurrentHashMap来替代HashMap。
JDK8中HashMap的实现
在Java 8中，HashMap的实现进行了优化，特别是在处理哈希冲突方面引入了红黑树，从而提升了高冲突情况下的性能。
数据结构
- 数组：
HashMap的底层依旧是数组，每个位置存储一个键值对或链表的头节点。 - 链表：当发生哈希冲突且冲突的数量较小时，
HashMap使用链表来解决冲突。 - 红黑树：当链表的长度超过阈值（默认为8）时，链表会被转换为红黑树，以提高查找和插入效率。
存储过程
计算哈希值：
HashMap首先通过键的hashCode()方法计算哈希值，并对该哈希值进行扰动，以减少冲突。扰动操作使哈希值更加均匀地分布在数组中，避免直接使用原始哈希值导致的冲突。javastatic final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }确定数组索引：使用哈希值与数组长度减一后的值进行按位与运算，计算出键值对存储的数组索引位置。
javastatic int indexFor(int h, int length) { return h & (length - 1); }插入节点：
- 如果数组索引位置为空，直接插入节点。
- 如果不为空，处理哈希冲突。Java 8引入了红黑树来优化冲突处理。
处理哈希冲突
在Java 8中，处理哈希冲突的方法根据链表长度的不同有两种：
链表：如果冲突的节点数较少（链表长度≤8），则使用链表存储，节点的插入顺序保持在链表尾部。
红黑树：当链表长度超过8时，
HashMap会将链表转换为红黑树。红黑树是一种自平衡的二叉搜索树，查找、插入和删除操作的时间复杂度为O(log n)，相比链表的O(n)更高效。javaif (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st node treeifyBin(tab, hash);
取值过程
取值时，HashMap会根据键的哈希值找到对应的数组索引位置。如果该位置存储的是链表，则遍历链表查找；如果是红黑树，则在树中查找。红黑树查找的时间复杂度为O(log n)，相比链表的O(n)更高效。
扩容
当HashMap中的元素数量超过一定的阈值（通常为数组长度的0.75倍）时，会进行扩容。扩容时，HashMap会创建一个更大的数组，并将旧数组中的元素重新哈希，放入新数组中。
final void resize(int newCapacity) {
Node<K,V>[] oldTable = table;
int oldCapacity = (oldTable == null) ? 0 : oldTable.length;
if (oldCapacity > 0) {
if (oldCapacity >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新数组容量是旧容量的两倍
int newThr = (int)(newCapacity * loadFactor);
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTable = (Node<K,V>[])new Node[newCapacity];
// 重新哈希旧的节点到新数组中
transfer(newTable);
table = newTable;
threshold = newThr;
}
}扩容的步骤分析：
- 创建新数组：扩容时，
HashMap会创建一个新的数组，大小是原数组的两倍。 - 重新哈希：旧数组中的元素会被重新哈希并插入到新数组中。这是因为数组的大小变了，所以所有键的哈希值必须重新计算，以决定它们在新数组中的位置。
通过这种机制，HashMap可以保持较高的查找和插入性能，即使在存储大量数据时也能有效避免哈希冲突。
总结：Java 8中的HashMap通过引入红黑树来优化哈希冲突的处理，当链表长度超过一定阈值时，链表会转换为红黑树，以提高查找和插入效率。同时，扩容机制保证了HashMap在数据量较大时仍能保持性能。
JDK8中HashMap的put过程
1. 初始化表
如果哈希表尚未初始化或者长度为0，则需要进行初始化（或扩容）。在插入新节点之前，HashMap会检查当前的表是否需要初始化。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;2. 计算索引
使用键的哈希值和数组长度计算出索引位置。该位置决定了新节点应该插入到数组的哪个位置。
int i = (n - 1) & hash;3. 插入新节点
如果计算出的索引位置为空，则直接在该位置插入新节点。将HashMap的修改次数（modCount）加1，便于在迭代时发现并发修改。
if ((p = tab[i]) == null)
tab[i] = newNode(hash, key, value, null);4. 处理哈希冲突
如果索引位置不为空，说明发生了哈希冲突。需要处理冲突，包括以下几个步骤：
检查是否存在相同的键：如果在该位置已经存在相同的键，则替换其值。
javaif (e != null) { // 处理键相同的情况 K oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }红黑树处理：如果当前位置的节点已经是红黑树节点，调用
putTreeVal方法插入新节点。如果键值对集合是红黑树结构，在红黑树中使用哈希码和equals0)方法进行査找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。javaif (p instanceof TreeNode) ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);链表处理：如果当前位置的节点是链表，遍历链表插入新节点。
javafor (Node<K,V> e = (Node<K,V>)p; e != null; e = e.next) { if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) { oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } }
5. 转换为红黑树
如果链表长度超过阈值（默认为8）并且数组长度大于64，链表将转换为红黑树。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st node
treeifyBin(tab, hash);6. 更新节点值
如果在链表或红黑树中找到相同的键，更新其值。如果onlyIfAbsent为true且旧值为null，则更新值；否则，跳过更新。
if (e != null) {
K oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}7. 调整大小
每插入一个新节点后，增加元素数量。如果当前元素数量超过阈值，则进行扩容。
++modCount; // 版本修改
if (++size > threshold)
resize();8. 插入后的处理
插入新节点后，执行一些插入后的处理操作，如清理可能的垃圾回收等。
afterNodeInsertion(evict);总结
- 初始化表：确保表已初始化。
- 计算索引：使用哈希值确定索引位置。
- 插入新节点：如果索引位置为空，直接插入新节点。
- 处理哈希冲突：
- 检查是否存在相同的键并更新值。
- 如果当前位置是红黑树，调用
putTreeVal方法插入新节点。 - 如果当前位置是链表，遍历链表插入新节点。
- 转换为红黑树：链表长度超过阈值时，转换为红黑树。
- 更新节点值：处理键相同的情况，更新节点值。
- 调整大小：如果元素数量超过阈值，进行扩容。
- 插入后的处理：执行一些插入后的处理操作。
为什么String适合做为Key呢
用 string 做 key，因为 String对象是不可变的，一旦创建就不能被修改，这确保了Key的稳定性。如果Key是可变的，可能会导致hashCode和equals方法的不一致，进而影响HashMap的正确性
为什么HashMap要用红黑树而不是平衡二叉树？
- 平衡二叉树追求的是一种“完全平衡”状态：任何结点的左右子树的高度差不会超过 1，优势是树的结点是很平均分配的。这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
- 红黑树不追求这种完全平衡状态，而是追求一种“弱平衡”状态：整个树最长路径不会超过最短路径的2 倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。
HashMap可以用null作为key吗
HashMap中使用
hash方法来计算key的哈希值，当key为空（null）时，直接令key的哈希值为0，不走key.hashCode()方法javastatic final int hash(Object key){ int h; //当key等于null的时候，不走hashCode()方法 return(key == null)?0:(h= key.hashCode())^(h >>> 16); }HashMap虽然支持key和value为null，但是null作为key只能有一个，null作为value可以有多个；因为HashMap中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个。
重写HashMap的equal和hashcode方法需要注意什么?
HashMap使用Key对象的hashCode和equals方法去决定key-value对的索引。当我们试着从HashMap中获取值的时候，这些方法也会被用到。如果这些方法没有被正确地实现，在这种情况下，两个不同Key也许会产生相同的hashCode和equals输出，HashMap将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方。
同样的，所有不允许存储重复数据的集合类都使用hashCode和equals去查找重复，所以正确实现它们非常重要。equals和hashCode的实现应该遵循以下规则:
如果 o1.equals(o2)，那么 o1.hashcode() == o2.hashCode() 总是为true
如果 o1.hashCode() == o2.hashCode()，并不意味着 o1.equals(o2) 会为true
重写HashMap的equals方法不当会出现什么问题?
HashMap在比较元素时，会先通过hashCode进行比较，相同的情况下再通过equals进行比较。
所以 equals相等的两个对象，hashCode一定相等。hashcode相等的两个对象，equals不一定相等(比如散列冲突的情况)
重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，而hashCode方法却返回false，这样的一个后果会导致在hashmap等类中存储多个一模一样的对象，导致出现覆盖存储的数据的问题，这与hashmap只能有唯一的key的规范不符合。
列举HashMap在多线程下可能会出现的问题?
JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。
因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在(本质就是HashMap的put操作并不是一个原子性的操作)
JDK7中ConcurrentHashMap的实现
在 JDK 7 中，ConcurrentHashMap 的实现依赖于分段锁（Segment Locking）机制来实现高并发性能。主要结构包括 Segment、HashEntry 和 ConcurrentHashMap 本身。
主要结构
Segment
Segment类是ConcurrentHashMap的核心部分，每个Segment是一个小的哈希表，并且拥有独立的锁。Segment继承自ReentrantLock，提供了分段锁机制。javastatic final class Segment<K,V> extends ReentrantLock implements Serializable { transient volatile HashEntry<K,V>[] table; transient int count; transient int modcount; transient int threshold; final float loadFactor; Segment(float lf, int threshold, HashEntry<K,V>[] tab) { this.loadFactor = lf; this.threshold = threshold; this.table = tab; } }HashEntry
HashEntry是Segment内部哈希表中的每个节点，存储键值对。每个HashEntry包含键、值和指向下一个HashEntry的引用（用于处理哈希冲突的链表）。javastatic final class HashEntry<K,V> { final K key; volatile V value; final int hash; final HashEntry<K,V> next; HashEntry(int hash, K key, V value, HashEntry<K,V> next) { this.key = key; this.value = value; this.hash = hash; this.next = next; } }ConcurrentHashMap
ConcurrentHashMap包含多个Segment。每个Segment负责哈希表的一部分，并拥有自己的锁，从而允许多个线程并发地访问不同的Segment。
Segment 类
分段锁：每个
Segment是一个独立的哈希表，拥有自己的锁。这样 不同的线程 可以 并发地访问不同的Segment，显著提高并发性能。高效并发：细粒度的锁机制避免了全表锁的性能瓶颈，提高了并发性能。
ConcurrentHashMap 的 put 和 get 方法简述
put方法在 JDK 7 的
ConcurrentHashMap中，put方法涉及以下步骤：- 确定 Segment：根据哈希值计算出应该插入到哪个
Segment。 - 获取锁：对该
Segment上的锁进行加锁，确保线程安全。 - 插入或更新：在锁保护下，执行插入或更新操作。
- 释放锁：操作完成后，释放锁。
javapublic V put(K key, V value) { int hash = hash(key); Segment<K,V> segment = segmentFor(hash); segment.lock(); try { // 执行插入或更新操作 } finally { segment.unlock(); } }- 确定 Segment：根据哈希值计算出应该插入到哪个
get方法在 JDK 7 的
ConcurrentHashMap中，get方法涉及以下步骤：- 确定 Segment：根据哈希值计算出应该查询的
Segment。 - 获取锁：对该
Segment上的锁进行加锁，确保线程安全。 - 查询：在锁保护下，执行查询操作。
- 释放锁：操作完成后，释放锁。
javapublic V get(Object key) { int hash = hash(key); Segment<K,V> segment = segmentFor(hash); segment.lock(); try { // 执行查询操作 } finally { segment.unlock(); } }- 确定 Segment：根据哈希值计算出应该查询的
总结
- 分段锁：
ConcurrentHashMap使用分段锁来提高并发性能，每个Segment拥有独立的锁。 - Segment：
Segment是ConcurrentHashMap的核心，管理哈希表的一部分，并处理并发操作。 - HashEntry：哈希表中的每个节点，存储键值对。
- put 方法：通过锁定相应的
Segment来插入或更新键值对。 - get 方法：通过锁定相应的
Segment来查询键对应的值。
每个Seqment是一个独立的小哈希表，拥有自己的锁，允许多个线程并发地访问不同的Segment。这种设计在高并发环境下显著提高了性能，同时保证了线程安全性。
JDK8中ConcurrentHashMap的实现
在 JDK 8 中，ConcurrentHashMap 进行了显著的重新设计，相比于 JDK 7 的实现，改用了 更细粒度的锁和无锁操作 来提高并发性能。
JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空:
- 如果为空则使用 volatile 加 CAS 来初始化
- 如果容器不为空，则根据存储的元素计算该位置是否为空。
- 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点
- 如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。
如果把上面的执行用一句话归纳的话，就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。
而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度。
已经用了synchronized（悲观锁），为什么还要用CAS（乐观锁）呢?
ConcurrentHashMap使用这两种手段来保证线程安全主要是一种权衡的考虑，在某些操作中使用synchronized，还是使用CAS，主要是根据锁竞争程度来判断的。
比如 : 在putVal中，如果计算出来的hash槽没有存放元素，那么就可以直接使用CAS来进行设置值，这是因为在设置元素的时候，因为hash值经过了各种扰动后，造成hash碰撞的几率较低，那么我们可以预测使用较少的自旋来完成具体的hash落槽操作。
当发生了hash碰撞的时候说明容量不够用了或者已经有大量线程访问了，因此这时候使用synchronized来处理hash碰撞比CAS效率要高，因为发生了hash碰撞大概率来说是线程竞争比较强烈。
Java 8 中 ConcurrentHashMap 的主要改进
数据结构
Node：基本的链表节点，存储键值对和指向下一个节点的指针。TreeNode：用于红黑树的节点。当链表长度超过一定阈值（默认是8）时，链表会转换为红黑树。TreeBin：红黑树的容器，管理红黑树的操作。ForwardingNode：在扩容过程中用于指示节点已经被移动。主要操作
put操作：通过 CAS（Compare-And-Swap）操作和细粒度的锁来实现高效的并发插入和更新。get操作：使用 无锁 的方式进行查找，性能更高。扩容：通过逐步迁移节点和协作扩容机制，提高扩容效率。
细粒度的并发控制
CAS 操作：使用 CAS 操作进行无锁插入和更新，减少锁竞争。
synchronized块：在必要时对单个桶（bin）进行加锁，而不是整个段，从而进一步提高并发性。红黑树：当链表长度超过阈值时，转换为红黑树，降低查找时间复杂度，从 O(n) 降低到 O(log n)。
Java 7 vs Java 8 的对比
更高的并发性
- Java 7：使用分段锁机制，每个
Segment是独立的锁，锁的粒度较粗。 - Java 8：使用更细粒度的锁和无锁操作，减少了锁竞争，提升了并发性能。
- Java 7：使用分段锁机制，每个
更好的性能
get操作：- Java 7：使用锁来保证线程安全。
- Java 8：使用无锁的方式进行查找，性能更高。
put操作：- Java 7：使用分段锁进行操作，性能受到锁粒度的限制。
- Java 8：使用 CAS 操作和细粒度锁，性能得到提升。
更高效的扩容
- Java 7：扩容过程涉及整个哈希表的锁定和迁移，可能会影响性能。
- Java 8：通过逐步迁移节点和协作扩容机制，提高了扩容效率，减少了扩容过程中对性能的影响。
更高效的查找
- Java 7：链表用于处理哈希冲突，查找时间复杂度为 O(n)。
- Java 8：当链表长度超过阈值时，转换为红黑树，查找时间复杂度降为 O(log n)。
代码实现概述
Node 类
javastatic final class Node<K,V> { final int hash; final K key; volatile V value; volatile Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } }val和next都标注为volatile，保证在多线程环境下的可见性。
TreeNode 类
javastatic final class TreeNode<K,V> extends Node<K,V> { TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; boolean red; TreeNode(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }TreeBin 类
javastatic final class TreeBin<K,V> extends Node<K,V> { final TreeNode<K,V> root; TreeBin(TreeNode<K,V> root) { super(-1, null, null, null); this.root = root; } }扩容
扩容过程中，Java 8 中的
ConcurrentHashMap会使用 逐步迁移 的机制，将旧表中的节点逐步迁移到新表中，同时通过ForwardingNode来指示迁移过程中的节点。javafinal void resize() { // 扩容过程的实现 }
总结
Java 8 中的 ConcurrentHashMap 通过引入更细粒度的锁、无锁操作、红黑树等改进，在高并发环境下提供了更高效的性能。
通过 对链表的头加锁 实现，使用的是 CAS 操作加内部的 Synchroized。Node数组+链表+红黑树的结构，从而 实现了对每一行数据进行加锁，进一步减少并发冲突的概率（更细粒度的锁）。
Node类成员变量Node的元素val和指针next都标注volatile，目的是在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。
这些改进使得 ConcurrentHashMap 在处理并发插入、查询和扩容时表现更为优越。
什么是HashTable
Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自Dictionary 类，并且是 线程安全 的，任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap。Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。
Hashtable vs HashMap :
- Hashtable是线程安全的，而HashMap不是
- Hashtable不允许键或值为null，而HashMap允许一个null键和多个nul值。
在现代 Java 编程中，HashMap更常用，因为它在大多数情况下性能更好，并且可以通过外部同步来实现线程安全。
Hashtable vs.ConcurrentHashMap:
- ConcurrentHashMap是Java5引入的一种改进的哈希表实现，专为高并发环境设计。
- ConcurrentHashMap提供了更细粒度的锁机制，允许更高的并发性和更好的性能。
什么是TreeMap
基本特点
- 有序性:
TreeMap保证键的自然顺序(通过Comparable接口)或通过提供的比较器(Comparator)的顺序。 - 红黑树: 使用红黑树数据结构，操作时间复杂度为 O(log n)。
- 不允许 null 键: 键不能为 null，但值可以为 null。
- 线程不安全: 不是线程安全的，需外部同步机制保证线程安全。
与其他集合类的比较
TreeMap vs. HashMap:
TreeMap: 保证键的有序性，操作时间复杂度 O(log n)，不允许 null 键。HashMap: 不保证顺序，操作平均时间复杂度 O(1)，允许一个 null 键。TreeMap vs. LinkedHashMap:
TreeMap: 保证键的自然顺序或比较器的顺序，操作时间复杂度 O(log n)。LinkedHashMap: 保证插入顺序或访问顺序，操作时间复杂度 O(1)。
适用场景
- 实现基于范围的查询。
- 按顺序遍历键值对。
- 快速查找最小或最大键值对。
什么是LinkedHashMap
LinkedHashMap 是 Java 集合框架中的一个类，继承自 HashMap，并结合了哈希表和链表的特点。它通过双向链表来维护键值对的顺序，可以是插入顺序（默认）或访问顺序（可选）。
基本特点:
- 有序性: LinkedHashMap 保证了键值对的顺序，支持 插入顺序（默认） 或 访问顺序（可选）。
- 哈希表和链表结合: 使用哈希表实现快速查找，双向链表维护键值对的顺序。
- 允许 null 键和值: 允许一个 null 键和多个 null 值。
- 线程不安全: 不是线程安全的，需外部同步来保证线程安全。
与其他集合类的比较:
- LinkedHashMap vs. HashMap: LinkedHashMap 保证顺序，而 HashMap 不保证。插入和删除操作上，LinkedHashMap 可能略慢于 HashMap。
- LinkedHashMap vs. TreeMap: LinkedHashMap 维护插入或访问顺序，而 TreeMap 维护键的自然顺序或通过比较器的顺序。操作复杂度方面，LinkedHashMap 的平均时间复杂度为 O(1)，而 TreeMap 为 O(log n)。
适用场景:
- 实现 LRU（最近最少使用）缓存。
- 按插入顺序遍历键值对。
- 在保持顺序的同时快速查找键值对。
LinkedHashMap为什么能用来做LRUCache
LinkedHashMap 可以实现 LRU（最近最少使用）缓存的关键在于其可以维护访问顺序。通过重写 removeEldestEntry 方法，能够实现缓存的自动清理。
关键特性
- 访问顺序: 通过将构造方法中的
accessOrder参数设置为true，LinkedHashMap 可以根据每次访问（get或put操作）调整顺序，将最近访问的键值对移到链表的末尾。 - 自动清理: 通过重写
removeEldestEntry方法，可以在插入新键值对时自动移除最老的键值对，实现缓存的自动清理。
实现步骤
- 创建一个
LinkedHashMap实例，将accessOrder参数设置为true。 - 重写
removeEldestEntry方法，当缓存大小超过预定义的最大容量时，自动移除最老的键值对。
示例代码
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxCapacity;
// 构造函数，初始化最大容量和访问顺序
public LRUCache(int maxCapacity) {
super(maxCapacity, 0.75f, true); // accessOrder 参数设置为 true
this.maxCapacity = maxCapacity;
}
// 重写 removeEldestEntry 方法，当大小超过最大容量时移除最老的键值对
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxCapacity;
}
public static void main(String[] args) {
// 创建一个容量为 3 的 LRU 缓存
LRUCache<String, Integer> cache = new LRUCache<>(3);
// 插入键值对
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
// 访问键 "A" (使其成为最近使用的)
cache.get("A");
// 插入新键值对 "D"，导致最老的键值对 "B" 被移除
cache.put("D", 4);
// 打印缓存内容
System.out.println(cache); // 输出: {C=3, A=1, D=4}
}
}解释
- 构造方法:
LRUCache构造方法调用了LinkedHashMap的构造方法，设置accessOrder参数为true以保持访问顺序。 removeEldestEntry方法: 当缓存的大小超过maxCapacity时，该方法返回true，从而移除最老的键值对。- 使用示例: 主方法中创建了一个
LRUCache实例，插入了几个键值对，并通过访问键 "A" 改变其顺序。插入新键值对 "D" 导致最老的键值对 "B" 被移除。
这种方式使得 LinkedHashMap 能够高效地实现 LRU 缓存，确保最近使用的键值对保留在缓存中，而最老的键值对在缓存容量达到上限时自动移除。
LinkedHashMap如何保证有序性
LinkedHashMap 通过维护一个双向链表来保证键值对的顺序
具体实现原理
- 双向链表: LinkedHashMap 内部维护一个双向链表。每个节点包含一个键值对及两个引用，分别指向前一个节点和后一个节点。这个链表使得 LinkedHashMap 可以高效地遍历和保持键值对的顺序。
- 插入顺序: 默认情况下，LinkedHashMap 按照插入顺序维护键值对。每次插入新键值对时，新的节点会被添加到链表的末尾。
- 访问顺序: 如果构造方法中的
accessOrder参数设置为true，LinkedHashMap 会按照访问顺序维护键值对的顺序。每次访问（get或put操作）一个键值对时，该节点会被移动到链表的末尾，反映最新的访问顺序。
示例代码
// 创建一个按照访问顺序维护键值对的 LinkedHashMap
LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);内部机制
- 节点结构: 每个节点包含键、值以及指向前一个节点和后一个节点的引用。这样可以高效地调整链表中的节点位置。
- 操作调整: 插入或访问键值对时，LinkedHashMap 会调整节点在链表中的位置，以保持所需的顺序。例如，在访问顺序模式下，每次访问键值对时，相应的节点会被移动到链表的末尾，以保持访问顺序的正确性。
如何确保函数不能修改集合
不可修改集合的创建与使用
使用
Collections.unmodifiableCollection方法功能: 将集合包装为不可修改的视图，修改操作会抛出
UnsupportedOperationException。示例代码:
javaimport java.util.*; public class UnmodifiableCollectionExample { public static void main(String[] args) { List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C")); Collection<String> unmodifiableList = Collections.unmodifiableCollection(list); // 传递不可修改的集合给函数 printCollection(unmodifiableList); // 尝试修改集合将抛出 UnsupportedOperationException // unmodifiableList.add("D"); // 这行代码会抛出异常 } public static void printCollection(Collection<String> collection) { for (String item : collection) { System.out.println(item); } } }使用
Collections.unmodifiableList、Collections.unmodifiableSet、Collections.unmodifiableMap功能: 对于特定类型的集合（List、Set、Map），提供相应的不可修改视图方法。
示例代码:
javaimport java.util.*; public class UnmodifiableSpecificCollectionsExample { public static void main(String[] args) { List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C")); List<String> unmodifiableList = Collections.unmodifiableList(list); Set<String> set = new HashSet<>(Arrays.asList("X", "Y", "Z")); Set<String> unmodifiableSet = Collections.unmodifiableSet(set); Map<String, Integer> map = new HashMap<>(); map.put("One", 1); map.put("Two", 2); Map<String, Integer> unmodifiableMap = Collections.unmodifiableMap(map); // 传递不可修改的集合给函数 printList(unmodifiableList); printSet(unmodifiableSet); printMap(unmodifiableMap); // 尝试修改集合将抛出 UnsupportedOperationException // unmodifiableList.add("D"); // 这行代码会抛出异常 // unmodifiableSet.add("W"); // 这行代码会抛出异常 // unmodifiableMap.put("Three", 3); // 这行代码会抛出异常 } public static void printList(List<String> list) { for (String item : list) { System.out.println(item); } } public static void printSet(Set<String> set) { for (String item : set) { System.out.println(item); } } public static void printMap(Map<String, Integer> map) { for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }使用递归包装嵌套集合
功能: 对包含嵌套集合的集合递归地应用不可修改视图，以确保所有层级都不可修改。
示例代码:
javaimport java.util.*; public class UnmodifiableNestedCollectionsExample { public static void main(String[] args) { List<Set<String>> listOfSets = new ArrayList<>(); listOfSets.add(new HashSet<>(Arrays.asList("A", "B", "C"))); listOfSets.add(new HashSet<>(Arrays.asList("X", "Y", "Z"))); List<Set<String>> unmodifiableListOfSets = new ArrayList<>(); for (Set<String> set : listOfSets) { unmodifiableListOfSets.add(Collections.unmodifiableSet(set)); } Collection<List<Set<String>>> unmodifiableCollection = Collections.unmodifiableCollection(unmodifiableListOfSets); // 传递不可修改的集合给函数 printNestedCollection(unmodifiableCollection); // 尝试修改集合将抛出 UnsupportedOperationException // unmodifiableListOfSets.get(0).add("D"); // 这行代码会抛出异常 } public static void printNestedCollection(Collection<List<Set<String>>> collection) { for (List<Set<String>> list : collection) { for (Set<String> set : list) { for (String item : set) { System.out.println(item); } } } } }
通过以上方法，可以创建不可修改的集合，确保集合内容不会被修改，从而保护数据的一致性和安全性。
Comparable 和 Comparator 的区别
Comparable 和 Comparator 接口的比较
Comparable接口用途: 用于定义对象的 自然排序顺序。实现该接口的类需覆盖
compareTo方法，该方法用于比较当前对象与指定对象的顺序。实现方式:
- 类实现
Comparable接口，并覆盖compareTo方法。 - 示例代码:java
public class Person implements Comparable<Person> { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public int compareTo(Person other) { return this.name.compareTo(other.name); // 按名字排序 } }
- 类实现
Comparator接口用途: 用于定义对象的 自定义排序顺序。允许定义多个排序标准，而 不需要修改对象的类。
实现方式:
- 创建实现
Comparator接口的类或匿名类，并覆盖compare方法。 - 示例代码:java
import java.util.Comparator; public class PersonAgeComparator implements Comparator<Person> { @Override public int compare(Person p1, Person p2) { return Integer.compare(p1.getAge(), p2.getAge()); // 按年龄排序 } }
- 创建实现
主要区别:
接口实现位置:
Comparable: 对象类自身实现Comparable接口，定义其自然排序顺序。Comparator: 单独的类或匿名类实现Comparator接口，定义自定义排序顺序。
方法名称:
Comparable: 实现compareTo方法。Comparator: 实现compare方法。
排序标准:
Comparable: 只能有一个排序标准（自然顺序）。Comparator: 可以有多个排序标准，可以根据需要定义不同的Comparator实现。
使用场景:
Comparable: 适用于单一的自然排序顺序，例如字典顺序、数字顺序等。Comparator: 适用于需要多个排序标准的场景，例如按名字排序、按年龄排序等。
Enumeration 和 Iterator 的接口区别
尽管 Enumeration 和 Iterator 都用于遍历集合，Iterator 是更现代和灵活的选择，适用于所有集合类，并提供了在遍历过程中安全地移除元素的功能。
主要区别:
引入时间:
Enumeration: 引入于 Java 1.0。Iterator: 引入于 Java 2 (DK 1.2)。
方法名称和功能:
Enumeration: 使用hasMoreElements()和nextElement()方法。Iterator: 使用hasNext()和next()方法，并增加了remove()方法。
元素移除:
Enumeration: 不支持在遍历过程中移除元素。Iterator: 支持在遍历过程中 安全地移除 元素（通过remove()方法）。
适用范围:
Enumeration: 主要用于旧的集合类，如Vector和Hashtable。Iterator: 适用于所有集合类，是集合框架的一部分。
设计初衷:
Enumeration: 设计较为简单，功能有限。Iterator: 设计更为灵活，功能更强大，支持安全地修改集合。
什么是Fail-Fast机制
工作原理:
- Fail-fast 迭代器: 在遍历集合时维护一个修改计数器。当集合结构发生变化（如添加或删除元素）时，该计数器增加。
- 检测修改: 创建迭代器时，迭代器保存当前的修改计数器值。在每次调用
next()方法时，迭代器检查当前的修改计数器值是否与保存的值一致。如果不一致，说明集合在迭代过程中被修改了，迭代器会抛出ConcurrentModificationException异常。
注意事项:
- 机制并不保证: Fail-fast 机制并不能保证在所有情况下都能检测到并发修改，它是 尽力而为 的检测机制。如果需要并发安全的集合，可以使用
java.util.concurrent包中的并发集合类。 - 避免并发修改: 避免在遍历集合时修改集合。可以使用迭代器的
remove方法安全地移除元素。
示例代码:
import java.util.*;
public class FailFastExample {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String element = iterator.next();
System.out.println(element);
// 在迭代过程中修改集合
if (element.equals("B")) {
list.add("D"); // 这将引发 ConcurrentModificationException
iterator.remove(); // 使用迭代器的 remove 方法安全地移除元素
}
}
}
}总结:
- Fail-fast 机制用于在遍历集合时检测结构性修改并抛出
ConcurrentModificationException异常，有助于防止遍历过程中出现不一致的状态。 - 避免在遍历集合时进行结构性修改，或使用迭代器的
remove方法来安全地移除元素。