Реализация картыв С

Question

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

Answer 1

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

Answer 2

Структура данных карты и «столкновение» не могут быть разделены.то, как вы начали свою реализацию, выглядит хорошо, вот как вы должны обрабатывать коллизии:

Добавление новой записи в карту

1. вычисление hashcode для key
2. вычислить index из хеш-кода (более или менее index = hashcode value% size of keyset)
3. , если keyset[index] не равно нулю
   1. , еслинабор ключей [index]! = ключ (т. е. для строк, используйте strcmp) увеличение index модуль size of keyset, затем перейти к 3
4. положить value в entryset[index]

Получение значения с карты

1. вычисление hashcode для key
2. вычисление index из хеш-кода (подробнееили меньше index = hashcode value% size of keyset)
3. , если keyset[index] не равно нулю
   1. , если keyset [index]! = key (т. е. для строк, используйте strcmp)приращение index модуль size of keyset, затем перейти к 3
4. , если keyset[index] равно нулю, вернуть нуль
5. вернуть entryset[index]

Удаление записи с карты

1. Рассчитать hashcode для key
2. вычисление index из хеш-кода (более или менее index = hashcode value% size of keyset)
3. , если keyset[index] не равно нулю
   1. , если набор ключей [индекс]! = ключ (т.е.для строк используйте strcmp) приращение index модуль size of keyset, затем перейдите к 3
4. установите keyset[index] и entryset[index] в ноль

какВы можете видеть, вы можете поместить шаги с 1 по 3 в функцию int findIndexFromKey(Map *map, char *key);, и большая часть работы сделана

** EDIT **

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

Answer 3

Это то, что известно как коллизии, но самое простое - сделать каждую корзину в вашей Hashmap списком элементов с одинаковым хешем. Затем на get все, что вам нужно сделать, - это перебирать список, пока не найдете нужный элемент.