Как хранятся в памяти значения HashTable и HashMap?

Я понимаю, что к hashированию применяется метод хеширования для сохранения его значения в адресе памяти.

Но я не понимаю, как здесь происходит столкновение ? Какой алгоритм хеширования использует Java для создания пространства памяти ? Это MD5?

Основная идея HashMap заключается в следующем:

  1. HashMap – это действительно массив специальных объектов, которые содержат как ключ, так и значение.
  2. Массив имеет некоторое количество ведер (слотов), например 16.
  3. Алгоритм хеширования обеспечивается методом hashCode() который имеет каждый объект. Поэтому, когда вы пишете новый Class , вы должны позаботиться о правильной hashCode() методов hashCode() и equals() . По умолчанию один (classа Object ) принимает указатель памяти как число. Но это не хорошо для большинства classов, которые мы хотели бы использовать. Например, class String использует алгоритм, который делает hash из всех символов в строке – подумайте об этом так: hashCode = 1.char + 2.char + 3.char... (упрощенный). Поэтому две равные строки, даже если они находятся в другом месте в памяти, имеют одинаковый hashCode() .
  4. Результатом hashCode() , скажем, «132», является то количество ведро, где объект должен быть сохранен, если бы у нас был массив, большой. Но мы этого не делаем, у нас всего лишь 16 ведер. Таким образом, мы используем очевидный расчет 'hashcode % array.length = bucket' или '132 mod 16 = 4' и сохраняем пару Key-Value в ведро №4.
    • Если еще нет пары, все в порядке.
    • Если есть ключ с ключом, который у нас есть, мы удаляем старый.
    • Если есть другая пара Key-Value (collision), мы связываем новую, после старой, в связанный список.
  5. Если массив резервных копий становится слишком полным, поэтому нам нужно будет создать слишком много связанных списков, мы создадим новый массив с удвоенной длиной, перефразируем все элементы и добавим их в новый массив, а затем утилизируем старый. Это, скорее всего, самая дорогая операция на HashMap , поэтому вы хотите сообщить своим Maps сколько ведер вы будете использовать, если вы это знаете раньше.
  6. Если кто-то пытается получить значение, он предоставляет ключ, мы хешируем его, модифицируем, а затем переходим через потенциальный связанный список для точного соответствия.

Изображение, любезно предоставленное Википедии: Графика

В этом случае,

  • существует массив с 256 ведрами (нумеруется, конечно, 0-255)
  • есть пять человек. Их hash-коды после того, как они были перенесены через mod 256 , указывают на четыре разных слота в массиве.
  • вы можете видеть, что у Сандры Ди нет свободного места, поэтому она была прикована к Джону Смиту.

Теперь, если вы попытаетесь найти номер телефона Сандры Ди, вы бы назвали ее имя, измените его на 256 и заглянете в ведро 152. Там вы найдете Джона Смита. Это не Сандра, посмотри дальше … ага, Сандра прикован к Джону.

Здесь Hash не означает для Hashing , таких как MD5 . Его ячейка памяти HashCode, используемая для хранения Object для определенного ключа.

Показания:

  • Как работает Java hashmap?
  • Как работает HashMap в Java

Это несколько более ясное объяснение того, как работает HashMap?

По умолчанию функция hashCode() умолчанию в classе Object возвращает адрес памяти как хеш, который используется как ключ в HashTable & HashMap .

Пройдя через ответ @ Slanec, см. Javadoc с Java-8, так как есть значительные изменения. Например: «TREEIFY», где LinkedList преобразуется в TreeMap в случае достижения порогового количества записей на каждый ковш (в настоящее время 8).