Функция хеширования в C - Типы методов разрешения столкновений

Введение в функцию хеширования в C

В этой статье есть краткое примечание о хешировании (хеш-таблица и хеш-функция). Наиболее важным понятием является «поиск», который определяет сложность времени. Чтобы уменьшить временную сложность, по сравнению с любой другой концепцией хеширования структуры данных, у которой в среднем случае есть время O (1), а в наихудшем случае потребуется время O (n).

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

Что такое хэш-функция?

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

Типы хэш-функции

Типы хеш-функций описаны ниже:

1. Метод деления

В этом методе хеш-функция зависит от остатка от деления.

Пример: элементы для размещения в хеш-таблице равны 42, 78, 89, 64, и давайте примем размер таблицы равным 10.

Хеш (ключ) = элементы% размера таблицы;

2 = 42% 10;

8 = 78% 10;

9 = 89% 10;

4 = 64% 10;

Табличное представление можно увидеть как ниже:

2. Метод середины квадрата

В этом методе средняя часть квадрата элемента берется в качестве индекса.

Элемент, который должен быть размещен в хеш-таблице: 210, 350, 99, 890, а размер таблицы - 100.

210 * 210 = 44100, индекс = 1, поскольку средняя часть результата (44100) равна 1.

350 * 350 = 122500, индекс = 25, поскольку средняя часть результата (122500) равна 25.

99 * 99 = 9801, индекс = 80, поскольку средняя часть результата (9801) равна 80.

890 * 890 = 792100, индекс = 21, поскольку средняя часть результата (792100) равна 21.

3. Метод складывания цифр

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

Элемент для размещения 23576623, 34687734.

• хеш (ключ) = 235 + 766 + 23 = 1024
• хэш-ключ) = 34 + 68 + 77 + 34 = 213

В этих типах хэширования предположим, что у нас есть числа от 1 до 100 и размер хеш-таблицы = 10. Элементы = 23, 12, 32

Хеш (ключ) = 23% 10 = 3;

Хеш (ключ) = 12% 10 = 2;

Хеш (ключ) = 32% 10 = 2;

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

Типы методов разрешения столкновений

Давайте обсудим типы методов разрешения столкновений:

1. Цепочка

В этом методе, как следует из названия, он обеспечивает цепочку блоков для записи в таблице, имеющей две записи элементов. Таким образом, всякий раз, когда такие столкновения происходят, ящики действуют как связанный список.

Пример: 23, 12, 32 с размером таблицы 10.

Хеш (ключ) = 23% 10 = 3;

Хеш (ключ) = 12% 10 = 2;

Хеш (ключ) = 32% 10 = 2;

2. Открытая адресация

• Линейное зондирование

Это еще один метод решения проблем столкновения. Как следует из названия, всякий раз, когда происходит столкновение, два элемента должны быть помещены в одну и ту же запись в таблице, но с помощью этого метода мы можем искать следующий пустой пробел или запись в таблице и размещать второй элемент. Это может снова привести к другой проблеме; если мы не найдем пустую запись в таблице, это приведет к кластеризации. Таким образом, это известно как проблема кластеризации, которая может быть решена следующим способом.

Пример: 23, 12, 32 с размером таблицы 10

Хеш (ключ) = 23% 10 = 3;

Хеш (ключ) = 12% 10 = 2;

Хеш (ключ) = 32% 10 = 2;

На этой диаграмме 12 и 32 могут быть размещены в одной записи с индексом 2, но этим способом они размещаются линейно.

• Квадратичное зондирование

Этот метод является решением проблемы кластеризации при линейном зондировании. В этом методе хеш-функция с хеш-ключом рассчитывается как хеш (ключ) = (хеш (ключ) + x * x)% размера таблицы (где x = 0, 1, 2…).

Пример: 23, 12, 32 с размером таблицы 10

Хеш (ключ) = 23% 10 = 3;

Хеш (ключ) = 12% 10 = 2;

Хеш (ключ) = 32% 10 = 2;

В этом мы можем видеть, что 23 и 12 могут быть легко размещены, но 32 не могут так же, как 12 и 32 разделяет ту же самую запись с тем же индексом в таблице, как в этом методе hash (key) = (32 + 1 * 1) % 10 = 3. Но в этом случае запись таблицы с индексом 3 помещается с 23, поэтому мы должны увеличить значение x на 1. Хэш (ключ) = (32 + 2 * 2)% 10 = 6. Итак, теперь мы можем поместить 32 в записи с индексом 6 в таблице.

• Двойное хеширование

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

• 1 (ключ) = ключ% размер таблицы.
• 2 (ключ) = p - (ключ mod p), где p - простые числа <размер таблицы.

Пример: 23, 12, 32 с размером таблицы 10

Хеш (ключ) = 23% 10 = 3;

Хеш (ключ) = 12% 10 = 2;

Хеш (ключ) = 32% 10 = 2;

При этом снова элемент 32 может быть размещен с использованием hash2 (key) = 5 - (32% 5) = 3. Таким образом, 32 может быть размещен с индексом 5 в таблице, которая пуста, так как для ее размещения нам нужно перейти на 3 записи.

Заключение-Хеширование в С

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

Рекомендуемые статьи

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

1. Хеширование в СУБД
2. Процесс шифрования
3. Как установить CakePHP?
4. Как работает блокчейн
5. Функция хеширования в Java
6. Функция хеширования в PHP | Как работать?