В чем разница в хэш-карте Java 7 и Java 8, когда оба работают по алгоритму постоянной сложности? Согласно моему пониманию хэш-поиск карт в постоянное время, генерируя хэш-ключ для объекта через хеш-функцию.Разница в хэш-карте в java 7 и 8
В Java 7 после вычисления хэша из хеш-функции, если более одного элемента имеет один и тот же хэш, чем при поиске по линейному поиску, поэтому сложность это (n). В Java 8 этот поиск выполняется бинарным поиском, поэтому сложность станет log (n). Таким образом, это понятие неверно, что хеш-карта ищет объект в постоянной сложности, потому что это не так.
На самом деле существует порог, описанный в JEP180, когда один ковш/bin имеет более TREEIFY_THRESHOLD = 8 записей, он будет преобразован в дерево. В Java 7, где коллизии были линейно искажены, существовала защита DOS: случайное семя Xord с хешами, чтобы сделать их менее предсказуемыми. Эта функция удалена в Java 8. – eckes
Если мы углубимся в реализацию, это именно то, что вы объяснили @eckes – MDaniyal
Возможно, вы столкнулись с последними проблемами специалиста Java newsletter. В течение многих лет он изучает хеширование на Java; например, указывая на то, что вам лучше убедиться, что ваши ключи карты реализуют Comparable (при использовании Java8).
@MDaniyal ответил правильно, не используя фразу, описывающую ситуацию двух или более элементов, имеющих один и тот же хеш: «хеш-столкновение». Если вы хотите глубже входить в хеш-коллизии вообще, я рекомендую начать здесь: https://en.wikipedia.org/wiki/Hash_table#Collision_resolution – Jeutnarg