面试题：自定义实现一个符合Java集合框架规范的高性能集合类

设计思路

数据结构：采用HashMap作为底层数据结构。HashMap基于哈希表实现，在插入、删除和查找操作上平均时间复杂度为 O(1)，可以满足高效操作的需求。
实现接口：实现Set接口，因为Set集合的特点是不允许重复元素，符合题目中集合类的一般性要求。具体实现java.util.Set接口下的add（插入）、remove（删除）、contains（查找）等方法。

代码实现

import java.util.*;

public class CustomSet<T> implements Set<T> {
    private Map<T, Object> map;
    private static final Object PRESENT = new Object();

    public CustomSet() {
        map = new HashMap<>();
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    @Override
    public Iterator<T> iterator() {
        return map.keySet().iterator();
    }

    @Override
    public Object[] toArray() {
        return map.keySet().toArray();
    }

    @Override
    public <T1> T1[] toArray(T1[] a) {
        return map.keySet().toArray(a);
    }

    @Override
    public boolean add(T t) {
        return map.put(t, PRESENT) == null;
    }

    @Override
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return map.keySet().containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean modified = false;
        for (T t : c) {
            if (add(t)) {
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return map.keySet().retainAll(c);
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return map.keySet().removeAll(c);
    }

    @Override
    public void clear() {
        map.clear();
    }
}

算法说明

插入（add方法）：通过HashMap的put方法将元素作为键存入map，值统一使用一个常量PRESENT。如果put方法返回null，说明该元素是首次插入，返回true；否则返回false，表示元素已存在。
删除（remove方法）：调用HashMap的remove方法移除指定元素，若成功移除（返回PRESENT）则返回true，否则返回false。
查找（contains方法）：直接调用HashMap的containsKey方法判断元素是否存在。

性能优化措施

负载因子调整：HashMap默认负载因子为0.75，在初始化HashMap时可以根据实际使用场景调整负载因子。如果预计元素数量较多且内存充足，可以适当增大负载因子以减少哈希表的扩容次数，但会增加哈希冲突的概率；反之，如果内存紧张且需要尽量减少冲突，可以适当减小负载因子，但会导致更多的扩容操作。
初始容量设置：在创建CustomSet时，如果能预先估计元素的大致数量，可以在构造函数中传入合适的初始容量给HashMap，避免频繁的扩容操作。扩容操作会重新计算哈希值并移动元素，消耗较大的性能。

这样设计的集合类能在满足Java集合框架规范的同时，高效地完成插入、删除和查找操作。

面试题：自定义实现一个符合Java集合框架规范的高性能集合类

知识考点

面试题答案

设计思路

代码实现

算法说明

性能优化措施