Are sets really implemented as cards?

Question

Throughout StackOverflow, I see the answer:

A Set is just a Map , except that it Key is Value . This is why both Set and Map cannot have duplicates, as this violates the unique Key principle.

But then I see (for example) that Set is not related to Map . Infact, Map not part of Collections , but Set is. But for me this does not make sense, because most likely the implementation of the HashSet in the JDK is very similar to the implementation of the HashMap , except that they both come from different interfaces.

What is the relationship between Set and Map in this regard?

Answer 1

The Set and Map interfaces are not connected (except for the keySet() and entrySet() methods of the Map interface, which return the Set supported by Map ).

However, several Set implementations use the fallback Map implementation to store their data ( Set elements become keys in the base Map , and the values ​​of the base Map are just dummy objects). This is true for HashSet and TreeSet .

This is mentioned in Javadoc :

open class hashset
extends AbstractSet
implements Set, Cloneable, Serializable

This class implements the Set, interface , supported by a hash table (actually an instance of a HashMap) .

And :

public class TreeSet
extends AbstractSet
implements NavigableSet, Cloneable, Serializable

TreeMap based NavigableSet implementation.

Answer 2

In fact, the installation interface is not supported by the card or anything else. However, a HashSet is implemented using the Hashmap as the actual data structure.

The set does not indicate that the card is in javadoc

A collection that does not contain duplicate elements. More formally, the sets do not contain a pair of elements e1 and e2 such that e1.equals (e2) and no more than one zero element. As its name implies, this interface models a mathematical abstract abstraction.

However, according to javadoc, the Hashset uses the interval between the HashMap to ensure that unique data is preserved.

This class implements the Set interface, supported by a hash table (actually an instance of HashMap). It makes no guarantees regarding the iterative recruitment order; in particular, it does not guarantee that order will remain constant over time. This class allows a null element.

It saves the value added in the "Set inside the card as a key" field, not the value. It adds the same constant single object to the values ​​for all records.

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

Here, PRESENT is a static value object that should be stored on a memory card.

  private static final Object PRESENT = new Object(); 

The Backing Map object is created when we call various HashSet constructors: -

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

public Read more ... HashSet (collection c) {map = new HashMap (Math.max ((int) (c.size () /. 75f) + 1, 16)); addAll (s); }

public Read more ... HashSet (int initialCapacity, float loadFactor) {map = new HashMap (initialCapacity, loadFactor); }

The whole source can be seen on this link.

Refer to javadocs for other Set implementations supported by Map.