java significance of hashing linkedHashSet

Question

I know following things about linkedHashSet

• it maintains insertion order
• uses LinkedList to preserve order
• my question is how does hashing come into picture ??

I understand If hashing is used then the concept of bucketing comes in

However, from checking the code in the JDK it seems that LinkedHashSet implementation contains only constructor and no implementation, so I guess all the logic happens in HashSet?

• so hashSet uses LinkedList by default ?

Let me put my question this way ... if objective is to write a collection that

1. maintains unique values
2. preserves insertion order using a linked list THEN ... it can easily be done without Hashing ... may be we can call this collection LinkedSet

saw a similar question what's the difference between HashSet and LinkedHashSet but not very helpful

Let me know if i need to explain my question more

Answer 1

False. The implementation of LinkedHashSet is really all in LinkedHashMap. (And the implementation of HashSet is really all in HashMap. Le gasp!)

HashSet has no linked list at all.

It's entirely possible to write a LinkedSet collection backed by a linked list, that keeps elements unique -- it's just that its performance will be pretty crappy.

Answer 2

It's an 'interesting' implementation. The constructors for LinkedHashSet defer to package-private constructors in HashSet which setup the data structure (a LinkedHashMap) for maintaining iteration order.

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

The API designers could simply have exposed this constructor as public, with appropriate documentation, but I guess they wanted the code to be more 'self-documenting'.

Answer 3

If you look closely, you will see it is actually using some protected constructors on the HashSet that are there just for it, not regular ones. e.g.,

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

So the keySet being used to back the LinkedHashSet is in fact coming from the implementation of LinkedHashMap, not a regular HashMap like a regular HashSet. It doesn't actually use java.util.LinkedList. It just maintains pointers that form a list within the implementation of the bucket contents (Map.Entry<K,V>)

316    private static class Entry<K,V> extends HashMap.Entry<K,V> {
317        // These fields comprise the doubly linked list used for iteration.
318        Entry<K,V> before, after;
319
320        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
321            super(hash, key, value, next);
322        }

Hashing comes into the picture because it's an easy way to create a collection that enforces uniqueness and offers constant-time performance for most operations. Sure we could just use a linked list and add uniqueness checking, but the time for several operations would become O(N) cause you'd have to iterate the whole list to check for duplicates.

Answer 4

Code Sample

Set<Registeration> registerationSet = new LinkedHashSet<>();
registerationSet.add(new Registeration());

Explanation of Line2.

1. computes hashCode for Registeration object
2. search for hashCode in registerationSet to locate the bucket
3. check for equal object in shortlisted bucket
   • 3.1. if equal found, replace it, with new objects reference
   • 3.2. if not found, append/add Registeration object's reference in bucket

Parallel to it,

A List maintains entry order/queue of all elements inserted

1. Always, add new reference to the end
2. In case of replacement(3.1. in above), remove previous occurrence.

Answer 5

For a Specific answer to your question

• how does hashing come into picture? (in a LinkedHashSet)

What the Java Docs say...

• Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets.
• This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).

The buckets accessed by a hashcode is used to speed up random access, and the LinkedList implementation is for returning an iterator which spits out elements in insertion order.

Hope i have answered your question?