Java hashSet обрабатывает несколько элементов с одинаковым хэш-кодом

Question

Я нигде не мог найти ответ на этот вопрос. Я добавил 100 000 различных строк с одинаковым хеш-кодом в HashSet в Java, и это заняло 63 мс. (Связанный список занял 37373 мс)

Мне было интересно, как Java hashSet справляется с этой ситуацией.

(Это было частью упражнения, и мои реализации заняли НАМНОГО дольше - как «открытая» реализация - где строки добавляются в связанные списки, так и «закрытая» реализация - где я нахожу следующую открытую ячейку с данная формула).

Answer 1

В OpenJDK HashMaps & HashSets откат к TreeMap / TreeSet, если есть много элементов в корзинах хэша:

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

Также не сравнивайте с LinkedList, сравните с ArrayList вместо этого - LinkedList медленнее и почти никогда не используется / полезен.