Где применяется
1. Задача
Два прошлых шага решали коллизии в таблице постоянного размера. У такой таблицы есть скрытый предел. Чем больше ключей ты добавляешь, тем плотнее заполнены корзины и тем длиннее списки внутри них. Поиск «примерно за один шаг» постепенно превращается в «просмотри длинный список». Таблица, которая не растёт, замедляется с каждым новым ключом.
Решение: пусть таблица растёт сама. Когда корзины становятся слишком полными, таблица заводит больше корзин и переносит туда все записи. Поиск остаётся быстрым, и угадывать нужный размер заранее не придётся.
2. Простыми словами
Возьми числа из тестов. Таблица начинается с 4 корзин. После 3 ключей в ней 3 записи на 4 корзины, меньше одной на корзину, и поиск проверяет примерно одну запись. Если добавлять ключи дальше и не расширять таблицу, то при 40 ключах в каждой корзине окажется около 10 записей, и поиску придётся их перебирать.
Поэтому таблица следит, насколько она заполнена. Когда приходит 4-й ключ, записей становится 4 на 4 корзины, и таблица решает, что это слишком тесно. Она заводит 8 корзин и заново раскладывает по ним все 4 ключа. Теперь на корзину в среднем приходится половина записи, и поиск снова короткий. Таблица сделала это сама, твой код только вызывал set.
3. Идея
Сначала нужно измерить, насколько тесно в таблице. Заполненность (load factor) это одно число: количество записей, делённое на количество корзин. 3 записи в 4 корзинах дают заполненность 0,75. 8 записей в 4 корзинах дают 2,0: в каждой корзине в среднем 2 записи, и каждый поиск просматривает около 2 записей, а не одну.
Ты выбираешь порог: заполненность, после которой считаешь, что стало слишком тесно. Часто берут 0,75. При каждой вставке нового ключа проверяешь, превысила ли заполненность порог. Если да, делаешь resize (расширение): заводишь таблицу побольше, обычно с вдвое большим числом корзин.
На этом месте многие ошибаются. Старые корзины нельзя просто скопировать в новую таблицу. Номер корзины ключа равен hash(key) % bucketCount, а bucketCount только что изменился. Поэтому многие ключи теперь должны лежать в другой корзине. Например, сумма кодов 13 при 4 корзинах даёт корзину 1 (13 % 4 = 1), а при 8 корзинах корзину 5 (13 % 8 = 5). Нужно перехешировать (rehash): пройти по каждой записи и вставить её заново, посчитав номер корзины для нового числа корзин.
Проследи это на тех числах, которые проверяют тесты. Начни с 4 корзин. Вставь 3 ключа: заполненность 3 / 4 = 0,75. Это не больше порога, ничего не происходит. Вставь 4-й ключ: заполненность 4 / 4 = 1,0, это больше 0,75. Таблица удваивается до 8 корзин, и все 4 ключа перехешируются в неё. Сравнивать дроби неудобно и в разных языках можно получить разные округления. Поэтому проверяй заполненность целыми числами: count * 4 > bucketCount * 3 значит то же, что count / bucketCount > 0.75, но без дробей. Для 4 ключей в 4 корзинах это 16 > 12, условие выполнено.
4. Во что это обходится
Один resize стоит O(n): ты по разу перехешируешь каждую из n записей. Звучит дорого, и одна вставка действительно может выйти дорогой. Но resize бывает редко. После удвоения заполненность падает вдвое, например с 1,0 до 0,5. До следующего resize пройдёт много дешёвых вставок за O(1), примерно столько, сколько записей уже было в таблице. Если разделить стоимость одного resize, O(n), на эти вставки, на каждую выйдет постоянное количество лишней работы. Это называют амортизированным O(1) (средней стоимостью на длинной серии операций): отдельная вставка бывает медленной, но в среднем на длинной серии стоимость одной вставки постоянна.
Память O(n) на записи плюс сам массив корзин. Из-за удвоения корзин бывает больше, чем нужно. Сразу после resize их примерно вдвое больше, чем минимально нужно, чтобы заполненность не превышала 0,75. Это цена за то, что вставки в среднем остаются дешёвыми.
6. Где это встречается
Все динамические хеш-структуры, которыми ты пользуешься, делают это внутри: Map и Set в JavaScript, dict и set в Python, HashMap в Java, map в Go. Все они начинают с маленького размера и расширяются по мере заполнения. Поэтому в них можно положить миллионы ключей и ни разу не задать размер. Тот же приём работает в хранилище сессий или в кэше в памяти, которые растут вместе с нагрузкой. В таблице символов компилятора или интерпретатора, пока он встречает всё новые имена в коде. В любом роутере (части сервера, которая выбирает код по адресу запроса), который при запуске регистрирует заранее неизвестное число маршрутов. Когда нужен быстрый поиск по ключу, а сколько будет ключей, заранее не известно, первым выбором будет хеш-таблица, которая расширяется сама.
На LeetCode
Задачи на проектирование хеш-таблицы, которая должна оставаться быстрой по мере заполнения, и вопрос на собеседовании, почему её операции стоят амортизированное O(1).
Начни с маленькой таблицы и удваивай корзины, перехешируя все пары, когда count * 4 > buckets * 3.
То же правило роста для множества, чтобы цепочки оставались короткими при любом числе ключей.
В одно множество попадает до 10^5 значений, и каждая проверка стоит около одного шага как раз благодаря удвоению, которое ты написал.
Твоя задача (Tier 2)
Большая часть класса HashMap уже написана. Конструктор (4 корзины), свойства size и bucketCount, вспомогательный метод хеша и методы get, has, delete даны. Ты пишешь два метода, благодаря которым таблица растёт: set и _resize.
Заполненность равна size / bucketCount. Когда она превышает 0.75, корзинам тесно, поэтому таблица удваивает число корзин и заново раскладывает каждую пару.
setвставляет новый ключ или заменяет значение старого и увеличивает таблицу, когда она слишком заполнена._resizeудваивает число корзин и раскладывает каждую пару в бо́льшую таблицу.
Шаги:
set(key, value): найди корзину через_index(key). Если ключ уже там, замени его значение и закончи (размер не меняется, таблица не растёт). Иначе добавь[key, value]и прибавь 1 к счётчику. Затем проверь заполненность: еслиcount * 4 > bucketCount * 3(заполненность больше0.75), вызови_resize._resize: запомни старые корзины. Сделай новый набор пустых корзин, вдвое больше. Пройди по каждой паре в старых корзинах и добавь её заново через_index. Корзин стало больше, поэтому_indexдаёт новый номер корзины. Именно поэтому пары раскладывают заново, а не копируют.
Готово, когда проходят все тесты:
- в начале таблица маленькая:
bucketCount->4,size->0 - после 4-го разного ключа растёт:
bucketCount->8, иgetпо-прежнему находит каждый прежний ключ - после 7-го разного ключа растёт снова:
bucketCount->16, все 7 ключей находятся - замена значения у одного ключа (
set("x",1),set("x",2),set("x",3)) ->get("x")->3,size->1,bucketCount->4(без роста) - пустая таблица:
size->0,bucketCount->4,get("missing")->undefined
Практика
HashMap with load factor and auto-resize
// Most of this class is written. Complete set() and _resize(). The task is described above the editor.
export class HashMap {
constructor() {
// 4 buckets to start; each bucket is a list of [key, value] pairs.
this.buckets = [[], [], [], []];
this.count = 0;
}
get size() {
return this.count;
}
get bucketCount() {
return this.buckets.length;
}
// sum of the key's char codes, wrapped into a bucket index.
_index(key) {
let sum = 0;
for (let i = 0; i < key.length; i++) sum += key.charCodeAt(i);
return sum % this.buckets.length;
}
set(key, value) {
// TODO: your core here.
// 1. Find the bucket for this key with _index.
// 2. If the key is already in that bucket, overwrite its value and return.
// An overwrite must not change size and must not resize.
// 3. Otherwise add the [key, value] pair and count it.
// 4. Then check the load factor and resize once it passes 0.75. Compare
// with whole numbers so every language agrees on the same moment.
}
get(key) {
const b = this.buckets[this._index(key)];
for (const pair of b) if (pair[0] === key) return pair[1];
return undefined;
}
has(key) {
const b = this.buckets[this._index(key)];
for (const pair of b) if (pair[0] === key) return true;
return false;
}
delete(key) {
const b = this.buckets[this._index(key)];
for (let i = 0; i < b.length; i++) {
if (b[i][0] === key) { b.splice(i, 1); this.count--; return true; }
}
return false;
}
_resize() {
// TODO: your core here.
// 1. Hold on to the current buckets.
// 2. Give this.buckets a fresh set of empty lists, twice as many.
// 3. Re-insert every pair from the old buckets, asking _index again for
// each key. The table is bigger now, so _index answers differently.
// That is why you rehash instead of copying.
}
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.
Лестница подсказок
Застрял? Открывай по одной, но сначала попробуй сам.