Hashtable и массив ведра

Question

Я читал, что в хеш-таблицу у нас есть массив ведра, но я не понимаю, что содержит этот массив.

Имеет ли он индекс хеширования? запись (пара ключ/значение)? и то и другое?

Этот образ, для меня, не очень понятно:

^(reference)

Так что массив ведро?

Answer 1

На практике связанный список записей, которые были вычислены (путем хэширования ключа), войти в это ведро.

Answer 2

В HashTable в большинстве случаев возникают столкновения. То есть, когда разные элементы имеют одно и то же значение хэш-функции. Элементы с одинаковым значением Хэш хранятся в одном ведре. Таким образом, для каждого хэш-значения у вас есть ведро, содержащее все элементы, которые имеют это значение хэша.

Answer 3

Что входит в массив ведра, зависит от того, что хранится в хеш-таблице, а также от стратегии разрешения конфликтов.

При использовании linear probing или другой open addressing technique, ведро таблицы хранит ключи или пары ключ-значение, в зависимости от использования вашей хэш-таблицы ^*.

Когда вы используете separate chaining technique, тогда ваш массив ведер хранит пары ключей и заголовки вашей цепочки (например, связанные списки).

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

^* Если ваша хэш-таблица используется для проверки членства (т. Е. Представляет собой набор ключей), то массив ведра хранит ключи; в противном случае он хранит пары ключ-значение.

Answer 4

Индекс массива в основном эквивалентен значению хэша (ну, значение хэша модифицирует размер массива), поэтому нет необходимости хранить его в массиве вообще.

Относительно того, что содержит фактический массив, есть несколько вариантов:

• Если мы используем separate chaining:

  • Ссылка на связанный список всех элементов, которые имеют это хэш-значение. Таким образом:

    LinkedList<E>[] 
    

  • Узел связанного списка (т.глава связанного списка) - аналогично первому варианту, но вместо этого мы просто начинаем со связанного списка сразу, не теряя пространства, имея отдельную ссылку на него. Итак:

    LinkedListNode<E>[] 
    

• Если мы используем open addressing, мы просто хранить фактический элемент. Если есть еще один элемент с тем же значением хэша, мы используем некоторую воспроизводимую технику, чтобы найти место для него (например, мы просто попробуем следующую позицию). Итак:

  E[] 
  

• Там может быть несколько других вариантов, но выше, являются наиболее известными, с раздельным сцепления является наиболее популярным (к моему знанию)

* I» m, предполагая некоторое знакомство с дженериками и синтаксисом Java/C#/C++ - E здесь просто тип элемента, который мы храним, LinkedList<E> означает LinkedList элементы хранения типа E. X[] - это массив, содержащий элементы типа X.

Answer 5

Ведро - это связанный список пар ключ-значение. хэш-индекс - это один , чтобы указать «какой ковш», а «ключ» в паре «ключ-значение» - это тот, который указывает «какая запись в этом ковше». также выезд hashing in Java -- structure & access time, я уже рассказывал подробности.