### 6. 序列化与克隆
#### 6.1 序列化
`HashSet` 实现了 `Serializable` 接口,允许其对象被序列化。
```java
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
s.writeInt(map.size());
for (E e : map.keySet())
s.writeObject(e);
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
int capacity = s.readInt();
float loadFactor = s.readFloat();
int size = s.readInt();
map = ((size >= 0) ? new HashMap<>(capacity, loadFactor) : new HashMap<>());
for (int i = 0; i < size; i++) {
@SuppressWarnings("unchecked")
E e = (E) s.readObject();
map.put(e, PRESENT);
}
}
```
- `writeObject`:序列化 `HashSet` 对象,包括哈希表的容量、加载因子和所有键。
- `readObject`:反序列化 `HashSet` 对象,根据序列化的数据恢复哈希表结构和所有键。
#### 6.2 克隆
`HashSet` 实现了 `Cloneable` 接口,提供了 `clone` 方法用于深度克隆。
```java
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
```
- `clone` 方法通过 `super.clone` 创建一个新的 `HashSet` 实例,并深度克隆内部的 `HashMap`。
### 7. 性能分析
#### 7.1 时间复杂度
- **添加元素**:在平均情况下,`HashSet` 的添加操作时间复杂度为 O(1)。在最坏情况下(大量哈希冲突),时间复杂度为 O(n)。
- **删除元素**:在平均情况下,`HashSet` 的删除操作时间复杂度为 O(1)。在最坏情况下(大量哈希冲突),时间复杂度为 O(n)。
- **判断是否包含元素**:在平均情况下,`HashSet` 的包含操作时间复杂度为 O(1)。在最坏情况下(大量哈希冲突),时间复杂度为 O(n)。
#### 7.2 空间复杂度
`HashSet` 使用 `HashMap` 存储元素,因此其空间复杂度主要取决于 `HashMap` 的容量和加载因子。默认情况下
`HashSet` 使用的空间复杂度与 `HashMap` 的容量和加载因子有关。默认情况下,`HashMap` 的初始容量为16,加载因子为0.75,这意味着在重新调整大小之前可以容纳12个元素。随着元素的增加,`HashMap` 会根据需要动态扩展容量,从而保持较低的哈希冲突。
### 8. `HashSet` 的应用场景
#### 8.1 数据去重
`HashSet` 主要用于需要确保集合中元素唯一性的场景。它可以高效地检测重复元素并删除它们。
```java
import java.util.HashSet;
import java.util.Set;
public class DuplicateRemover {
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 1, 2, 4, 5};
Set<Integer> uniqueNumbers = new HashSet<>();
for (int number : numbers) {
uniqueNumbers.add(number);
}
System.out.println("Unique numbers: " + uniqueNumbers);
}
}
```
#### 8.2 查找操作
由于 `HashSet` 基于哈希表实现,因此查找操作非常高效,适用于需要快速查找元素的场景。
```java
import java.util.HashSet;
import java.util.Set;
public class MembershipTest {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("cherry");
if (set.contains("banana")) {
System.out.println("Set contains banana");
} else {
System.out.println("Set does not contain banana");
}
}
}
```