Ктри
-
Описание Ctrie
- Параллельная потокобезопасная реализация хэш-массива без блокировок
- Используется для реализации абстракции параллельной карты
- Поддерживает O(1) атомарные моментальные снимки без блокировок
-
Структура данных
- Неблокирующий параллельный хэш-массив на основе команд сравнения и подкачки
- Использует 32-битное пространство для хэш-значений
- Каждый узел может содержать до 32 подузлов
- Ключи вставляются путем атомарной операции CAS
-
Операции
- Вставка: атомарная операция CAS для замены старого узла на новый
- Удаление: атомарная операция CAS для удаления узла
- Поиск: операция, изменяющая различные части хэш-файла
-
Преимущества
- Сопоставимая производительность с параллельными списками пропусков и хэш-таблицами
- Более масштабируемые вставки по сравнению с хэш-таблицами
- Выделенная память зависит только от текущего количества ключей
- Логарифмические границы сложности базовых операций
- Поддержка моментальных снимков с постоянным временем
-
Проблемы
- Динамическое выделение памяти и сборка мусора
- Текущая реализация для JVM
- Ручное управление памятью узлов
-
Реализации
- Реализация для Scala 2.9.x, ScalaSTM, Haskell, Java, CL-CTRIE, Go, Rust, Clojure
- История: впервые описана в 2011 году, пересмотрена в 2012 году, дополнена Cache-Trie в 2018 году