CODEWITHSUNDEEP
javahashsethashcode
Tomer Hochbaum
Tomer Hochbaum

Reputation: 67

Java's hashSet handling mult items with same hashcode

I couldn't find an answer to this question anywhere. I added 100,000 different strings with the same hash code to a HashSet in java, and it took 63 ms. (Linked List took 37373 ms)

I was wondering how Java's hashSet handles this situation.

(It was a part of an exercise, and my implementations took MUCH longer - both the "Open" implementation - where the Strings are added to Linked lists, ans "Closed" implementation - where I find the next open cell with a given formula).

Upvotes: 0

Views: 88

Answers (1)

user158037
user158037

Reputation: 2603

In OpenJDK HashMaps & HashSets fallback to TreeMap/TreeSet if there are to many items in by-hash buckets:

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l145

Also don't compare with LinkedList, compare to ArrayList instead - LinkedList is slower and almost never used/useful.

Upvotes: 1

Related Questions