Хеш-таблица. Как это устроено?

Question

Теперь я пытаюсь понять, как построить Hashtable.

Самое интересное - как объекты добавляются в Hashtable?

, который я прочитал вЗапишите, что:

на первом шаге: Расчет hashCode() объекта.

Далее мы определим положение этого объекта в Hashtable: obj.hashCode() % Hashtable.length.

Например, добавьте больше элементов к Hashtable:

Hashtable<String, String> hm=new Hashtable<String, String>(100);

        hm.put("Lee","Lee");
        hm.put("lee","lee");
        hm.put("eel","eel");

Определите корзину, в которую помещается объект:

    System.out.println("Lee".hashCode() % 100);
    System.out.println("lee".hashCode() % 100);
    System.out.println("eel".hashCode() % 100);

Если я понимаю алгоритм, объекты должны бытьпоместите в таблицу следующее:

eel /*because,"eel".hashCode() % 100=0*/, 
lee /*because, "lee".hashCode() % 100=20*/, 
Lee /*because, "Lee".hashCode() % 100=68*/

а что мы видим в результате?

System.out.println(hm);

{Lee=Lee, lee=lee, eel=eel} 

Пожалуйста, скажите, где я ошибся?

Answer 1

Порядок итерации Hashtable (а также HashMap) элементов не гарантирован (зависит от реализации), поэтому ИМХО нет особого смысла пытаться построить на нем теорию.Это может даже измениться между различными версиями Java (это действительно изменилось с Java5 на Java6).

Btw Hashtable устарел, рекомендуется использовать (и анализировать) HashMap вместо.

Ваше описание звучит нормально для меня как базовая реализация хэш-карты.Тем не менее, фактическая реализация HashMap несколько сложнее, по крайней мере со времен Java4.Например, размер хеш-таблицы всегда является степенью двойки (что было бы довольно плохим решением для базовой хеш-таблицы, как вы описали), а значения хеш-функции, полученные из ключевых объектов, внутренне перефразируются для достижения более равномерного распределения по фактическомуразмер стола.Подробнее об этом см. В следующих выпусках бюллетеня Java Specialist Newsletter:

• Для HashMap требуется улучшенный hashCode ()
• Последующие действияв JDK 1.4 HashMap hashCode () mystery

Answer 2

Hashtable - это отображение ключей на значения. Именно это отображение отображается при печати Hashtable.

Рассказ о .hashCode и .equals - это грубое описание того, как ему удается отслеживать пары ключ / значение внутри.

Несколько замечаний по вашему вопросу:

• capacity, который вы задали равным 100 в вашем примере, не представляет количество сегментов для хранения объектов. Он представляет количество объектов, для которых Hashtable имеет емкость, с коэффициент загрузки 0,75.

• Количество сегментов может изменяться во время выполнения . Если вы продолжаете добавлять объекты в течение длительного времени, коэффициент загрузки будет увеличен, и сегменты могут быть перераспределены, а объекты "перефразированы".

Из документов :

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

Answer 3

Концепция хеш-таблицы заключается в добавлении объектов в таблицу в соответствии с некоторой хеш-функцией (принимает объект и возвращает индекс).

Ваше описание хеш-таблицы является одним из многих (много), и я был бы удивлен, если бы он был реализован в Java так же, как вы читаете.

Answer 4

Как упоминалось ранее, Hashtable зависит от реализации, и я бы рекомендовал прочитать о Hashtable в целом, чтобы получить представление о том, как они работают, а затем, после понимания того, как он работает, прочитать о конкретной реализации на Java или другом языке.

Википедия имеет довольно хорошую статью на эту тему, поэтому я предлагаю прочитать это в первую очередь.