Какой тип данных может исполнять роль хеш-таблиц в JavaScript?

Хеш-таблицы в JavaScript

В JavaScript роль хеш-таблиц (hash tables) выполняют несколько типов данных. Хеш-таблица — это структура данных, которая хранит пары "ключ-значение" и обеспечивает быстрый поиск по ключу за O(1) время.

Основные типы для хеш-таблиц

1. Object — классический вариант

// Использование Object как хеш-таблица
const users = {
  'user1': { name: 'John', age: 30 },
  'user2': { name: 'Jane', age: 25 },
  'user3': { name: 'Bob', age: 35 }
};

// Быстрый поиск за O(1)
console.log(users['user1']); // { name: 'John', age: 30 }
console.log(users.user2); // { name: 'Jane', age: 25 }

// Добавление
users['user4'] = { name: 'Alice', age: 28 };

// Удаление
delete users['user3'];

// Проверка наличия
console.log('user1' in users); // true

2. Map — современный стандарт

// Map с любыми типами ключей
const cache = new Map();

// Добавление
cache.set('key1', 'value1');
cache.set(42, 'numeric key');
cache.set({ id: 1 }, 'object key');

// Быстрый поиск за O(1)
console.log(cache.get('key1')); // 'value1'
console.log(cache.get(42)); // 'numeric key'

// Проверка
console.log(cache.has('key1')); // true

// Удаление
cache.delete('key1');

// Размер
console.log(cache.size); // 2

// Итерация
for (const [key, value] of cache) {
  console.log(`${key}: ${value}`);
}

3. WeakMap — для памяти (слабые ссылки)

// WeakMap - ключи должны быть объектами
const cache = new WeakMap();

const obj1 = { id: 1 };
const obj2 = { id: 2 };

cache.set(obj1, 'data for obj1');
cache.set(obj2, 'data for obj2');

console.log(cache.get(obj1)); // 'data for obj1'

// Если obj1 удален из памяти, запись в WeakMap автоматически удалится
// Полезно для предотвращения утечек памяти

Сравнение Object, Map и WeakMap

// Object
const obj = {};
obj['key'] = 'value';
obj[123] = 'number'; // Преобразуется в строку '123'
console.log(obj[123]); // 'number' - но ключ является строкой!
console.log(Object.keys(obj)); // ['key', '123']

// Map
const map = new Map();
map.set('key', 'value');
map.set(123, 'number'); // Числовой ключ остаётся числом
console.log(map.get(123)); // 'number' - точный тип
console.log([...map.keys()]); // ['key', 123]

// Различия в производительности
console.time('Object');
const obj2 = {};
for (let i = 0; i < 1000000; i++) obj2[i] = i;
console.timeEnd('Object'); // ~5ms

console.time('Map');
const map2 = new Map();
for (let i = 0; i < 1000000; i++) map2.set(i, i);
console.timeEnd('Map'); // ~15ms (немного медленнее, но незначительно)

Практические примеры

Пример 1: Кеш результатов функции (Memoization)

const fibonacci = (() => {
  const cache = {}; // Или new Map()
  
  return (n) => {
    if (n in cache) {
      return cache[n];
    }
    
    if (n <= 1) return n;
    
    const result = fibonacci(n - 1) + fibonacci(n - 2);
    cache[n] = result;
    return result;
  };
})();

console.log(fibonacci(10)); // Быстро благодаря кешированию

Пример 2: Счётчик повторений

function countCharacters(str) {
  const counts = new Map(); // или {}
  
  for (const char of str) {
    counts.set(char, (counts.get(char) || 0) + 1);
  }
  
  return counts;
}

const result = countCharacters('aabbcc');
console.log(result); // Map { 'a' => 2, 'b' => 2, 'c' => 2 }

Пример 3: Индекс пользователей по ID

const users = [
  { id: 1, name: 'John' },
  { id: 2, name: 'Jane' },
  { id: 3, name: 'Bob' }
];

// Создание индекса
const userIndex = {};
for (const user of users) {
  userIndex[user.id] = user;
}

// Быстрый поиск
console.log(userIndex[2]); // { id: 2, name: 'Jane' }

// Или с Map
const userIndexMap = new Map(users.map(u => [u.id, u]));
console.log(userIndexMap.get(2)); // { id: 2, name: 'Jane' }

Пример 4: Граф соседей

// Представление графа как хеш-таблицы
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'D'],
  'D': ['B', 'C']
};

// Быстрый поиск соседей
console.log(graph['A']); // ['B', 'C']

// DFS обход
function dfs(node, visited = new Set()) {
  visited.add(node);
  console.log(node);
  
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited);
    }
  }
}

dfs('A'); // A B D C

Пример 5: Проверка уникальности элементов

function hasUniqueChars(str) {
  const seen = {}; // Или new Set()
  
  for (const char of str) {
    if (seen[char]) {
      return false;
    }
    seen[char] = true;
  }
  
  return true;
}

console.log(hasUniqueChars('abc')); // true
console.log(hasUniqueChars('aba')); // false

// Ещё проще с Set
function hasUniqueCharsSet(str) {
  return new Set(str).size === str.length;
}

console.log(hasUniqueCharsSet('abc')); // true

Когда использовать какой тип

Object:

• Когда ключи всегда строки
• Для простых конфигураций
• Когда нужны методы объекта (Object.keys, Object.entries)
• Для совместимости со старым кодом

Map:

• Когда нужны нестроковые ключи (числа, объекты)
• Для больших данных (лучше производительность на добавление/удаление)
• Когда нужна итерация в порядке добавления
• Когда нужно различать 1 и '1' как разные ключи

WeakMap:

• Для приватных данных объектов
• Когда нужно избежать утечек памяти
• Для кеша привязанного к жизненному циклу объекта

Set/WeakSet:

• Для хранения уникальных значений
• Для быстрой проверки наличия элемента
• Когда нужны методы has(), add(), delete()

Производительность O(1)

// Hash table гарантирует O(1) для:
// - Вставки: obj[key] = value
// - Удаления: delete obj[key]
// - Поиска: obj[key]

const start = performance.now();
const map = {};
for (let i = 0; i < 1000000; i++) {
  map[i] = Math.random();
}
for (let i = 0; i < 1000000; i++) {
  const val = map[i];
}
const end = performance.now();
console.log(`Time: ${end - start}ms`); // ~100ms для 2M операций

Вывод

В JavaScript роль хеш-таблиц выполняют:

1. Object — классический вариант, ключи всегда строки
2. Map — современный стандарт, ключи любого типа
3. WeakMap — для слабых ссылок и предотвращения утечек памяти
4. Set/WeakSet — для уникальных значений

Для обычных задач Object достаточно. Для сложных сценариев (нестроковые ключи, большие данные) лучше использовать Map.