Как выбрать структуру данных

Пункт «не изобретайте велосипед» стоит развернуть: в стандартной библиотеке уже лежат реализации всех структур, о которых шла речь, и выбор на практике превращается в выбор класса. Вот карта соответствия.

По умолчанию берут ArrayList и HashMap — вдвоём они закрывают большинство задач. ArrayDeque — когда нужен стек или очередь, TreeMap — когда нужен порядок или диапазоны, PriorityQueue — когда всегда нужен самый срочный элемент. Остальное — узкие случаи.

Две группы классов из той же библиотеки, которые в таблицу не попали, а выбираются тем же вопросом «какие операции частые». Неизменяемые коллекции List.of, Set.of, Map.of и List.copyOf для данных, которые записали один раз и только читают: они компактнее изменяемых, их безопасно отдавать наружу и делить между потоками, а любая попытка изменить бросает UnsupportedOperationException; ловушки те же, что в примерах фазы, где List.of встречается трижды: null в них класть нельзя, у Map.of предел десять пар.

Специализированные структуры под конкретный тип ключа: EnumMap и EnumSet для enum-ключей (массив по порядковому номеру и битовая маска вместо хеширования), BitSet для миллионов флагов, int[] и long[] вместо List<Integer> для чисел в горячем коде. Все три разобраны в статье про коллекции и в разделах ниже; правило одно: если тип ключа известен и узок, под него есть структура компактнее общей.

Картинку из начала статьи можно выполнить: те же ключи в трёх классах, каждому свой вопрос.

живой пример

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Lookup {
    public static void main(String[] args) {
        int[] ids = {50, 25, 75, 10, 60, 90, 42};
        List<Integer> list = new ArrayList<>();
        Map<Integer, String> hash = new HashMap<>();
        TreeMap<Integer, String> tree = new TreeMap<>();
        for (int id : ids) {
            list.add(id);
            hash.put(id, "заказ " + id);
            tree.put(id, "заказ " + id);
        }
        int steps = 0;
        for (int id : list) {
            steps++;
            if (id == 42) break;
        }
        System.out.println("список: " + steps + " сравнений до ключа 42");
        System.out.println("хеш-таблица: " + hash.get(42) + ", обход " + hash.keySet());
        System.out.println("дерево: " + tree.get(42) + ", следующий ключ " + tree.higherKey(42));
    }
}

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

Грабля. Самая частая ошибка при выборе структуры — не сам выбор, а то, что его потом нельзя поменять. Если конкретный класс попал в объявления полей, параметры и возвращаемые типы, замена превращается в правку по всему коду — и её просто не делают, даже когда видно, что выбрано неудачно.

List<Order> orders = new ArrayList<>();
ArrayList<Order> pinned = new ArrayList<>();

Первая строка оставляет свободу: сменить реализацию можно в одном месте. Вторая приколачивает выбор к сигнатурам. Правило простое: переменные, поля, параметры и возвращаемые типы объявляют интерфейсом (List, Map, Set, Deque), а конкретный класс называют один раз — в new. Интерфейс берут по нужному поведению: List — доступ по индексу, Deque — работа с концами, NavigableMap — диапазонные запросы. Тогда вывод «здесь всё-таки нужен порядок» стоит одну строку, а не день правок.

Пункт «не изобретайте велосипед» в Go звучит с оговоркой: в стандартной библиотеке лежат срез, map и три пакета container, а дерево и приоритетную очередь приходится либо собирать, либо брать пакетом. Выбор на практике всё равно превращается в выбор типа. Вот карта соответствия.

По умолчанию берут срез и map — вдвоём они закрывают большинство задач. Канал — когда очередь связывает горутины, отсортированный срез — когда нужен порядок или диапазоны на редко меняющихся данных, container/heap — когда всегда нужен самый срочный элемент. Остальное — узкие случаи.

