Почему хеш-таблица вырождается в связанный список, когда реализация hashcode () возвращает постоянное значение?

Question

// The worst possible legal hash function - never use!
@Override public int hashCode() { return 42; }

Это законно, поскольку гарантирует, что равные объекты имеют одинаковый хэш-код.Это ужасно, потому что гарантирует, что каждый объект имеет одинаковый хэш-код.Поэтому каждый объект хешируется в одно и то же ведро, а хеш-таблицы вырождаются в связанные списки.Программы, которые должны работать в линейном времени, вместо этого работают в квадратичном времени.

Я пытаюсь понять вышесказанное (цитата из стр. 47, пункт 9, Эффективная Java Джошуа Блоха).

Я вижу это следующим образом (рассмотрим следующий код):

Map<String, String> h = new HashMap<String,String>();
h.put("key1", "value1");
h.put("key1", "value2");

То, что происходит со второй командой h.put("key1",...), выглядит следующим образом: 1. Получите хэш-код key1 2. Получитеблок, представляющий вышеуказанный хэш-код 3. Внутри этого блока для каждого объекта вызовите метод equals, чтобы определить, существует ли идентичный объект.

Это немного быстрее, потому что сначала вы находите «группу» (сегмент) объектов, а затем фактический объект.

Теперь, когда реализация хэш-кода такова, что она возвращает то же целое число (например, 42 выше) для ALL объектов, тогдатолько один сегмент, и метод equals должен вызываться один за другим для каждого объекта во всей hashmap / hashtable.Это так же плохо, как связанный список, потому что, если объекты находятся в связанном списке, то тоже придется проходить через них один за другим, сравнивая (называя равенство) каждый объект.

Вот почему, как было сказано, хеш-таблицы вырождаются в связанный список?

(Прошу прощения за многословие приведенного выше текста. Мне не яснодостаточно в моих понятиях, чтобы изложить это более кратко)

Answer 1

HashTable - это массив с функцией отображения (hashCode). При вставке в массив вы вычисляете позицию и вставляете туда элемент.

НО, hashCode не гарантирует, что каждый элемент будет иметь различную позицию, поэтому некоторые объекты могут сталкиваться (иметь один и тот же адрес), и hashTable должен разрешить это. Есть два общих подхода, как это сделать.

Отдельная цепочка

В отдельной цепочке (используемой в Java) каждый индекс массива содержит связанный список - поэтому каждая корзина (позиция) имеет бесконечную емкость. Следовательно, если ваш hashCode возвращает только одно значение, вы используете только один понравившийся список => hashTable - это связанный список.

Линейное зондирование

Второй подход - линейное зондирование. При линейном зондировании внутренний массив - это действительно обычный массив элементов. Когда вы узнаете, что позиция уже занята, вы перебираете массив и помещаете новый элемент в первую пустую позицию.

Итак, ваш impl hashCode генерирует значение для каждого элемента, вы генерируете только коллизии, поэтому вы пытаетесь поместить все элементы в один и тот же индекс и, поскольку он всегда занят, вы перебираете все расположенные элементы и размещаете новый элемент в конце this structure. Если вы снова прочитаете, что делаете, вы должны увидеть, что вы используете только другую (можно сказать, неявную) реализацию связанного списка.

Почему бы не сделать это

Вы действительно не должны возвращать постоянные значения, потому что хеш-таблицы созданы для обеспечения O(1) ожидаемой сложности операций поиска и вставки (из-за хеш-функции, которая возвращает разные адреса для (почти) каждого отдельного объекта). Если вы вернете только одно значение, реализация снизится до связного списка с O(n) для обеих операций.

Answer 2

Да, ваше понимание кажется точным.Однако это не как связанный список.Фактическая внутренняя реализация записей, которые совместно используют общий сегмент , представляет собой простой старый связанный список.Контейнер содержит Map.Entry в начале списка, и каждая запись имеет прямой указатель на следующего участника своего сегмента.(Конечно, для реализации HashMap, встроенной в Java.)

Answer 3

Хеш-таблицы - при правильном использовании - в среднем обеспечивают постоянный поиск.С точки зрения сложности времени, постоянное время так же хорошо, как и оно.

Связанные списки предлагают поиск в линейном времени.Линейное время (т. Е. Просмотр каждого элемента по очереди) так же плохо, как и получается.

Когда хэш-таблица используется не так, как описано Блохом, ее поведение поиска вырождается в поведениесвязанный список, просто потому что он становится связанным списком.

Подобные вещи можно сказать и о других операциях.