Имеет ли хэш-таблицу допустимые значения?

Question

Скажем, у меня есть хэш-таблицу обр [1..n], набор ключей k1, k2, k3 (м нет. Ключей) и т.д .. и хэш-функция Н (к)

ч (к) принимает вход k и дает выход i как индекс для arr [i].

Теперь в концепции линейного зондирования хеширования давайте рассмотрим сценарии.

1> let k1=101 and h(k)=i=5, then k1(101) is stored in arr[5] 

2> let k2=102 and h(k)=i=6 then k1(102) is stored in arr[6] 

3>Now again k3=101 and h(k)=i=5 then by linear probing it will go one 
step ahead(i=i+1) and check a[i](a[6]) is free or not, since a[6] is not free 
so we repeat again (i=i+1) and check a[i](a[7]) is free or not, since a[7] is free 
so k3(101) is again inserted at arr[7]. 

Теперь arr [5] и arr [7] являются возможными дубликатами, они принадлежат к одному и тому же ключу.

Имеет ли хэш-таблицу дубликаты? Я правильно понимаю.

Пожалуйста, проверьте меня, если я ошибаюсь

Answer 1

Я считаю, что это более сложное обсуждение

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

Answer 2

В C++ существуют два контейнера хэша, которые допускают дубликаты. Это std::unordered_multiset и std::unordered_multimap.

Answer 3

Существует множество различных реализаций хеш-таблиц.

Например, класс шаблонов CAtlMap от Microsoft использует подход, называемый «Separate chaining with linked lists» - то есть, ковши полностью независимы, и каждое ведро может содержать более одной записи.

STL также использует список. Они просто помещают все элементы в один список, упорядоченный по индексу, и в массиве они содержат 2 итератора, указывающих на первый и последний элемент ведра.

Answer 4

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

Чтобы исключить дубликаты, на шаге 3 в вашем примере вы сравниваете ключ с ключом в слоте 5, находите, что они совпадают, а затем либо перезаписываете запись, либо отклоняете входящую запись (ваше дизайнерское решение).