Две вещи, которые в таблицу не попали, а выбираются тем же вопросом. Неизменяемых коллекций в Go нет: срез и map меняемы всегда, и «только для чтения» обеспечивают копией через slices.Clone и maps.Clone перед тем, как отдать наружу, или типом с методами только на чтение. Специализированные структуры под узкий тип: map[K]struct{} вместо множества с булевыми значениями (пустая структура не занимает памяти), массив [N]bool или битовая маска вместо map[int]bool для флагов по номеру, []int64 вместо []any для чисел; правило одно: если тип ключа известен и узок, под него есть структура компактнее общей. Память на элемент: 8 байт на число в []int64, около 40 байт на узел container/list плюс упакованное значение, в map ключ и значение подряд плюс байт метки и запас незаполненных слотов, примерно на треть больше самих данных, около 100 байт на узел дерева из пакета.

Картинку из начала статьи можно выполнить: те же ключи в трёх структурах, каждой свой вопрос.

живой пример

package main

import (
	"fmt"
	"slices"
)

func main() {
	ids := []int{50, 25, 75, 10, 60, 90, 42}
	var list []int
	hash := map[int]string{}
	var tree []int // отсортированный срез вместо дерева
	for _, id := range ids {
		list = append(list, id)
		hash[id] = fmt.Sprintf("заказ %d", id)
		i, _ := slices.BinarySearch(tree, id)
		tree = slices.Insert(tree, i, id)
	}
	steps := 0
	for _, id := range list {
		steps++
		if id == 42 {
			break
		}
	}
	fmt.Println("список:", steps, "сравнений до ключа 42")
	keys := make([]int, 0, len(hash))
	for k := range hash {
		keys = append(keys, k)
	}
	fmt.Println("хеш-таблица:", hash[42], ", обход", keys)
	i, _ := slices.BinarySearch(tree, 42)
	fmt.Println("отсортированный срез: заказ", tree[i], ", следующий ключ", tree[i+1])
}

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

Грабля. Самая частая ошибка при выборе структуры — не сам выбор, а то, что его потом нельзя поменять. Если map[int]Order или []Order разошлись по сигнатурам функций и полям других пакетов, замена превращается в правку по всему коду — и её просто не делают, даже когда видно, что выбрано неудачно.

type Orders struct{ byID map[int]Order } // структура спрятана, менять можно в одном месте

func process(orders map[int]Order) {} // структура торчит в сигнатуре

Первая запись оставляет свободу: сменить map на отсортированный срез или дерево можно внутри типа, не трогая вызывающих. Вторая приколачивает выбор к сигнатуре. Правило простое: структуру данных прячут в тип с методами под нужное поведение, Get, Add, Range, а наружу отдают этот тип или маленький интерфейс. Тогда вывод «здесь всё-таки нужен порядок» стоит одну правку, а не день.

Пункт «не изобретайте велосипед» в JavaScript звучит с оговоркой: в языке лежат массив, Map и Set, а дерево, приоритетную очередь и честную очередь приходится либо собирать, либо брать пакетом. Выбор на практике всё равно превращается в выбор структуры. Вот карта соответствия.

По умолчанию берут Array и Map — вдвоём они закрывают большинство задач. Массив с индексом головы — когда нужна очередь, отсортированный массив — когда нужен порядок или диапазоны на редко меняющихся данных, самодельная куча — когда всегда нужен самый срочный элемент. Остальное — узкие случаи.

Две вещи, которые в таблицу не попали, а выбираются тем же вопросом. Неизменяемость даёт Object.freeze: замороженный массив или объект нельзя изменить, в строгом режиме попытка бросает TypeError; заморозка поверхностная, вложенные объекты остаются меняемыми. Специализированные структуры под узкий тип: типизированные массивы Int32Array и Float64Array для чисел, компактные и без переездов; WeakMap и WeakSet, когда ключи — объекты и таблица не должна их удерживать; Object.create(null) для словаря со строковыми ключами без прототипа. Правило одно: если тип известен и узок, под него есть структура компактнее общей. Память на элемент: 4–8 байт на число в типизированном массиве и в плотном массиве целых, 30–40 байт на запись Map сверх ключа и значения, десятки байт на каждый объект-узел самодельного списка или дерева.

