Когда в hashtable нужно хранить и ключ и значение?

Question

[returnZero]

Всем добрый день, изучаю структуры данных на примере C#, есть пара непонятных моментов.
1. у нас есть хэш-таблица которую представляет некий массив и хэш-функция. Хэш-функции мы передаем ключ которая превращает его путем определённых манипуляций в индекс этого массива. Но если у нас вдруг совпадут хэши то возникнет коллизия, и тогда у нас есть 2 метода её обхода, 1 - открытая адресация 2 - связанный список. Тут я не понимаю одного, нужно ли хранить ключ так же в массиве, ведь если мы запросим какой-то айтем в массиве у которого есть коллизия то как мы поймем какой из них нам нужен, и если это нужно делать то каким методом стоит пользоваться в случае открытой адресации и списков?
2. Где можно посмотреть примеры реализации хэш-таблицы на шарпе?

Answer 1

[mayton2019]

Но если у нас вдруг совпадут хэши то возникнет коллизия, и тогда у нас есть 2 метода её обхода, 1 - открытая адресация 2 - связанный список.

Да. В связном списке всегда хранятся и ключи и значения. В противном случае вы не докажете что нашли верно.

UPD: Обновление. Поскольку я был неверно понят комментаторами - я обновляю цитату. Мой комментарий относится ко второму алгоритму. А точнее к структуре данных. В данном случае к связному списку который реализован в 99% хеш-таблиц в Java/DotNet.

Comments

[returnZero]

А в случае с открытой адресацией? Нужно просто использовать двумерный массив где в одной ячейке будет ключ а во второй значение?

[Владимир Коротенко]

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

[mayton2019]

returnZero, я их не использовал никогда. И не видел практически в продуктовом коде чтоб нечто работало. Есть в Java реализация таких таблиц в виде библиотеки Trove. Но кажется она не сильно популярна.

[Владимир Коротенко]

mayton2019, Не большой специалист в яве но в шарпах это базовый функционал.
Например хэшмэп

// Create Dictionary.
        Dictionary<string, int> hash = new Dictionary<string, int>();
        
       
        hash.Add("diamond", 500);
        hash.Add("ruby", 200);
        hash.Add("pearl", 100);

[Максим Федоров]

mayton2019,

Но кажется она не сильно популярна.

может у вас и задача столько же не популярная? :)

[mayton2019]

Владимир Коротенко, а где вы указываете что хеш должен использовать открытую адресацию?

[Владимир Коротенко]

mayton2019, Я даже не в курсе. Исходники доступны, но копаться в них смысла не вижу. Есть абстракция, она предоставляет нужное поведение, как оно там внутри, ну это как по мне лишнее

[mayton2019]

Владимир Коротенко, я обновил свой ответ. Почитайте его.