Массивы, списки и хеш-таблицы

Что это такое

Это три структуры, к которым рабочая программа тянется в первую очередь. Массив хранит элементы рядом, в одном блоке памяти, и находит n-й арифметикой; связный список хранит каждый элемент где-то в памяти вместе с указателем на следующий; хеш-таблица хранит значения под ключами и вычисляет, где место каждого ключа. Из этих трёх построены почти все остальные структуры.

Почему это важно

Разница не академическая: поиск значения в неупорядоченном массиве из десяти тысяч записей стоит десять тысяч сравнений, а хеш-таблица — примерно одного. Добавление в связный список мгновенно, тогда как добавление в полный массив вынуждено скопировать всё, и всё же обход связного списка из десяти тысяч узлов может оказаться медленнее обхода массива: каждый узел заставляет прыгнуть в случайное место памяти. Ошибка здесь даёт код, функционально верный и загадочно медленный.

Ключевые идеи

Непрерывная память — быстрый путь

Массив целых одинакового размера индексируется одним умножением: address = base + index * width. Чтение очередного элемента тянет за собой всю строку кэша, поэтому движение вперёд быстро даже для миллионов записей. Платить приходится тем, что блок должен найтись свободным и непрерывным, а вставка в середину требует сдвинуть всё после неё.

массив из 5: [10][20][30][40][50]
чтение индекса 3  -> base + 3 * width   (один шаг)
вставка в 1       -> сдвинуть 20,30,40,50 вправо, затем записать

Динамические массивы растут удвоением

«Список» в большинстве языков оказывается динамическим массивом — непрерывным блоком с длиной и ёмкостью. Когда блок заполняется, среда выделяет вдвое больший и копирует элементы туда; одно добавление, вызвавшее копирование, дорого, но размазанное по всем добавлениям, которые заполнили блок, оно в среднем константно. Такова амортизированная стоимость: редкие всплески при ровном среднем.

ёмкость 4, длина 4 -> добавить -> выделить 8, копировать 4, записать 1
следующие 3 добавления -> выделения нет вовсе

Связные списки меняют локальность на дешёвую вставку

Связному списку нужно только чтобы узел был свободен, а не непрерывный отрезок, а вставка после уже удерживаемого узла оборачивается парой записей указателей. Арифметического ярлыка здесь нет: тысячный элемент означает тысячу переходов по указателям в тысячу строк кэша. Связные списки выигрывают, когда элементы постоянно добавляют и удаляют и редко обходят, а в остальных случаях сильно проигрывают.

узел A -> узел C -> узел F
вставка B после A:  A.next = B; B.next = C

Хеш-таблицы превращают ключ в ячейку

Хеш-функция превращает ключ в число, которое выбирает ячейку в массиве. Два ключа могут попасть в одну ячейку, поэтому таблице нужна стратегия разрешения коллизий: цепочка на списке или поиск свободной ячейки. По мере заполнения коллизии учащаются, поэтому по достижении порога заполнения таблица перехешируется в большую, а порядок обхода следует за хешем и размером таблицы — потому-то он и документируется как неопределённый.

hash("alice") -> 4  -> ячейка 4: ["alice" -> 30]
hash("bob")   -> 7  -> ячейка 7: ["bob"   -> 41]
lookup("bob"): хешировать, прыжок в ячейку 7, сравнить ключи

Читайте операцию, которую делаете чаще всего

Выпишите три-четыре операции, которые код выполняет чаще всего. Если это поиск по ключу — берите таблицу; если индексация или скан по порядку — берите массив; если удаление из середины при удерживаемой ссылке — связная структура заслуживает места. Тянитесь к чему-то экзотическому только тогда, когда эти требования конфликтуют.

Практика

Посчитайте стоимость своего поиска

Возьмите функцию, написанную на этой неделе, которая ищет по коллекции. Определите её тип, посчитайте элементы, которые она держит в продакшене, и сравнения, которые стоят одного поиска.

Готово, когда: вы можете назвать стоимость через число элементов и сказать, скан это или прыжок.

Замените скан таблицей

Найдите цикл, который сканирует список, чтобы найти один элемент по id. Постройте хеш-таблицу с ключом по этому значению один раз, затем замените скан поиском.

Готово, когда: функция даёт те же результаты, а скан исчез с горячего пути.

Частые ошибки

• Убеждение, что список устроен как массив — связный список и динамический массив носят одно имя во многих языках, но противоположны по производительности; исправить: проверьте тип, который даёт ваш язык, и то, как он растёт.
• Линейный скан внутри цикла — код становится квадратичным и выглядит как обычный перебор; исправить: постройте таблицу один раз и ищите в ней вместо сканирования.
• Опора на порядок обхода хеш-таблицы — порядок меняется вместе с хешем и размером таблицы, поэтому вывод перетасовывается между запусками; исправить: сортируйте ключи явно, когда порядок важен.
• Изменяемый объект как ключ хеша — его изменение меняет хеш, и значение становится недостижимым; исправить: ключом делайте неизменяемое значение, например строку с id.
• Удаление из середины динамического массива в цикле — каждое удаление сдвигает хвост, поэтому цикл становится квадратичным; исправить: отфильтруйте в новую коллекцию или идите по циклу с конца.

Что читать дальше

• Алгоритмы и Big-O (01-cs-fundamentals/14-algorithms-big-o) — как описывать только что встреченные стоимости без отговорок.
• Деревья, кучи и графы (01-cs-fundamentals/02-data-structures/02-trees-heaps-and-graphs) — что использовать, когда данные упорядочены или связаны.
• Псевдокод (01-cs-fundamentals/07-pseudocode) — набросок схемы доступа, прежде чем её фиксировать.