2.3.1 — от последовательности узлов до O(1) доступа по ключу2.3.1 — from a sequence of nodes to O(1) access by key
Первая тема раздела о структурах данных начинается с самого простого: последовательности элементов, связанных ссылками, и способа сделать поиск по ключу практически мгновенным, а не линейным. Здесь: связные списки и кольцевые буферы как база, затем хеш-таблицы во всех основных вариантах — от простых цепочек до продвинутых схем разрешения коллизий, до вероятностных структур, построенных на той же идее хеширования.The first topic in the data-structures section starts with the simplest thing: a sequence of elements linked by references, and a way to make key lookup practically instant instead of linear. Here: linked lists and ring buffers as the baseline, then hash tables in all their major variants — from simple chaining to advanced collision-resolution schemes, to probabilistic structures built on the same hashing idea.
Связный список и кольцевой буфер — структуры, где позиция элемента определяется его местом в последовательности: чтобы найти элемент, нужно пройти к нему от начала (или воспользоваться известным индексом в буфере). Хеш-таблица меняет саму модель доступа: позиция элемента определяется не порядком вставки, а значением его ключа, пропущенным через хеш-функцию, — поиск, вставка и удаление становятся в среднем O(1), независимо от того, сколько элементов уже хранится. Разница между вариантами хеш-таблиц в этой теме — не в этой базовой идее, а в том, как разрешается коллизия, когда двум разным ключам выпадает одна и та же позиция.Linked lists and ring buffers are structures where an element's position is defined by its place in the sequence: finding it means walking to it from the start (or using a known index in the buffer). A hash table changes the access model itself: an element's position is defined not by insertion order but by its key's value passed through a hash function — lookup, insertion, and deletion become O(1) on average, regardless of how many elements are already stored. The difference between the hash-table variants in this topic isn't in this basic idea, but in how a collision is resolved when two different keys land on the same slot.
хеш-функция превращает поиск из "идти и проверять" в "вычислить и попасть сразу"the hash function turns lookup from "walk and check" into "compute and land directly"
Порядок в карточках — от простейшей идеи до всё более изощрённых способов бороться с коллизиями и их последствиями. Полный разбор с диаграммами, кодом и живой демонстрацией — на отдельной странице по ссылке в названии.The card order goes from the simplest idea to increasingly refined ways of fighting collisions and their consequences. The full writeup with diagrams, code, and a live demo is on its own page via the name link.
Первые две карточки — линейные структуры без хеширования, база для понимания того, от чего хеш-таблицы отталкиваются. Следующие пять — хеш-таблицы с разными стратегиями разрешения коллизий, от простейшей (цепочки) до специализированной (идеальное хеширование для статичных наборов). Последние две — структуры, построенные на идее хеширования или вероятностного поиска, но решающие другие задачи: Bloom Filter жертвует точностью ради экономии памяти, Skip List заменяет хеширование вероятностной многоуровневой связностью, приближаясь по гарантиям к сбалансированным деревьям из 2.3.2.The first two cards are linear structures without hashing — the baseline for understanding what hash tables build on. The next five are hash tables with different collision-resolution strategies, from the simplest (chaining) to the specialized (perfect hashing for static sets). The last two are structures built on hashing or probabilistic search ideas, but solving different problems: Bloom Filter trades accuracy for memory savings, Skip List replaces hashing with probabilistic multi-level connectivity, approaching the guarantees of balanced trees from 2.3.2.
Классическая реализация LRU-кэша сочетает двусвязный список (для O(1) перемещения элемента в начало при обращении и удаления с конца при вытеснении) и хеш-таблицу (для O(1) поиска узла по ключу) — ни одна из структур по отдельности не даёт всех нужных гарантий.The classic LRU cache implementation combines a doubly linked list (for O(1) moving an element to the front on access and removal from the back on eviction) and a hash table (for O(1) lookup of a node by key) — neither structure alone provides all the needed guarantees.
Буферизация аудиопотока между производителем данных (декодером) и потребителем (звуковой картой) почти всегда реализована кольцевым буфером фиксированного размера — предсказуемое использование памяти и отсутствие аллокаций в реальном времени критичны для низкой задержки.Buffering an audio stream between a data producer (decoder) and consumer (sound card) is almost always implemented with a fixed-size ring buffer — predictable memory use and zero real-time allocations are critical for low latency.
Rust'овский hashbrown (используемый в std::collections::HashMap) и многие C++ библиотеки используют вариации Robin Hood hashing именно из-за предсказуемо низкой дисперсии времени поиска, важной для приложений, чувствительных к задержкам хвоста распределения (tail latency).Rust's hashbrown (used in std::collections::HashMap) and many C++ libraries use variations of Robin Hood hashing precisely for the predictably low lookup-time variance, important for applications sensitive to tail latency.
RocksDB, Cassandra и другие хранилища на основе LSM-деревьев используют Bloom-фильтр перед каждым дисковым чтением SSTable — "точно нет" отвечается мгновенно без обращения к диску, что даёт огромный выигрыш, когда искомый ключ отсутствует в большинстве файлов.RocksDB, Cassandra, and other LSM-tree-based stores use a Bloom filter before every SSTable disk read — a "definitely not present" answer is instant with no disk access, a huge win when the sought key is absent from most files.
Redis реализует ZSET (упорядоченное множество) через skip list именно потому, что она проще в реализации и настройке, чем сбалансированное дерево, при сравнимой O(log n) гарантии — тот же выбор сделан для memtable во многих LSM-движках хранения.Redis implements ZSET (a sorted set) via a skip list precisely because it's simpler to implement and tune than a balanced tree, with a comparable O(log n) guarantee — the same choice is made for the memtable in many LSM storage engines.
O(1) в среднем для хеш-таблиц держится только при разумном load factor (обычно < 0.7-0.75); при приближении к 1.0 (особенно в открытой адресации) время поиска резко деградирует к O(n) — рост таблицы должен запускаться заранее, а не когда она уже полностью заполнена.O(1) average for hash tables only holds at a reasonable load factor (typically < 0.7-0.75); as it approaches 1.0 (especially with open addressing), lookup time degrades sharply toward O(n) — table growth must trigger early, not once the table is already completely full.
В открытой адресации нельзя просто очистить слот при удалении — это разорвёт цепочку проб для более поздних вставок с той же начальной позицией; нужен специальный маркер "удалено, но не пусто" (tombstone), что усложняет реализацию по сравнению с цепочками, где удаление узла из списка ничего не ломает.In open addressing, a slot can't simply be cleared on deletion — that would break the probe chain for later insertions sharing the same starting position; a special "deleted but not empty" marker (tombstone) is needed, complicating the implementation compared to chaining, where removing a node from the list breaks nothing.
Классический Bloom Filter не поддерживает удаление — сброс одного бита может ложно "удалить" другой элемент, чей набор битов пересекается с удаляемым; для удаляемых наборов нужен Counting Bloom Filter (счётчики вместо битов) — другая структура с другими компромиссами по памяти.A classic Bloom filter doesn't support removal — clearing one bit can falsely "remove" another element whose bit set overlaps with the one being removed; for removable sets, a Counting Bloom Filter (counters instead of bits) is needed — a different structure with different memory trade-offs.