Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 6.5 Упражнения

## 6.5.1 Вопросы для самопроверки

### 1. Как искать после хеш-коллизии

Хеш-таблица содержит 5 бакетов и использует хеш-функцию \(h(x)=x \bmod 5\). При коллизии элементы последовательно добавляются в список соответствующего бакета. В таблицу по порядку вставляют `[1, 6, 11, 7]`.

1. Запишите содержимое бакетов с номерами 0–4.
2. В какой бакет сначала попадает поиск числа 6 и какие элементы проверяются по порядку?
3. Исходя из содержимого бакетов в вопросе 1, перезаписали ли позднее вставленные элементы более ранние? Объясните ответ с учетом этого способа разрешения коллизий.

Ответ

1. Так как \(1\bmod5=6\bmod5=11\bmod5=1\), а \(7\bmod5=2\), бакеты имеют вид:

       0: []
       1: [1, 6, 11]
       2: [7]
       3: []
       4: []

2. При поиске числа 6 сначала выбирается бакет 1, затем сравниваются элементы 1 и 6. Искомый элемент находится при втором сравнении.

3. Одинаковые хеш-значения означают лишь попадание элементов в один бакет, но не равенство самих элементов. При цепной адресации все столкнувшиеся элементы сохраняются в бакете, а при поиске сравниваются по очереди. Поэтому 1, 6 и 11 не перезаписывают друг друга.

### 2. Куда перемещаются элементы при расширении хеш-таблицы

Хеш-таблица с цепной адресацией первоначально содержит 5 бакетов и использует хеш-функцию \(h(x)=x\bmod5\). Ключи `[1, 6, 11]` находятся в бакете 1.

Теперь таблицу расширяют до 7 бакетов, и хеш-функция принимает вид \(h(x)=x\bmod7\).

1. Вычислите новые номера бакетов для 1, 6 и 11.
2. Какие бакеты будут непустыми после расширения?
3. Можно ли при расширении скопировать список из прежнего бакета 1 без изменений в новый бакет 1? Обоснуйте ответ результатами вопросов 1 и 2.

Ответ

1. Новые номера бакетов:

   - \(1\bmod7=1\);
   - \(6\bmod7=6\);
   - \(11\bmod7=4\).

2. В бакете 1 хранится 1, в бакете 4 — 11, а в бакете 6 — 6. Три ключа больше не находятся в одном бакете.

3. Копировать список без изменений нельзя. Номер бакета вычисляется как остаток от деления ключа на число бакетов. После замены 5 на 7 номер бакета для того же ключа может измениться, поэтому положение каждого ключа необходимо вычислить заново. Если просто скопировать прежний бакет 1, то последующий поиск по новой формуле направится за 6 в бакет 6, а за 11 — в бакет 4 и не найдет эти ключи.

### 3. Можно ли найти 11 после удаления 6

Хеш-таблица содержит 5 позиций с индексами `0–4` и использует хеш-функцию \(h(x)=x\bmod5\). При коллизии поиск первого свободного места начинается с вычисленного хеш-функцией индекса и продолжается вправо.

В таблицу по порядку вставляют `[1, 6, 11]`.

1. По какому индексу в итоге находится каждое из трех чисел?
2. Какие индексы проверяются по порядку при поиске 11?
3. Допустим, при удалении 6 его позицию просто освобождают, как если бы она никогда не использовалась, а поиск прекращается при встрече с пустой позицией. Что произойдет при следующем поиске 11? Будет ли результат правильным? Если нет, как избежать ошибки?

Ответ

1. Число 1 находится по индексу 1. Число 6 также отображается в индекс 1, но после коллизии помещается по индексу 2. Число 11 тоже начинает поиск с индекса 1, пропускает занятые индексы 1 и 2 и в итоге помещается по индексу 3.

2. При поиске 11 последовательно проверяются индексы `1, 2, 3`, и число находится по индексу 3.

3. Если пометить индекс 2 как «никогда не использовавшийся», то поиск 11 остановится на индексе 2 после проверки индекса 1 и ошибочно решит, что числа 11 нет. При удалении следует оставлять отметку «удалено»: встретив ее, поиск продолжает проверять следующий индекс (после индекса 4 возвращаясь к индексу 0), а при последующей вставке эту позицию можно использовать снова.

## 6.5.2 Задачи по программированию

### 1. Сравнение состава символов в двух строках

Даны две строки `s` и `t`, состоящие только из строчных английских букв. Символы в `s` можно переставлять произвольным образом, но нельзя добавлять, удалять или заменять.

Определите, можно ли после перестановки получить `t`. Если можно, верните `true`, иначе — `false`. Используйте хеш-таблицу для подсчета числа вхождений каждой буквы и не сортируйте символы в строках.

Подсказки

1. Если строки имеют разную длину, их состав символов не может совпадать
2. Сохраняйте в хеш-таблице количество каждой буквы; при обходе s увеличивайте соответствующий счетчик на 1
3. При обходе t уменьшайте соответствующий счетчик на 1; состав символов совпадает, только если все счетчики в конце равны 0

LeetCode

##### Оставляйте свои идеи, вопросы и предложения в комментариях