6.5 Упражнения¶
6.5.1 Вопросы для самопроверки¶
1. Как искать после хеш-коллизии¶
Хеш-таблица содержит 5 бакетов и использует хеш-функцию \(h(x)=x \bmod 5\). При коллизии элементы последовательно добавляются в список соответствующего бакета.
В таблицу по порядку вставляют [1, 6, 11, 7].
- Запишите содержимое бакетов с номерами 0–4.
- В какой бакет сначала попадает поиск числа 6 и какие элементы проверяются по порядку?
- Исходя из содержимого бакетов в вопросе 1, перезаписали ли позднее вставленные элементы более ранние? Объясните ответ с учетом этого способа разрешения коллизий.
Ответ
-
Так как \(1\bmod5=6\bmod5=11\bmod5=1\), а \(7\bmod5=2\), бакеты имеют вид:
-
При поиске числа 6 сначала выбирается бакет 1, затем сравниваются элементы 1 и 6. Искомый элемент находится при втором сравнении.
-
Одинаковые хеш-значения означают лишь попадание элементов в один бакет, но не равенство самих элементов. При цепной адресации все столкнувшиеся элементы сохраняются в бакете, а при поиске сравниваются по очереди. Поэтому 1, 6 и 11 не перезаписывают друг друга.
2. Куда перемещаются элементы при расширении хеш-таблицы¶
Хеш-таблица с цепной адресацией первоначально содержит 5 бакетов и использует хеш-функцию \(h(x)=x\bmod5\).
Ключи [1, 6, 11] находятся в бакете 1.
Теперь таблицу расширяют до 7 бакетов, и хеш-функция принимает вид \(h(x)=x\bmod7\).
- Вычислите новые номера бакетов для 1, 6 и 11.
- Какие бакеты будут непустыми после расширения?
- Можно ли при расширении скопировать список из прежнего бакета 1 без изменений в новый бакет 1? Обоснуйте ответ результатами вопросов 1 и 2.
Ответ
-
Новые номера бакетов:
- \(1\bmod7=1\);
- \(6\bmod7=6\);
- \(11\bmod7=4\).
-
В бакете 1 хранится 1, в бакете 4 — 11, а в бакете 6 — 6. Три ключа больше не находятся в одном бакете.
-
Копировать список без изменений нельзя. Номер бакета вычисляется как остаток от деления ключа на число бакетов. После замены 5 на 7 номер бакета для того же ключа может измениться, поэтому положение каждого ключа необходимо вычислить заново. Если просто скопировать прежний бакет 1, то последующий поиск по новой формуле направится за 6 в бакет 6, а за 11 — в бакет 4 и не найдет эти ключи.
3. Можно ли найти 11 после удаления 6¶
Хеш-таблица содержит 5 позиций с индексами 0–4 и использует хеш-функцию \(h(x)=x\bmod5\).
При коллизии поиск первого свободного места начинается с вычисленного хеш-функцией индекса и продолжается вправо.
В таблицу по порядку вставляют [1, 6, 11].
- По какому индексу в итоге находится каждое из трех чисел?
- Какие индексы проверяются по порядку при поиске 11?
- Допустим, при удалении 6 его позицию просто освобождают, как если бы она никогда не использовалась, а поиск прекращается при встрече с пустой позицией. Что произойдет при следующем поиске 11? Будет ли результат правильным? Если нет, как избежать ошибки?
Ответ
-
Число 1 находится по индексу 1. Число 6 также отображается в индекс 1, но после коллизии помещается по индексу 2. Число 11 тоже начинает поиск с индекса 1, пропускает занятые индексы 1 и 2 и в итоге помещается по индексу 3.
-
При поиске 11 последовательно проверяются индексы
1, 2, 3, и число находится по индексу 3. -
Если пометить индекс 2 как «никогда не использовавшийся», то поиск 11 остановится на индексе 2 после проверки индекса 1 и ошибочно решит, что числа 11 нет. При удалении следует оставлять отметку «удалено»: встретив ее, поиск продолжает проверять следующий индекс (после индекса 4 возвращаясь к индексу 0), а при последующей вставке эту позицию можно использовать снова.
6.5.2 Задачи по программированию¶
1. Сравнение состава символов в двух строках¶
Даны две строки s и t, состоящие только из строчных английских букв.
Символы в s можно переставлять произвольным образом, но нельзя добавлять, удалять или заменять.
Определите, можно ли после перестановки получить t. Если можно, верните true, иначе — false.
Используйте хеш-таблицу для подсчета числа вхождений каждой буквы и не сортируйте символы в строках.
Подсказки
- Если строки имеют разную длину, их состав символов не может совпадать
- Сохраняйте в хеш-таблице количество каждой буквы; при обходе s увеличивайте соответствующий счетчик на 1
- При обходе t уменьшайте соответствующий счетчик на 1; состав символов совпадает, только если все счетчики в конце равны 0