Деревья и хэш-таблицы

Деревья и хэш-таблицы

Технический фундамент комбинированных моделей

В реальных приложениях часто эффективнее комбинировать структуры:

  • дерево хранит отношения "родитель-дети";
  • Map дает быстрый доступ по ключу;
  • вместе они дают и правильную модель, и быстрый lookup.

Ключевая инженерная задача тут не только построить структуру, но и поддерживать консистентность при обновлениях.

Почему эти структуры появляются в прод-коде

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

Ключевой момент: дерево хорошо отражает вложенность, а хэш-таблица хорошо решает быстрый поиск по ключу.

Проверь себя: почему меню "категория -> подкатегория -> товар" удобнее хранить как дерево, а не как плоский массив?

Дерево: иерархическая структура

В дереве есть узлы (node), корень (root) и связи "родитель -> дети".

const tree = {
  value: 'Каталог',
  children: [
    { value: 'Электроника', children: [] },
    { value: 'Одежда', children: [] },
  ],
};

Новый термин: обход дерева - способ пройти все узлы в определенном порядке (DFS/BFS).

Мини-обход в глубину (DFS):

function walk(node) {
  console.log(node.value);
  for (const child of node.children) {
    walk(child);
  }
}

Смотри, что важно: дерево отлично подходит для вложенных комментариев, категорий, DOM-структуры.

Хэш-таблица: быстрый доступ по ключу

В JavaScript роль хэш-таблицы обычно играет Map (или объект в простых случаях).

const usersById = new Map();
usersById.set('u1', { name: 'Anna' });
usersById.set('u2', { name: 'Max' });

console.log(usersById.get('u2')); // { name: 'Max' }

Ожидаемая сложность доступа - близко к O(1) в среднем.

Проверь себя: почему для частого getById на больших данных Map обычно лучше линейного поиска по массиву?

Где что использовать

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

Часто они работают вместе:

  • дерево для структуры UI;
  • Map для быстрого доступа к узлу по id.
const nodeById = new Map();
// во время построения дерева заполняем индекс для быстрого доступа

Дополнительный пример: построение индекса узлов дерева по id.

function indexTree(root, index = new Map()) {
  index.set(root.id, root);
  for (const child of root.children ?? []) {
    indexTree(child, index);
  }
  return index;
}

Смотри, что важно: если нужен путь до узла (например, для breadcrumbs), можно искать узел DFS-обходом и параллельно собирать путь.

function findPath(root, targetId, path = []) {
  path.push(root.id);
  if (root.id === targetId) return [...path];

  for (const child of root.children ?? []) {
    const result = findPath(child, targetId, path);
    if (result) return result;
  }

  path.pop();
  return null;
}

Смотри, что важно: если ты держишь и дерево, и индекс (Map), обновления должны поддерживать оба инварианта:

  • id уникален в дереве;
  • при добавлении/удалении узла обновляй и children, и nodeById;
  • при перемещении узла между родителями не забывай обновить связь в дереве (и, если есть, parentId).

Реальные микро-сценарии

  1. Файловая система в веб-приложении: папки/файлы как дерево.
  2. Каталог категорий + быстрый поиск категории по slug через Map.
  3. Комментарии в треде: дерево ответов и индекс пользователей по id.

Частые ошибки новичков

  • Представлять иерархию плоским списком без ссылок, усложняя обход.
  • Искать элемент по ключу через find в цикле, когда можно держать индекс.
  • Не синхронизировать дерево и хэш-индекс при обновлениях.
  • Путать "структура хранения" и "формат API ответа".

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

Что будет, если изменить входные данные

Если в дереве пропустить проверку на children, рекурсивный обход может упасть на undefined. Если в Map использовать нестабильный ключ (например, объект-ссылку, которая пересоздается), get начнет возвращать undefined. Значит, для надежности нужны четкие инварианты структуры и ключей.

Проверь себя: почему строковый id чаще безопаснее объекта как ключа для долговременного индекса?

Краткий итог

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