Java Set实现类面试题

HashSet

Q1: HashSet的实现原理是什么？

HashSet是基于HashMap实现的，使用HashMap的key来存储元素，value统一使用一个Object对象。

java">public class HashSetPrincipleExample {
    // 模拟HashSet的基本实现
    public class SimpleHashSet<E> {
        private static final Object PRESENT = new Object();
        private HashMap<E, Object> map;
        
        public SimpleHashSet() {
            map = new HashMap<>();
        }
        
        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();
        }
    }
}

Q2: HashSet如何保证元素不重复？

java">public class HashSetDuplicationExample {
    public static class Person {
        private String name;
        private int age;
        
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
        
        // 错误的hashCode实现
        public int badHashCode() {
            return 1; // 所有对象都返回相同的hash值
        }
        
        // 正确的hashCode实现
        @Override
        public int hashCode() {
            return Objects.hash(name, age);
        }
        
        // 正确的equals实现
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Person)) return false;
            Person other = (Person) obj;
            return age == other.age && 
                   Objects.equals(name, other.name);
        }
    }
    
    public void demonstrateDuplication() {
        Set<Person> set = new HashSet<>();
        set.add(new Person("Tom", 20));
        set.add(new Person("Tom", 20)); // 不会被添加，因为equals返回true
        System.out.println("Set size: " + set.size()); // 输出1
    }
}

TreeSet

Q3: TreeSet的实现原理是什么？

TreeSet是基于TreeMap实现的，它是一个有序集合。

java">public class TreeSetPrincipleExample {
    // 1. 使用自然排序
    public void naturalOrdering() {
        TreeSet<String> set = new TreeSet<>();
        set.add("C");
        set.add("A");
        set.add("B");
        System.out.println(set); // 输出 [A, B, C]
    }
    
    // 2. 使用自定义排序
    public void customOrdering() {
        TreeSet<Person> set = new TreeSet<>((p1, p2) -> {
            int ageCompare = Integer.compare(p1.getAge(), p2.getAge());
            if (ageCompare != 0) return ageCompare;
            return p1.getName().compareTo(p2.getName());
        });
        
        set.add(new Person("Tom", 20));
        set.add(new Person("Jerry", 18));
        set.add(new Person("Bob", 20));
    }
    
    // 3. 实现Comparable接口
    public static class ComparablePerson implements Comparable<ComparablePerson> {
        private String name;
        private int age;
        
        @Override
        public int compareTo(ComparablePerson other) {
            int ageCompare = Integer.compare(this.age, other.age);
            if (ageCompare != 0) return ageCompare;
            return this.name.compareTo(other.name);
        }
    }
}

LinkedHashSet

Q4: LinkedHashSet的特点是什么？

LinkedHashSet是HashSet的子类，它使用LinkedHashMap来存储元素，维护了元素的插入顺序。

java">public class LinkedHashSetExample {
    public void demonstrateOrdering() {
        // 1. HashSet不保证顺序
        Set<String> hashSet = new HashSet<>();
        hashSet.add("C");
        hashSet.add("A");
        hashSet.add("B");
        System.out.println("HashSet: " + hashSet); // 顺序不确定
        
        // 2. LinkedHashSet保持插入顺序
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("C");
        linkedHashSet.add("A");
        linkedHashSet.add("B");
        System.out.println("LinkedHashSet: " + linkedHashSet); // 输出 [C, A, B]
        
        // 3. TreeSet按照自然顺序
        Set<String> treeSet = new TreeSet<>();
        treeSet.add("C");
        treeSet.add("A");
        treeSet.add("B");
        System.out.println("TreeSet: " + treeSet); // 输出 [A, B, C]
    }
}

性能比较

Q5: 不同Set实现类的性能对比？

java">public class SetPerformanceComparison {
    public void comparePerformance() {
        int n = 100000;
        
        // 1. 添加性能
        long start = System.currentTimeMillis();
        Set<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            hashSet.add(i);
        }
        System.out.println("HashSet添加耗时：" + (System.currentTimeMillis() - start));
        
        start = System.currentTimeMillis();
        Set<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            treeSet.add(i);
        }
        System.out.println("TreeSet添加耗时：" + (System.currentTimeMillis() - start));
        
        start = System.currentTimeMillis();
        Set<Integer> linkedHashSet = new LinkedHashSet<>();
        for (int i = 0; i < n; i++) {
            linkedHashSet.add(i);
        }
        System.out.println("LinkedHashSet添加耗时：" + (System.currentTimeMillis() - start));
        
        // 2. 查找性能
        start = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            hashSet.contains(i);
        }
        System.out.println("HashSet查找耗时：" + (System.currentTimeMillis() - start));
        
        start = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            treeSet.contains(i);
        }
        System.out.println("TreeSet查找耗时：" + (System.currentTimeMillis() - start));
    }
}

Q6: 如何选择合适的Set实现类？

java">public class SetSelectionExample {
    public void demonstrateUsage() {
        // 1. 需要最高性能，不关心顺序
        Set<String> hashSet = new HashSet<>();
        
        // 2. 需要排序
        Set<String> treeSet = new TreeSet<>();
        
        // 3. 需要记住插入顺序
        Set<String> linkedHashSet = new LinkedHashSet<>();
        
        // 4. 自定义排序示例
        Set<Person> customSortedSet = new TreeSet<>((p1, p2) -> {
            // 按年龄排序，年龄相同按姓名排序
            int ageCompare = Integer.compare(p1.getAge(), p2.getAge());
            if (ageCompare != 0) return ageCompare;
            return p1.getName().compareTo(p2.getName());
        });
        
        // 5. 需要线程安全
        Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>());
        
        // 6. 并发环境下的有序Set
        Set<String> concurrentSkipListSet = new ConcurrentSkipListSet<>();
    }
    
    // 使用场景示例
    public void usageScenarios() {
        // 1. 去重场景
        Set<String> uniqueEmails = new HashSet<>();
        uniqueEmails.add("user@example.com");
        uniqueEmails.add("user@example.com"); // 重复邮箱不会被添加
        
        // 2. 排序场景
        Set<Integer> sortedNumbers = new TreeSet<>();
        sortedNumbers.add(3);
        sortedNumbers.add(1);
        sortedNumbers.add(2);
        // 遍历时自动排序
        
        // 3. 记录访问顺序场景
        Set<String> pageViews = new LinkedHashSet<>();
        pageViews.add("/home");
        pageViews.add("/products");
        pageViews.add("/about");
        // 保持用户访问页面的顺序
    }
}