Как работает HashMap?

Как работает HashMap

HashMap - это основная структура данных для эффективного хранения пар ключ-значение. Расскажу как она работает, в том числе применительно к JavaScript.

1. Основной принцип

HashMap использует хеш-функцию для преобразования ключа в индекс массива. Это позволяет найти значение за O(1) в среднем случае вместо O(n).

// Упрощенная реализация HashMap
class SimpleHashMap {
  constructor(capacity = 16) {
    this.capacity = capacity;
    this.size = 0;
    this.table = new Array(capacity);
  }
  
  // Хеш-функция: преобразует ключ в индекс
  hash(key) {
    let hash = 0;
    const str = String(key);
    
    for (let i = 0; i < str.length; i++) {
      hash = ((hash << 5) - hash) + str.charCodeAt(i);
      hash = hash & hash; // convert to 32bit integer
    }
    
    return Math.abs(hash) % this.capacity;
  }
  
  // Вставить пару ключ-значение
  set(key, value) {
    const index = this.hash(key);
    
    if (!this.table[index]) {
      this.table[index] = [];
    }
    
    // Проверить, есть ли уже такой ключ
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    
    // Добавить новую пару
    this.table[index].push([key, value]);
    this.size++;
  }
  
  // Получить значение по ключу
  get(key) {
    const index = this.hash(key);
    
    if (this.table[index]) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i][0] === key) {
          return this.table[index][i][1];
        }
      }
    }
    
    return undefined;
  }
  
  // Удалить по ключу
  delete(key) {
    const index = this.hash(key);
    
    if (this.table[index]) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index].splice(i, 1);
          this.size--;
          return true;
        }
      }
    }
    
    return false;
  }
}

// Использование
const map = new SimpleHashMap();
map.set('name', 'Alice');
map.set('age', 30);
console.log(map.get('name')); // Alice
console.log(map.size); // 2

2. Проблема коллизий (Hash Collisions)

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

// СПОСОБ 1: Chaining (Цепочки)
// Несколько элементов хранятся в одной ячейке в виде связного списка
// Преимущества: простая реализация, хороша при малом количестве коллизий
// Недостатки: при большом количестве коллизий поиск становится медленнее

class ChainingHashMap {
  constructor(capacity = 16) {
    this.table = Array(capacity).fill(null).map(() => []);
    this.capacity = capacity;
  }
  
  hash(key) {
    return key.length % this.capacity;
  }
  
  set(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    
    // Обновить, если ключ уже существует
    for (let i = 0; i < chain.length; i++) {
      if (chain[i][0] === key) {
        chain[i][1] = value;
        return;
      }
    }
    
    // Добавить новый элемент
    chain.push([key, value]);
  }
  
  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    
    for (let [k, v] of chain) {
      if (k === key) return v;
    }
    
    return undefined;
  }
}

3. Load Factor и Resizing

Когда HashMap становится слишком заполненной, она расширяется.

// Load Factor = количество элементов / capacity
// Типично resize при load factor > 0.75

class DynamicHashMap {
  constructor(capacity = 16) {
    this.capacity = capacity;
    this.size = 0;
    this.table = Array(capacity).fill(null).map(() => []);
    this.loadFactorThreshold = 0.75;
  }
  
  set(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    
    // Обновить или добавить
    for (let i = 0; i < chain.length; i++) {
      if (chain[i][0] === key) {
        chain[i][1] = value;
        return;
      }
    }
    
    chain.push([key, value]);
    this.size++;
    
    // Проверить, нужен ли resize
    const loadFactor = this.size / this.capacity;
    if (loadFactor > this.loadFactorThreshold) {
      this.resize();
    }
  }
  
  resize() {
    const oldTable = this.table;
    this.capacity *= 2;
    this.table = Array(this.capacity).fill(null).map(() => []);
    this.size = 0;
    
    // Перехешировать все элементы
    for (let chain of oldTable) {
      for (let [key, value] of chain) {
        this.set(key, value);
      }
    }
  }
  
  hash(key) {
    let hash = 0;
    const str = String(key);
    
    for (let char of str) {
      hash = (hash << 5) - hash + char.charCodeAt(0);
      hash = hash & hash;
    }
    
    return Math.abs(hash) % this.capacity;
  }
}

4. В JavaScript: Map и Object

В JavaScript встроены оптимизированные структуры:

// OPTION 1: Object (хеш-таблица, но только строковые ключи)
const obj = {};
obj['name'] = 'Alice';
obj['age'] = 30;

// Проблема: все ключи становятся строками
obj[1] === obj['1']; // true!

// OPTION 2: Map (истинная HashMap, работает с любыми типами ключей)
const map = new Map();
map.set('name', 'Alice');
map.set(1, 'number key');
map.set(true, 'boolean key');
map.set({}, 'object key');

// Правильно различает типы
map.get('1') !== map.get(1); // true

// Методы Map
map.set(key, value);
map.get(key);
map.has(key);
map.delete(key);
map.clear();

// Итерация
for (let [key, value] of map) {
  console.log(key, value);
}

map.forEach((value, key) => {
  console.log(key, value);
});

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

5. Временная сложность

const complexities = {
  // Лучший и средний случай (без коллизий)
  'set': 'O(1)',
  'get': 'O(1)',
  'delete': 'O(1)',
  
  // Худший случай (много коллизий)
  'set_worst': 'O(n)',
  'get_worst': 'O(n)',
  'delete_worst': 'O(n)',
  
  // Resize операция
  'resize': 'O(n)',
};

6. Практический пример: Кеш

class Cache {
  constructor(maxSize = 100) {
    this.map = new Map();
    this.maxSize = maxSize;
  }
  
  set(key, value) {
    // Если ключ уже существует, удалим его (для LRU)
    if (this.map.has(key)) {
      this.map.delete(key);
    }
    
    this.map.set(key, value);
    
    // Если кеш переполнен, удалим самый старый элемент
    if (this.map.size > this.maxSize) {
      const firstKey = this.map.keys().next().value;
      this.map.delete(firstKey);
    }
  }
  
  get(key) {
    if (!this.map.has(key)) return null;
    
    // Переместить в конец (самый свежий)
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    
    return value;
  }
}

Ключевые моменты

• HashMap - это хеш-таблица, основанная на хеш-функции
• Коллизии разрешаются через chaining или open addressing
• Load factor определяет, когда нужен resize
• В JS используй Map вместо Object для HashMap
• Временная сложность O(1) в среднем, O(n) в худшем
• HashMap оптимальна для частых поисков и вставок