Картинку из начала статьи можно выполнить: те же ключи в трёх структурах, каждой свой вопрос.

живой пример

function lowerBound(a, key) {
  let lo = 0;
  let hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (a[mid] < key) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const ids = [50, 25, 75, 10, 60, 90, 42];
const list = [];
const hash = new Map();
const tree = []; // отсортированный массив вместо дерева
for (const id of ids) {
  list.push(id);
  hash.set(id, `заказ ${id}`);
  tree.splice(lowerBound(tree, id), 0, id);
}
let steps = 0;
for (const id of list) {
  steps++;
  if (id === 42) break;
}
console.log("список:", steps, "сравнений до ключа 42");
console.log("хеш-таблица:", hash.get(42), ", обход", [...hash.keys()]);
const i = lowerBound(tree, 42);
console.log("отсортированный массив: заказ", tree[i], ", следующий ключ", tree[i + 1]);

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

Грабля. Самая частая ошибка при выборе структуры — не сам выбор, а то, что его потом нельзя поменять. Если Map или массив разошлись по сигнатурам функций и полям других модулей, замена превращается в правку по всему коду — и её просто не делают, даже когда видно, что выбрано неудачно.

class Orders {                       // структура спрятана, менять можно в одном месте
  #byId = new Map();
  get(id) { return this.#byId.get(id); }
}

function process(ordersById) {}      // Map торчит в сигнатуре и во всех вызовах

Первая запись оставляет свободу: сменить Map на отсортированный массив или дерево можно внутри класса, не трогая вызывающих. Вторая приколачивает выбор ко всем местам, где функцию зовут. Правило простое: структуру данных прячут за классом или модулем с методами под нужное поведение, get, add, range, а наружу отдают их; в TypeScript то же делает интерфейс. Тогда вывод «здесь всё-таки нужен порядок» стоит одну правку, а не день.

Пункт «не изобретайте велосипед» стоит развернуть: в стандартной библиотеке уже лежат реализации почти всех структур, о которых шла речь, а недостающие дерево и упорядоченную карту закрывает один пакет. Выбор на практике превращается в выбор типа. Вот карта соответствия.

По умолчанию берут list и dict — вдвоём они закрывают большинство задач. deque — когда нужна очередь, bisect над отсортированным списком или SortedDict — когда нужен порядок или диапазоны, heapq — когда всегда нужен самый срочный элемент. Остальное — узкие случаи.

Две группы типов из той же библиотеки, которые в таблицу не попали, а выбираются тем же вопросом «какие операции частые». Неизменяемые коллекции tuple, frozenset и types.MappingProxyType для данных, которые записали один раз и только читают: кортеж компактнее списка, frozenset годится ключом словаря, а попытка изменить любой из них бросает TypeError или AttributeError. Специализированные структуры под конкретный тип: array('i') и NumPy для чисел без объектов-обёрток, bytearray для байтов и флагов, collections.Counter и defaultdict для подсчётов и группировок, enum.Flag для наборов флагов. Правило одно: если тип известен и узок, под него есть структура компактнее общей. Память на элемент: 8 байт на ссылку в list плюс 28 байт на сам объект int, 4 байта на число в array('i'), около 30 байт сверх ключа и значения в dict, около 100 байт на узел дерева на чистом Python.

Картинку из начала статьи можно выполнить: те же ключи в трёх структурах, каждой свой вопрос.

живой пример

from bisect import bisect_left, insort

ids = [50, 25, 75, 10, 60, 90, 42]
items: list[int] = []
hashed: dict[int, str] = {}
tree: list[int] = []            # отсортированный список вместо дерева
for order_id in ids:
    items.append(order_id)
    hashed[order_id] = f"заказ {order_id}"
    insort(tree, order_id)
steps = 0
for order_id in items:
    steps += 1
    if order_id == 42:
        break
print("список:", steps, "сравнений до ключа 42")
print("хеш-таблица:", hashed[42], ", обход", list(hashed))
i = bisect_left(tree, 42)
print("отсортированный список: заказ", tree[i], ", следующий ключ", tree[i + 1])

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

Грабля. Самая частая ошибка при выборе структуры — не сам выбор, а то, что его потом нельзя поменять. Если dict или list разошлись по сигнатурам функций и полям других модулей, замена превращается в правку по всему коду — и её просто не делают, даже когда видно, что выбрано неудачно.

class Orders:                       # структура спрятана, менять можно в одном месте
    def __init__(self) -> None:
        self._by_id: dict[int, Order] = {}

    def get(self, order_id: int) -> Order: ...


def process(orders_by_id: dict[int, Order]) -> None: ...   # dict торчит в сигнатуре

Первая запись оставляет свободу: сменить dict на отсортированный список или SortedDict можно внутри класса, не трогая вызывающих. Вторая приколачивает выбор ко всем местам, где функцию зовут. Правило простое: структуру данных прячут за классом с методами под нужное поведение, get, add, range, а в подсказках типов параметров пишут абстракции из collections.abc, Mapping и Sequence, а не dict и list. Тогда вывод «здесь всё-таки нужен порядок» стоит одну правку, а не день.

int mask = 0;
mask |= 1 << 3;                 // включить флаг 3
boolean on = (mask & (1 << 3)) != 0;
mask &= ~(1 << 3);              // выключить
int both = maskA & maskB;       // пересечение наборов
int count = Integer.bitCount(mask);

mask := 0
mask |= 1 << 3                     // включить флаг 3
on := mask&(1<<3) != 0
mask &^= 1 << 3                    // выключить: в Go для этого есть &^
both := maskA & maskB              // пересечение наборов
count := bits.OnesCount(uint(mask)) // math/bits

let mask = 0;
mask |= 1 << 3;                    // включить флаг 3
const on = (mask & (1 << 3)) !== 0;
mask &= ~(1 << 3);                 // выключить
const both = maskA & maskB;        // пересечение наборов
const count = mask.toString(2).replace(/0/g, "").length; // число единиц: своего bitCount нет

mask = 0
mask |= 1 << 3                     # включить флаг 3
on = mask & (1 << 3) != 0
mask &= ~(1 << 3)                  # выключить
both = mask_a & mask_b             # пересечение наборов
count = mask.bit_count()           # число единиц, с Python 3.10

Когда флагов миллионы, берут java.util.BitSet: тот же принцип поверх массива long, растёт по мере надобности, умеет and, or, cardinality и nextSetBit для быстрого перебора включённых. Миллион флагов в BitSet это 125 килобайт против мегабайта в boolean[] и десятков мегабайт в HashSet<Integer>; поэтому им отмечают «посещённые» идентификаторы, занятые слоты и просмотренные записи.

Когда флагов миллионы, битовый набор собирают из []uint64: флаг i живёт в слове i/64 под битом i%64, объединение и пересечение это цикл по словам с | и &, а число включённых считает bits.OnesCount64 из math/bits. Готового типа в стандартной библиотеке нет, но math/big.Int с SetBit и Bit годится как растущий набор, а пакет bits-and-blooms/bitset даёт всё сразу. Миллион флагов это 125 килобайт против мегабайта в []bool и десятков мегабайт в map[int]struct{}; поэтому ими отмечают «посещённые» идентификаторы, занятые слоты и просмотренные записи.

Здесь есть ловушка: побитовые операции в JavaScript работают с 32-битными целыми, 1 << 31 даёт отрицательное число, а 1 << 32 равно единице. Больше 31 флага в одном числе не бывает; для больших наборов либо BigInt, у которого сдвиги и & без предела, либо Uint32Array, где флаг i живёт в слове i >>> 5 под битом i & 31. Готового битового набора в языке нет, число единиц считают циклом или через toString(2). Миллион флагов в Uint32Array это 125 килобайт против мегабайта в массиве булевых и десятков мегабайт в Set; поэтому ими отмечают «посещённые» идентификаторы, занятые слоты и просмотренные записи.

В Python битовый набор любого размера это обычный int: целые не ограничены, mask |= 1 << 1_000_000 просто работает, & и | объединяют наборы одной операцией над всем числом, а bit_count() считает включённые. Плата — каждая операция создаёт новое число, для миллиона флагов это копирование 125 килобайт на каждый сдвиг; когда флаги меняют по одному, берут bytearray или массив bool в NumPy. Миллион флагов в int это те же 125 килобайт против восьми мегабайт в списке bool и десятков мегабайт в set; поэтому ими отмечают «посещённые» идентификаторы, занятые слоты и просмотренные записи.

Выбор выше шёл по операциям, порядку и объёму. Четвёртая ось: сколько потоков трогают структуру одновременно. Обычные HashMap и ArrayList рассчитаны на один поток: параллельная запись ломает их без исключений, молча теряя элементы или зацикливая обход. Collections.synchronizedMap вешает один замок на всё и превращает многопоточность в очередь.

В java.util.concurrent под каждую роль своя структура. ConcurrentHashMap делит таблицу на независимые участки, читатели не блокируются вовсе, а compute и merge дают атомарное «прочитать и обновить» без внешнего замка. CopyOnWriteArrayList копирует массив целиком при каждой записи, зато обход никогда не видит полуготового состояния: для списков слушателей, которые читают тысячи раз, а меняют раз в день. BlockingQueue (ArrayBlockingQueue, LinkedBlockingQueue) это очередь, у которой take ждёт элемент, а put ждёт место: способ связать поток-производитель с потоком-потребителем и естественный ограничитель нагрузки. ConcurrentSkipListMap заменяет TreeMap, когда нужен порядок ключей.

Правило выбора то же, что для однопоточных структур, плюс один вопрос: кто пишет и кто читает. Много читателей и редкая запись: copy-on-write; частая запись по ключам: сегментированная таблица; передача работы между потоками: блокирующая очередь. Как эти структуры устроены внутри и что бывает с обычными при гонке, разбирает фаза про многопоточность.

Выбор выше шёл по операциям, порядку и объёму. Четвёртая ось: сколько горутин трогают структуру одновременно. Обычные map и срез рассчитаны на одну горутину: параллельная запись в срез портит его молча, а в map среда выполнения ловит гонку и роняет процесс фатальной ошибкой concurrent map writes, которую не поймать через recover. Детектор go test -race находит такие гонки на тестах, и его включают всегда.

Готовых потокобезопасных коллекций в Go немного, потому что подход другой: делить память через каналы, а не каналы через память. sync.Mutex и sync.RWMutex вокруг обычной map закрывают большинство случаев, при RWMutex читатели идут параллельно. sync.Map рассчитана на узкий случай «ключ записали один раз, читают много» вроде кешей; на частой записи она медленнее map с мьютексом. Канал с буфером и есть блокирующая очередь: отправка ждёт место, приём ждёт элемент, это способ связать горутину-производителя с потребителем и естественный ограничитель нагрузки. Атомарное «прочитать и обновить» даёт пакет sync/atomic для чисел и указателей, а для map — мьютекс вокруг пары операций.

Правило выбора то же, что для однопоточных структур, плюс один вопрос: кто пишет и кто читает. Много читателей и редкая запись: RWMutex или sync.Map; частая запись по ключам: map под мьютексом, при большом числе горутин — несколько таблиц по хешу ключа; передача работы между горутинами: канал. Как это устроено внутри и что бывает с обычными структурами при гонке, разбирает фаза про горутины.

Выбор выше шёл по операциям, порядку и объёму. Четвёртая ось в других языках — сколько потоков трогают структуру; в JavaScript она почти исчезает. Код в одном потоке выполняется по очереди, обработчик события дорабатывает до конца, и Map или массив нельзя испортить одновременной записью: конкурентных коллекций в языке нет, потому что они не нужны.

Гонки всё же есть, только другие. Они живут на границе await: код прочитал значение из Map, ушёл ждать ответа базы, а за это время другой обработчик успел его изменить, и запись после await перезаписывает чужую. Проверка «есть ли ключ» и последующая вставка, разделённые await, — та же ошибка «прочитать и обновить», что в многопоточных языках, только без потоков. Лечат её так же: одна операция без ожиданий между проверкой и записью, или явный замок на ключ, обычно Map из промисов, по которому ждут предыдущую операцию.

Настоящие потоки в Node это worker_threads, и память они не делят: в воркер передают копии через postMessage, а общую память дают только SharedArrayBuffer с операциями Atomics, где нет ни Map, ни объектов, только числа в типизированном массиве. Блокирующей очереди в языке тоже нет; между обработчиками её заменяет обычный массив, между воркерами — сообщения. Правило выбора сводится к одному вопросу: нет ли await между чтением и записью.

Выбор выше шёл по операциям, порядку и объёму. Четвёртая ось: сколько потоков трогают структуру одновременно. У Python здесь особое положение: глобальная блокировка интерпретатора пускает к байткоду один поток за раз, поэтому отдельная операция с list или dict, append или d[k] = v, атомарна и структуру не портит. Ломается составное: «проверить, что ключа нет, и записать» или «прочитать счётчик и увеличить» — между двумя операциями поток могут переключить, и результат теряется без исключений.

Поэтому готовых конкурентных коллекций в стандартной библиотеке мало, а нужны в основном замки и очереди. threading.Lock вокруг составной операции закрывает большинство случаев. queue.Queue это блокирующая очередь: get ждёт элемент, put ждёт место в ограниченной очереди, это способ связать поток-производитель с потоком-потребителем и естественный ограничитель нагрузки; queue.PriorityQueue даёт то же с приоритетами. collections.Counter и defaultdict от гонок не защищают, их тоже закрывают замком. Процессы из multiprocessing памяти не делят вовсе, между ними ходят копии через очереди и Manager.

В коде на asyncio гонки живут на границе await, как в JavaScript: между чтением и записью не должно быть ожидания, иначе другая задача успеет изменить данные; asyncio.Lock и asyncio.Queue это те же замок и очередь для задач вместо потоков. Правило выбора то же, что для однопоточных структур, плюс один вопрос: есть ли между чтением и записью точка, где поток или задачу могут переключить. Как это устроено внутри, разбирает фаза про конкурентность.

• Четвёртая ось выбора, потоки: ConcurrentHashMap для частой записи по ключам, CopyOnWriteArrayList для редкой записи, BlockingQueue для передачи работы.
• Память на элемент это отдельная ось: 4 байта в int[], около 20 в ArrayList<Integer>, 40 в LinkedList, 50 в HashMap, 60 в TreeMap; неизменяемые List.of/Map.of для данных «записал и читаю», EnumMap, BitSet и массивы примитивов для узких типов ключей.

• Четвёртая ось выбора, горутины: map под sync.RWMutex для записи по ключам, sync.Map для «записал раз, читаю много», канал для передачи работы; гонку в map среда выполнения роняет фатально, go test -race ловит раньше.
• Память на элемент: 8 байт в []int64, около 40 на узел container/list плюс упаковка, в map данные подряд с запасом слотов; неизменяемых коллекций нет, наружу отдают копию; map[K]struct{} и битовые маски для узких ключей.

• Четвёртая ось, потоки, в JavaScript сводится к await: гонка это чтение и запись, разделённые ожиданием; воркеры памяти не делят, кроме SharedArrayBuffer с Atomics.
• Память на элемент: 4–8 байт в типизированном и плотном массиве, 30–40 на запись Map; Object.freeze для данных «записал и читаю», Int32Array, WeakMap и Object.create(null) для узких случаев.

• Четвёртая ось выбора, потоки: отдельная операция атомарна благодаря GIL, составная нет — threading.Lock, queue.Queue для передачи работы, в asyncio гонка на await.
• Память на элемент: 8 байт ссылки плюс 28 на объект int в list, 4 байта в array('i'), около 30 сверх ключа и значения в dict; tuple и frozenset для данных «записал и читаю», Counter, bytearray и enum.Flag для узких типов.