18.2.4 HashSet去重原理与TreeSet排序机制
1. HashSet去重原理
1.1 HashSet基本结构
HashSet基于HashMap实现，利用HashMap的key唯一性来保证元素不重复。
public class HashSet<E> extends AbstractSet<E> implements Set<E> {
// 内部使用HashMap存储数据
private transient HashMap<E,Object> map;
// 所有value都使用这个虚拟对象
private static final Object PRESENT = new Object();
// 构造方法
public HashSet() {
map = new HashMap<>();
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
}
1.2 HashSet的核心操作
public class HashSetOperations {
// 添加元素
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
// 删除元素
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
// 检查是否包含元素
public boolean contains(Object o) {
return map.containsKey(o);
}
// 获取大小
public int size() {
return map.size();
}
// 清空集合
public void clear() {
map.clear();
}
// 判断是否为空
public boolean isEmpty() {
return map.isEmpty();
}
}
1.3 HashSet去重机制详解
public class HashSetDeduplication {
public void demonstrateDeduplication() {
HashSet<String> set = new HashSet<>();
// 添加重复元素
System.out.println(set.add("apple")); // true - 首次添加
System.out.println(set.add("banana")); // true - 首次添加
System.out.println(set.add("apple")); // false - 重复元素
System.out.println("Set size: " + set.size()); // 2
System.out.println("Set contents: " + set); // [apple, banana]
}
// 自定义对象去重示例
public void customObjectDeduplication() {
HashSet<Person> personSet = new HashSet<>();
Person p1 = new Person("张三", 25);
Person p2 = new Person("李四", 30);
Person p3 = new Person("张三", 25); // 与p1相同
personSet.add(p1);
personSet.add(p2);
personSet.add(p3);
System.out.println("Person set size: " + personSet.size()); // 取决于Person类的equals和hashCode实现
}
// 正确实现equals和hashCode的Person类
static class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Person person = (Person) obj;
return age == person.age && Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public String toString() {
return "Person{name='" + name + "', age=" + age + "}";
}
}
}
1.4 HashSet去重原理深入分析
public class HashSetInternalMechanism {
// 模拟HashSet的add方法内部逻辑
public boolean simulateAdd(Object element) {
// 1. 计算元素的hashCode
int hash = element.hashCode();
System.out.println("Element hashCode: " + hash);
// 2. 根据hash值定位到HashMap的桶
int bucketIndex = hash & (capacity - 1); // 简化的索引计算
System.out.println("Bucket index: " + bucketIndex);
// 3. 在桶中查找是否存在相同元素
// 这里会调用equals方法进行比较
for (Object existing : getBucketElements(bucketIndex)) {
if (existing.equals(element)) {
System.out.println("Element already exists, not added");
return false; // 元素已存在，不添加
}
}
// 4. 元素不存在，添加到集合中
addToBucket(bucketIndex, element);
System.out.println("Element added successfully");
return true;
}
// 演示hash冲突情况下的去重
public void demonstrateHashCollision() {
HashSet<BadHashObject> set = new HashSet<>();
BadHashObject obj1 = new BadHashObject("A", 1);
BadHashObject obj2 = new BadHashObject("B", 2);
BadHashObject obj3 = new BadHashObject("A", 1); // 与obj1相同
set.add(obj1);
set.add(obj2);
set.add(obj3);
System.out.println("Set size: " + set.size()); // 2，因为obj1和obj3相同
}
// 故意设计hash冲突的类
static class BadHashObject {
private String value;
private int id;
public BadHashObject(String value, int id) {
this.value = value;
this.id = id;
}
@Override
public int hashCode() {
return 1; // 所有对象都返回相同的hash值，制造冲突
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
BadHashObject that = (BadHashObject) obj;
return id == that.id && Objects.equals(value, that.value);
}
@Override
public String toString() {
return "BadHashObject{value='" + value + "', id=" + id + "}";
}
}
}
2. TreeSet排序机制
2.1 TreeSet基本结构
TreeSet基于红黑树实现，内部使用TreeMap存储数据，自动保持元素的有序性。
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E> {
// 内部使用NavigableMap（实际是TreeMap）
private transient NavigableMap<E,Object> m;
// 所有value都使用这个虚拟对象
private static final Object PRESENT = new Object();
// 构造方法
public TreeSet() {
this(new TreeMap<>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
}
2.2 TreeSet的核心操作
public class TreeSetOperations {
// 添加元素
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}
// 删除元素
public boolean remove(Object o) {
return m.remove(o) == PRESENT;
}
// 检查是否包含元素
public boolean contains(Object o) {
return m.containsKey(o);
}
// 获取第一个元素
public E first() {
return m.firstKey();
}
// 获取最后一个元素
public E last() {
return m.lastKey();
}
// 获取小于指定元素的最大元素
public E lower(E e) {
return m.lowerKey(e);
}
// 获取大于指定元素的最小元素
public E higher(E e) {
return m.higherKey(e);
}
// 获取子集
public SortedSet<E> subSet(E fromElement, E toElement) {
return new TreeSet<>(m.subMap(fromElement, true, toElement, false));
}
}
2.3 TreeSet排序机制详解
public class TreeSetSorting {
// 自然排序示例
public void naturalOrderSorting() {
TreeSet<Integer> numbers = new TreeSet<>();
// 添加元素（无序）
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
numbers.add(9);
numbers.add(3);
System.out.println("TreeSet (natural order): " + numbers);
// 输出: [1, 2, 3, 5, 8, 9] - 自动排序
}
// 自定义排序示例
public void customComparatorSorting() {
// 降序排列
TreeSet<Integer> descendingNumbers = new TreeSet<>(Collections.reverseOrder());
descendingNumbers.add(5);
descendingNumbers.add(2);
descendingNumbers.add(8);
descendingNumbers.add(1);
System.out.println("TreeSet (descending): " + descendingNumbers);
// 输出: [8, 5, 2, 1]
// 字符串长度排序
TreeSet<String> stringsByLength = new TreeSet<>((s1, s2) -> {
int lengthCompare = Integer.compare(s1.length(), s2.length());
return lengthCompare != 0 ? lengthCompare : s1.compareTo(s2);
});
stringsByLength.add("apple");
stringsByLength.add("banana");
stringsByLength.add("cat");
stringsByLength.add("dog");
System.out.println("TreeSet (by length): " + stringsByLength);
// 输出: [cat, dog, apple, banana]
}
// 自定义对象排序
public void customObjectSorting() {
TreeSet<Student> students = new TreeSet<>();
students.add(new Student("张三", 85));
students.add(new Student("李四", 92));
students.add(new Student("王五", 78));
students.add(new Student("赵六", 95));
System.out.println("Students sorted by score:");
for (Student student : students) {
System.out.println(student);
}
}
// 实现Comparable接口的Student类
static class Student implements Comparable<Student> {
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student other) {
// 按分数降序排列
int scoreCompare = Integer.compare(other.score, this.score);
// 如果分数相同，按姓名升序排列
return scoreCompare != 0 ? scoreCompare : this.name.compareTo(other.name);
}
@Override
public String toString() {
return "Student{name='" + name + "', score=" + score + "}";
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Student student = (Student) obj;
return score == student.score && Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(name, score);
}
}
}
2.4 TreeSet内部红黑树机制
public class TreeSetInternalMechanism {
// 模拟TreeSet的add方法内部逻辑
public boolean simulateAdd(Comparable element, TreeNode root) {
if (root == null) {
// 空树，直接插入作为根节点
root = new TreeNode(element);
return true;
}
TreeNode current = root;
TreeNode parent = null;
int compareResult;
// 查找插入位置
while (current != null) {
parent = current;
compareResult = element.compareTo(current.value);
if (compareResult < 0) {
current = current.left;
} else if (compareResult > 0) {
current = current.right;
} else {
// 元素已存在，不插入
return false;
}
}
// 创建新节点并插入
TreeNode newNode = new TreeNode(element);
compareResult = element.compareTo(parent.value);
if (compareResult < 0) {
parent.left = newNode;
} else {
parent.right = newNode;
}
newNode.parent = parent;
// 红黑树平衡调整（简化）
fixAfterInsertion(newNode);
return true;
}
// 红黑树节点
static class TreeNode {
Comparable value;
TreeNode left;
TreeNode right;
TreeNode parent;
boolean red = true; // 新节点默认为红色
TreeNode(Comparable value) {
this.value = value;
}
}
// 插入后的平衡调整（简化版本）
private void fixAfterInsertion(TreeNode node) {
// 红黑树的平衡调整逻辑
// 这里是简化版本，实际实现更复杂
while (node != null && node != root && node.parent.red) {
if (node.parent == node.parent.parent.left) {
TreeNode uncle = node.parent.parent.right;
if (uncle != null && uncle.red) {
// Case 1: 叔叔节点是红色
node.parent.red = false;
uncle.red = false;
node.parent.parent.red = true;
node = node.parent.parent;
} else {
// Case 2 & 3: 叔叔节点是黑色或null
if (node == node.parent.right) {
node = node.parent;
rotateLeft(node);
}
node.parent.red = false;
node.parent.parent.red = true;
rotateRight(node.parent.parent);
}
} else {
// 对称情况
TreeNode uncle = node.parent.parent.left;
if (uncle != null && uncle.red) {
node.parent.red = false;
uncle.red = false;
node.parent.parent.red = true;
node = node.parent.parent;
} else {
if (node == node.parent.left) {
node = node.parent;
rotateRight(node);
}
node.parent.red = false;
node.parent.parent.red = true;
rotateLeft(node.parent.parent);
}
}
}
root.red = false; // 根节点始终为黑色
}
// 左旋转
private void rotateLeft(TreeNode nod
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
Java面试圣经 文章被收录于专栏
Java面试圣经，带你练透java圣经
查看14道真题和解析