目录
1. 同步包装器（Synchronized Wrappers）
2. 并发集合类（Concurrent Collections）
3. 不可变集合（Immutable Collections）
1.集合类的线程安全实现
在 Java 中，为了保证集合类的线程安全性，有几种不同的策略和工具。以下是一些常用的线程安全集合类及其保证线程安全的方式：
1. 同步包装器（Synchronized Wrappers）
Java 提供了一些静态工厂方法，可以将现有的集合类包装成线程安全的版本。这些方法位于 java.util.Collections 类中。
List<String> list = new ArrayList<>(); List<String> synchronizedList = Collections.synchronizedList(list); Map<String, String> map = new HashMap<>(); Map<String, String> synchronizedMap = Collections.synchronizedMap(map);
保证线程安全的方式
-
同步方法：这些包装器通过在每个方法上调用
synchronized关键字来实现线程安全。例如，synchronizedList的add方法会被包装成如下形式：
public synchronized boolean add(E e) {
return list.add(e);
}
-
同步块：对于需要多个操作的复合动作（如迭代），必须手动同步整个块：
synchronized (synchronizedList) {
Iterator<String> it = synchronizedList.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
2. 并发集合类（Concurrent Collections）
Java 的 java.util.concurrent 包提供了一系列专门设计的并发集合类，这些类在设计时就考虑了多线程环境下的性能和安全性。
常见的并发集合类
-
ConcurrentHashMap：线程安全的哈希表实现，允许多个线程同时读取和更新表。它通过分段锁（Segment Locking）或更细粒度的锁（如 JDK 8 中的 CAS 操作）来实现高并发性能。 -
CopyOnWriteArrayList：线程安全的列表实现，基于写时复制（Copy-On-Write）机制。每次写操作都会创建一个新的数组副本，读操作则始终在旧的数组上进行，因此读操作是无锁的。 -
CopyOnWriteArraySet：基于CopyOnWriteArrayList实现的线程安全的集合。 -
ConcurrentLinkedQueue：线程安全的无界非阻塞队列。 -
ConcurrentSkipListMap和ConcurrentSkipListSet：基于跳表（Skip List）实现的线程安全的有序映射和集合。
保证线程安全的方式
-
分段锁：
ConcurrentHashMap使用分段锁技术，将哈希表分成多个段，每个段有自己的锁，从而允许多个线程同时访问不同的段。 -
CAS 操作：
ConcurrentHashMap在 JDK 8 及以上版本中使用 CAS（Compare-and-Swap）操作来实现无锁化。 -
写时复制：
CopyOnWriteArrayList和CopyOnWriteArraySet在写操作时创建新的数组副本，读操作则在旧的数组上进行，从而避免了读写冲突。 -
非阻塞算法：
ConcurrentLinkedQueue使用非阻塞算法，允许多个线程并发地进行插入和删除操作。
3. 不可变集合（Immutable Collections）
不可变集合一旦创建就不能被修改，因此天生就是线程安全的。Java 提供了一些工具类来创建不可变集合，如 Collections.unmodifiableList、Collections.unmodifiableMap 等。
2.哈希表
Java 的集合框架中，特别是 HashMap、HashSet 和 Hashtable 等集合类，广泛使用哈希算法的原因主要有以下几个方面：
1. 高效的查找、插入和删除操作
哈希表（Hash Table）通过哈希函数将键（key）映射到数组的索引位置，从而实现快速的查找、插入和删除操作。理想情况下，这些操作的时间复杂度为 O(1)O(1)。
2. 减少内存占用
哈希表通过将键映射到数组索引，可以有效地利用内存。相比于其他数据结构（如二叉搜索树），哈希表在大多数情况下可以使用更少的内存来存储相同数量的元素。
3. 支持唯一性
HashSet 和 HashMap 的键必须是唯一的。哈希表通过哈希函数和冲突解决机制确保键的唯一性。如果尝试插入一个已经存在的键，哈希表会覆盖旧值或忽略插入操作。
4. 快速的集合操作
哈希表支持快速的集合操作，如并集、交集和差集。这些操作在哈希表中通常比在其他数据结构中更快。
5. 灵活的键类型
哈希表可以使用任何实现了 hashCode 和 equals 方法的对象作为键。这使得哈希表非常灵活，可以用于各种类型的键。
3.哈希表结构存储的过程
1.HashMap底层数据数据结构:哈希表
2.jdk7:哈希表 = 数组+链表 jdk8:哈希表 = 数组+链表+红黑树
3.先算哈希值,此哈希值在HashMap底层经过了特殊的计算得出 如果哈希值不一样,直接存 如果哈希值一样,再去比较内容,如果内容不一样,也存 如果哈希值一样,内容也一样,直接去重复(后面的value将前面的value覆盖)
哈希值一样,内容不一样->哈希冲突(哈希碰撞)
Java 的集合类通过以下几种方法处理哈希冲突：
a.链地址法（Separate Chaining）：
-
在每个数组索引位置维护一个链表或链式结构。
-
当发生冲突时，将冲突的键值对存储在链表中。
-
例如，
HashMap使用链表（在 JDK 8 及以上版本中，当链表长度超过一定阈值时，会转换为红黑树）来处理冲突。
b.开放地址法（Open Addressing）：
-
当发生冲突时，寻找下一个可用的位置。
-
常见的开放地址法包括线性探测、二次探测和双重哈希等。
-
Hashtable使用线性探测来处理冲突。
4.要知道的点:
a.在不指定长度时,哈希表中的数组默认长度为16,HashMap创建出来,一开始没有创建长度为16的数组
b.什么时候创建的长度为16的数组呢?在第一次put的时候,底层会创建长度为16的数组
c.哈希表中有一个数据加[加载因子]->默认为0.75(加载因子)->代表当元素存储到百分之75的时候要扩容了->2倍
d.如果对个元素出现了哈希值一样,内容不一样时,就会在同一个索引上以链表的形式存储,当链表长度达到8并且当前数组长度>=64时,链表就会改成使用红黑树存储 如果后续删除元素,那么在同一个索引位置上的元素个数小于6,红黑树会变回链表 e.加入红黑树目的:查询快
1.HashMap无参数构造方法的分析
//HashMap中的静态成员变量
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
解析：使用无参数构造方法创建HashMap对象，将加载因子设置为默认的加载因子，loadFactor=0.75F。
2.HashMap有参数构造方法分析
HashMap(int initialCapacity, float loadFactor) ->创建Map集合的时候指定底层数组长度以及加载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//10
}
解析：带有参数构造方法，传递哈希表的初始化容量和加载因子
-
如果initialCapacity（初始化容量）小于0，直接抛出异常。
-
如果initialCapacity大于最大容器，initialCapacity直接等于最大容器
-
MAXIMUM_CAPACITY = 1 << 30 是最大容量 (1073741824)
-
-
如果loadFactor（加载因子）小于等于0，直接抛出异常
-
tableSizeFor（initialCapacity）方法计算哈希表的初始化容量。
-
注意：哈希表是进行计算得出的容量，而初始化容量不直接等于我们传递的参数。
-
3.tableSizeFor方法分析
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
8 4 2 1规则->无论指定了多少容量,最终经过tableSizeFor这个方法计算之后,都会遵循8421规则去初始化列表容量为了存取高效，尽量较少碰撞
解析：该方法对我们传递的初始化容量进行位移运算，位移的结果是 8 4 2 1 码
-
例如传递2，结果还是2，传递的是4，结果还是4。
-
例如传递3，结果是4，传递5，结果是8，传递20，结果是32。
4.Node 内部类分析
哈希表是采用数组+链表的实现方法，HashMap中的内部类Node非常重要，证明HashSet是一个单向链表
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
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;
}
解析：内部类Node中具有4个成员变量
-
hash，对象的哈希值
-
key，作为键的对象
-
value，作为值得对象（讲解Set集合，不牵扯值得问题）
-
next，下一个节点对象
5.存储元素的put方法源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
解析：put方法中调研putVal方法，putVal方法中调用hash方法。
-
hash(key)方法：传递要存储的元素，获取对象的哈希值
-
putVal方法，传递对象哈希值和要存储的对象key
6.putVal方法源码
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
解析：方法中进行Node对象数组的判断，如果数组是null或者长度等于0，那么就会调研resize()方法进行数组的扩容。
7.resize方法的扩容计算
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
}
解析：计算结果，新的数组容量=原始数组容量<<1，也就是乘以2。
8.确定元素存储的索引
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
解析：i = (数组长度 - 1) & 对象的哈希值，会得到一个索引，然后在此索引下tab[i]，创建链表对象。
不同哈希值的对象，也是有可能存储在同一个数组索引下。
其中resize()扩容的方法,默认是16 tab[i] = newNode(hash, key, value, null);->将元素放在数组中 i就是索引 i = (n - 1) & hash 0000 0000 0000 0000 0000 0000 0000 1111->15 & 0&0=0 0&1=0 1&1=1 0000 0000 0000 0001 0111 1000 0110 0011->96355 -------------------------------------------------------- 0000 0000 0000 0000 0000 0000 0000 0011->3
0000 0000 0000 0000 0000 0000 0000 1111->15 & 0&0=0 0&1=0 1&1=1 0000 0000 0001 0001 1111 1111 0001 0010->1179410 -------------------------------------------------------- 0000 0000 0000 0000 0000 0000 0000 0010->2
9.遇到重复哈希值的对象
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
解析：如果对象的哈希值相同，对象的equals方法返回true，判断为一个对象，进行覆盖操作。
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
解析：如果对象哈希值相同，但是对象的equals方法返回false，将对此链表进行遍历，当链表没有下一个节点的时候，创建下一个节点存储对象.
4.Map的两种遍历方式
在 Java 中，Map 接口提供了多种遍历方式，以下是两种常见的遍历方法：通过 entrySet 和通过 keySet。
1. 通过 entrySet 遍历
entrySet 方法返回一个包含 Map 中所有条目的 Set 视图。每个条目都是一个 Map.Entry 对象，包含了键和值。这种方式可以直接访问键值对，效率较高。
示例代码
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class MapEntrySetExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
// 使用 entrySet 遍历
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
for (Map.Entry<String, Integer> entry : entrySet) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println("Key: " + key + ", Value: " + value);
}
}
}
2. 通过 keySet 遍历
keySet 方法返回一个包含 Map 中所有键的 Set 视图。这种方式需要先获取键，然后再通过键来获取对应的值。这种方式适用于需要单独处理键的情况。
示例代码
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class MapKeySetExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
// 使用 keySet 遍历
Set<String> keySet = map.keySet();
for (String key : keySet) {
Integer value = map.get(key);
System.out.println("Key: " + key + ", Value: " + value);
}
}
}
性能比较
-
entrySet遍历：-
优点：直接访问键值对，避免了多次调用
get方法，效率更高。 -
适用场景：当你需要同时访问键和值时，推荐使用
entrySet遍历。
-
-
keySet遍历：-
优点：适用于只需要处理键的情况，代码可能更简洁。
-
缺点：每次都需要通过键调用
get方法来获取值，可能会有一些性能开销。 -
适用场景：当你只需要处理键，或者需要对键进行额外操作时，可以使用
keySet遍历。
-
其他遍历方式
除了上述两种常见的遍历方式，还可以使用 Java 8 引入的流（Stream）API 来遍历 Map。
使用 Stream API 遍历
import java.util.HashMap;
import java.util.Map;
public class MapStreamExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
// 使用 Stream API 遍历
map.entrySet().stream().forEach(entry -> {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println("Key: " + key + ", Value: " + value);
});
}
}
总结
-
entrySet遍历：直接访问键值对，效率更高，适用于需要同时处理键和值的场景。 -
keySet遍历：通过键获取值，适用于只需要处理键的场景，但可能会有一些性能开销。 -
Stream API：适用于需要使用函数式编程风格的场景，代码更简洁。
选择合适的遍历方式取决于你的具体需求和性能考虑。
标签：遍历,0000,哈希,04,线程,key,集合,HashMap From： https://blog.csdn.net/Elaine2391/article/details/143503909