Results 1 to 4 of 4

Thread: LinkedHashSet

  1. #1
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default LinkedHashSet

    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?

  2. #2
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    12,086
    Rep Power
    20

    Default Re: 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.
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  3. #3
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Re: LinkedHashSet

    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?

  4. #4
    jashburn is offline Senior Member
    Join Date
    Feb 2014
    Posts
    219
    Rep Power
    1

    Default Re: LinkedHashSet

    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •