如何在 Java 中实现一个集合数据结构?

How to implement a Set Data Structure in Java?

我一直想知道您将如何在 Java 中实现 Set。我们能否像使用 LinkedList 和包含 Key 和 Value 的对象(Cell)实现 HashMap 一样实现它?您将如何处理唯一性部分?

基本上,Set 只是一个只包含键的 Map。所以你应该了解映射算法。注意:例如 HashSet 实际上只是 HashMap 的适配器。 HashSet 的添加方法仅使用 HashMap.put(value , SomeDummyValue).

Set 内部实现了一个 map.So 集合中的每个值只是一个键 map.So 它的唯一性得以维护。

Here 是 link.So,您可以清楚地了解 set 的内部工作原理。 也很少堆栈答案。 First , Second

下面是解释上述答案的代码片段

public HashSet() { map = new HashMap<>(); }
private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

// Since PRESENT is a constant, for all keys we have same value in backup HashMap called map.

public Iterator<E> iterator() {
    return map.keySet().iterator();
}
class HashSetBasicImpl<K> {

        static class Entry<K> {
            private K key;
            private Entry<K> next;

            Entry(K key) {
                key = key;
                next = null;
            }
        }

        private Entry<K>[] entries;

        public HashSetBasicImpl() {
            // fixed size
            map =new Entry[100];
        }

        public boolean contains(K key) {
            int idx = key.hashCode();
            Entry<K> start = entries[idx];
            while(start != null) {
                if(start.key == key) {
                    return true;
                }
                start = start.next;
            }
            return  false;

        }

        public boolean add(K key) {

            Entry<K> entry = new Entry(key);
            int idx = key.hashCode();

            // check if entry exists
           if(contains(key)) {
               return false;
           }
            // add as first entry
            start = entries[idx];
            if(start == null) {
                entries[idx]= new Entry(key);
                return true;
            }
            // add as nth entry
            Entry prev = null;
            while(start != null) {
                prev = start;
                start = start.next;
            }
            prev.next = new Entry(key);
            return true;
        }
}

简答:地图

基础知识优先

集合数据结构有哪些特点?

  1. 每个元素只存储一次。
  2. 查询 Set 中的项目应该是最快的,即 O(1)
  3. 如果要插入的项目已经存在于集合中,则不要插入。如果不存在,则插入。

仔细一看,到底是哪个数据结构可以实现的呢? 答案是 Map,因为我们只记录出现的值。并且我们可以在O(1)时间查询。