Лекция 9. Hash Array Mapped Trie

Андрей Гейн: Мы построим необычную хеш-таблицу, а затем сделаем её итерабельной, персистентной и даже lock-free. Такая хэш-таблица используется в стандартных библиотеках Clojure, Haskell и Scala, так как в функциональных языках программирования персистентность — важное свойство структур данных. Субъективная сложность лекции — четыре теты из пяти. Содержание: 0:59 Сравнение хэш-таблиц и деревьев поиска 3:20 Хранение ключей в префиксном дереве 11:10 Оптимизация: битовые маски и массивы переменной длины 22:37 Оптимизация: пулы вершин 26:59 Компромиссы в сравнении с хэш-таблицами и деревьями поиска 32:18 Другие неасимптотические оптимизации 38:42 Персистентность в однопоточном варианте 46:15 Краткое отступление про неблокирующие алгоритмы 52:48 Неблокирующий многопоточный вариант 1:14:07 Снэпшоты в неблокирующем варианте