LinkedHashSet=Linked + Hash +Set
In linkedHashSet are the elements stored according to the insertion order or according to the hash value. If the elements are stored according to the insertion order then why is it not named as LinkedSet instead of LinkedHashSet? Why is the word hash used in LinkedHashSet?
Did you read the API?
If you did and didn't understand it, it would probably help if you explained where it confuses you.
Just happened to read it. It says
Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries.
I understand about using doubly linked list for maintaining insertion order but how is the hash table used in this. Hash table is a map. I am not able to relate how hash table is used in LinkedHashSet and what purpose does it serve?
According to the HashSet class description a HashSet (which LinkedHashSet extends) is backed by a HashMap. Conceptually when an element is added to a HashSet, a hash function is used to decide on the location to store the element. Under the covers a call to HashSet.add(e) results in a follow up call to the internal HashMap's put(e, constant) method. ("Constant" is used because a HashSet is only interested in the key, i.e., the element (e) to be added, and not the value that will be placed into the internal HashMap.) This in turn places the element's
- hash value (computed using the hash function)
- key (which is the element itself)
- value (which is a constant)
into the HashMap's internal data structure.
This is an example of code reuse. If HashSet does not reuse HashMap for storing elements, HashSet will need to be written using pretty much a subset of HashMap's code. If later Oracle decide to, e.g., improve the hash function, the improvement will need to be done in both HashSet and HashMap rather than just HashMap alone from which HashSet will automatically benefit.
LinkedHashSet inherits all of the above from HashSet. The difference is the use of the linked list to track insertion order of elements. When a LinkedHashSet is instantiated, a LinkedHashMap (which extends HashMap, and so behaves just like a HashMap apart from than the tracking of insertion order) is used as the backing hash map. It is in the LinkedHashMap where the linked list to track the insertion order of the LinkedHashMap's keys (which corresponds to the LinkedHashSet's elements) comes from.
As mentioned above, a hash function is used to decide on the location to store an element added to a HashSet. It is this hash function that makes it really quick to find out if the element already exists in the HashSet. Remember that a HashSet does not store duplicate elements, and so it needs to check for each element to be added if it already has the element. The hash function allows it to go straight to the expected location to do the check, rather than having to go through all its elements one by one. This is also the reason HashSet.contains(e) is much faster than ArrayList.contains(e), especially when they have a lot of elements stored.