#java #algorithm #equals #hashcode
#java #алгоритм #равно #хэш-код
Вопрос:
// 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, чтобы определить, существует ли идентичный объект.
Это быстрее, потому что сначала вы находите «группу» (корзину) объектов, а затем фактический объект.
Теперь, когда реализация hashcode такова, что она возвращает одно и то же целое число (например, 42 указанное выше) для ВСЕХ объектов, тогда существует только один сегмент, и метод equals необходимо вызывать по одному для каждого объекта во всей хэш-карте / хэш-таблице. Это так же плохо, как связанный список, потому что, если объекты находятся в связанном списке, тогда тоже нужно будет просматривать их один за другим, сравнивая (вызывая equals) каждый объект.
Именно поэтому, как было сказано, хэш-таблицы вырождаются в связанный список ?
(Я прошу прощения за многословность приведенного выше текста. Я недостаточно ясен в своих концепциях, чтобы изложить это более кратко)
Комментарии:
1. «Я прошу прощения за многословность приведенного выше текста». Материал, спасибо за интересный вопрос.
2. Это немного вводящее в заблуждение обобщение, чтобы сказать, что хеш-таблицы вырождаются. Более правильным утверждением было бы то, что реализация вырождается в поиск по корзине, который в данном случае реализуется как связанный список.
Ответ №1:
Хеш-таблица — это массив с функцией отображения (hashCode). При вставке в массив вы вычисляете позицию и вставляете туда элемент.
НО хеш-код не гарантирует, что каждый элемент будет иметь разную позицию, поэтому некоторые объекты могут сталкиваться (иметь один и тот же адрес), и хеш-таблица должна разрешить это. Есть два распространенных подхода, как это сделать.
Отдельная цепочка
В отдельной цепочке (используемой в Java) каждый индекс массива содержит связанный список, поэтому каждая ячейка (позиция) имеет бесконечную емкость. Следовательно, если ваш хеш-код возвращает только одно значение, вы используете только один список понравившихся => Хеш-таблица — это связанный список.
Линейное зондирование
Второй подход — линейное зондирование. При линейном зондировании внутренний массив на самом деле представляет собой обычный массив элементов. Когда вы обнаружите, что позиция уже занята, вы выполняете итерацию по массиву и помещаете новый элемент в первую пустую позицию.
Итак, я ваш impl hashCode генерирует постоянное значение для каждого элемента, вы генерируете только коллизии, следовательно, вы пытаетесь поместить все элементы в один и тот же индекс и, поскольку он всегда занят, вы перебираете все размещенные элементы и помещаете новый элемент в конец this structure . . Если вы снова прочитаете, что вы делаете, вы должны увидеть, что вы используете только другую (можно сказать, неявную) реализацию связанного списка.
Почему бы этого не сделать
Вы действительно не должны возвращать постоянные значения, потому что хеш-таблицы создаются для обеспечения O(1) ожидаемой сложности операций поиска и вставки (из-за хеш-функции, которая возвращает разные адреса для (почти) каждого отдельного объекта). Если вы возвращаете только одно значение, реализация деградирует до связанного списка с O(n) для обеих операций.
Комментарии:
1. IIRC, реализации Sun обоих
HashtableиHashMapиспользуют отдельные цепочки, а не линейное зондирование.2. Вау, спасибо, что нашли время, чтобы ответить так подробно. Ваше объяснение отлично ответило на мой вопрос. Спасибо!!
3. Возможно, стоит отметить, что линейное зондирование — это всего лишь частный случай более обобщенного подхода к зондированию; для коллекций «только для добавления» обобщенные подходы к зондированию могут достигать производительности, сравнимой с отдельными цепочками, но с меньшими затратами на хранение (линейное зондирование часто имеет гораздо худшую производительность, за исключением случаев, когда хэш-таблицы в основном пусты). Большая проблема с пробными подходами заключается в том, что удаление элементов затруднено. Это немного проще с линейным зондированием, чем с другими подходами, но в целом отдельная цепочка лучше, если коллекция должна поддерживать удаление элемента .
Ответ №2:
Да, ваше понимание кажется точным. Однако это не похоже на связанный список. Фактическая внутренняя реализация записей, которые используют общую корзину, представляет собой обычный старый связанный список. Корзина содержит Map.Entry во главе списка, и каждая запись имеет прямой указатель на следующего пользователя ее корзины. (Для реализации HashMap, встроенной в Java, конечно.)
Ответ №3:
Хеш-таблицы — при правильном использовании — предлагают поиск в среднем в течение постоянного времени. С точки зрения временной сложности постоянное время настолько хорошо, насколько это возможно.
Связанные списки предлагают поиск в линейном времени. Линейное время (т. Е. Просмотр каждого элемента по очереди) настолько плохо, насколько это возможно.
Когда хэш-таблица неправильно используется способом, описанным Блохом, ее поведение при поиске вырождается в поведение связанного списка просто потому, что он фактически становится связанным списком.
Аналогичные вещи можно сказать и о других операциях.