1

As per this

Underlying data structure for HashSet is hashtable.

But I have also read that HashSet internally uses HashMap to avoid duplicate values which in turn internally uses array of buckets and LinkedList(replaced by tree in Java 8)

So is it right to say that HashSet uses HashTable as data stucture and HashMap as collection?

TreeSet implements the SortedSet interface so duplicate values are not allowed.

Does that mean that TreeSet doesn't uses HashMap internally which is used by HashSet to avoid duplicate values?Does LinkedHashSet uses HashMap internally?

As per this

Memory point of view arrays are not recommended to use.

Why? By what i read before-

Since ArrayList can’t be created for primitive data types, members of ArrayList are always references to objects at different memory locations (See this for details). Therefore in ArrayList, the actual objects are never stored at contiguous locations. References of the actual objects are stored at contiguous locations. In array, it depends whether the arrays is of primitive type or object type. In case of primitive types, actual values are contiguous locations, but in case of objects, allocation is similar to ArrayList.

Android Developer
  • 9,157
  • 18
  • 82
  • 139
  • 3
    `HashSet` uses `HashMap`, not `HashTable` (it's possible that this changed with versions). These are not things to be "learned". Please just open your IDE and look at the source code. – ernest_k Jun 07 '18 at 14:33
  • Maybe they've used `hashtable` not as a Java class but a synonym for a hash based collection – Ivan Jun 07 '18 at 14:40
  • I think you mixed two questions into one. The second part of your question should be answered by whoever wrote the article (I think his claim is not entirely true). – Sergey Kalinichenko Jun 07 '18 at 14:41
  • IMO, you should mention Java implementation and version you are talking about. – Bhesh Gurung Jun 07 '18 at 14:43
  • @ErnestKiwele So..how it should be answered "Which Data Structure HashSet internally uses?"..bcoz HashMap is not a data structure but collection..Should answer be "array and linked list" since hashmap internally uses it? – Android Developer Jun 07 '18 at 15:16

2 Answers2

7

There is a difference between lowercase hashtable, which is a generally defined data structure, and the java Hashtable class, which is a synchronized implementation of hashtable in Java that predates the HashMap and HashSet classes. HashSet does not use the Hashtable class at all. Instead, it uses the (again, lowercase h) hashtable data structure, which is implemented using HashMap. Hashtable should rarely if ever be used in contemporary code. As per the javadocs for Hashtable:

If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use ConcurrentHashMap in place of Hashtable.

As for your other questions:

  • TreeSet uses a completely different data structure from hashtable, called a red-black tree. See e.g. this detailed answer for an overview of the differences between HashSet and TreeSet.
  • I'm not sure what that quote on "Memory point of view arrays" means. That website is not well written.
shiri
  • 745
  • 6
  • 24
  • So..how it should be answered "Which Data Structure HashSet internally uses?"..bcoz HashMap is not a data structure but collection..Should answer be "array and linked list" since hashmap internally uses it? – Android Developer Jun 07 '18 at 14:55
  • As mentioned above: there is a data structure called [hashtable](https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm). If the question is about practical, internal implementation you could answer "arrays and linked list along with a hash function", I suppose. But the most accurate answer is simply "hash table". If this answer (or the other one) resolved your question, please accept it. Please consider using [best practices](https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions) when asking homework questions. – shiri Sep 10 '18 at 15:09
1

So is it right to say that HashSet uses HashTable as data structure and HashMap as collection?

Not really. Although Java has a Hashtable class, which dates back to Java 1.0, but HashSet implementation does not share code with that class. Geeks For Geeks article claims that HashSet uses hash table data structure without making a reference to any specific class. They claim that HashSet uses the approach and algorithms of hash tables, which is true: by re-using the code of HashMap, which is based on hash table approach for building associative containers, HashSet uses hash table approach as well.

Does that mean that TreeSet doesn't uses HashMap internally which is used by HashSet to avoid duplicate values?

TreeSet uses TreeMap, which uses a comparison-based (as opposed to hash-based) approach of ensuring uniqueness of its keys.

Does LinkedHashSet uses HashMap internally?

Yes. LinkedHashSet inherits from HashSet, so it uses HashMap, indirectly.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523