Как я могу улучшить реализацию моей собственной хэш-карты

Question

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

Вот как будет выглядеть структура:

| 0   | ---> | 11 | ---> | 33 | ---> | -- | ---> | 121 | ---> | TAIL |
| 1   | ---> | 12 | ---> | 34 | ---> | -- | ---> | 122 | ---> | TAIL |
| -   |
| -   |
| -   |
| D-1 | ---> | -- | ---> | -- | ---> | -- | ---> | -- | ---> | TAIL |

Это массив связанных списковгде

D = размер массива,

|11 |= элемент с ключом;11 Элементы AND вставляются в отсортированном виде

Алгоритм:

void Insert(key, value):
 int bucket = hash_fn(key); // key % D, for now
 // accessing this bucket or array-index in array is O(1)
 // insert in linked list at the right position
 LL[bucket]->insert(new object(key, value))

bool Lookup(key):
 int bucket = hash_fn(key); // key % D, for now
 // search for key in LL[bucket]

Концерн : если множество элементов сопоставлено с одним и тем же сегментом, поиск не будет O(1), фактически, он может стремиться к O (n).

Как я могу улучшить это?

Answer 1

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

Если вы хотите отклониться от идеи хеш-таблицы со связанными списками для сегментов, вы можете попробовать поместить в эти сегменты некоторую другую структуру данных - например, какое-то самобалансирующееся дерево, например красное черный или AVL, чтобы получить поведение O (log (m)), где m - максимальное количество записей в сегменте. Но это на самом деле не сделает вас счастливым. Простое использование хорошей хеш-функции даст.

Answer 2

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

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

В этой статье Википедии также содержится очень хорошая информация об этой технике.

Answer 3

Из Википедия :

При хорошей хэш-функции средняя стоимость поиска почти постоянна, так как коэффициент загрузки увеличивается от 0 до 0,7 (примерно на 2/3 заполнено) или около того. стоимость обработки их увеличивается.

Так что с достаточно хорошей хеш-функцией и достаточно большой хеш-таблицей вам не стоит об этом беспокоиться.