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

Условие:

Решить

Решение:

Данное задание относится к предмету **информатика**, конкретнее, к разделу **структуры данных и алгоритмы**, а именно к теме **хеширование и хеш-таблицы**. ### Что такое хеширование? Хеширование — это метод преобразования данных (в данном случае — последовательности символов ФИО) в фиксированную длину путем применения некоторой математической функции. Результат называется **хешем** и используется для быстрого поиска данных. В этом конкретном задании вам предложено выполнить несколько вариантов хеширования строки, а также обсчитать и найти элементы внутри таблицы с помощью различных методов. ### Разбор задания: #### 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 ```