Хеширование и хеш-таблицы

Данное задание относится к предмету информатика, конкретнее, к разделу структуры данных и алгоритмы, а именно к теме хеширование и хеш-таблицы.

Что такое хеширование?

Хеширование — это метод преобразования данных (в данном случае — последовательности символов ФИО) в фиксированную длину путем применения некоторой математической функции. Результат называется хешем и используется для быстрого поиска данных. В этом конкретном задании вам предложено выполнить несколько вариантов хеширования строки, а также обсчитать и найти элементы внутри таблицы с помощью различных методов.

Разбор задания:

1. Построение индексного массива для 12 символов ФИО.

Здесь требуется:

• Взять первые 12 символов ФИО.
• Построить индексный массив, который будет упорядочивать символы по алфавиту.

Для указанных ФИО: «Соколов Алексей Михайлович»* ФИО включает 26 символов, но для этой задачи берем только первые 12 символов: Соколов Алек

Алгоритм:

1. Представляете каждый символ в числовом виде согласно таблице кодировок символов (например, ASCII).
2. Сортируете символы по порядку этих значений.

Например, для "Соколов Алек" сначала переводите символы в числовое значение:

• С -> 67, о -> 111, к -> 107, о -> 111, л -> 108, о -> 111, в -> 118
• А -> 65, л -> 108, е -> 101, к -> 107

Отсортированные значения: \( 65\ (А), 67\ (С), 101\ (е), 107\ (к, к), 108\ (л, л), 111\ (о, о, о), 118\ (в) \). Итоговая последовательность символов: А, С, e, к, к, л, л, о, о, о, в.

2. Прямое связное хеширование с размером хеш-таблицы 5.

- Необходимо выполнить хеширование методом прямого связного хеширования с хеш-таблицей размера 5. Здесь подразумевается использование метода разрешения коллизий путем прямого связывания (примерно как списки).

Создаем хеш-функцию для данной строки. Допустим, простая хеш-функция:

hash(i) = ord(i) % 5

Применяем её для нашей строки:

• С: ord(С) = 67, 67 % 5 = 2
• о: ord(о) = 111, 111 % 5 = 1
• к: ord(к) = 107, 107 % 5 = 2
• л: ord(л) = 108, 108 % 5 = 3
• в: ord(в) = 118, 118 % 5 = 3
• А: ord(А) = 65, 65 % 5 = 0
• е: ord(е) = 101, 101 % 5 = 1

0 -> [А]
1 -> [о, е]
2 -> [С, к]
3 -> [л, в]

3. Хеширование методом открытой адресации с размером хеш-таблицы 11.

- Необходимо выполнить хеширование методом открытой адресации с помощью линейной и квадратной проб. Используем ту же строку "Соколов Алек", и хеш-таблицу размера 11. Простая хеш-функция:

hash(i) = ord(i) % 11

Применяем её для каждого символа:

• С: ord(С) = 67, 67 % 11 = 1
• о: ord(о) = 111, 111 % 11 = 1
• к: ord(к) = 107, 107 % 11 = 8
• л: ord(л) = 108, 108 % 11 = 9
• в: ord(в) = 118, 118 % 11 = 8
• А: ord(А) = 65, 65 % 11 = 10
• е: ord(е) = 101, 101 % 11 = 2

При линейной пробе, если ячейка занята, идем к следующей:

1 -> С
2 -> е
8 -> к (затем происходит коллизия с "в")
9 -> л
10 -> А

Для коллизии на позиции 8: просто идем на следующую свободную позицию: в и л ставим в ячейки 9 и 10.

В квадратной пробе, вместо простого перехода к следующей ячейке, используется формула:

i = (h(x) + j^2) % table_size