Hash-таблицы (hash table)

Hash-таблица — неупорядоченная структура данных для быстрого доступа к значению по ключу.

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

Плюсы

• Эффективно работает с неизменяемыми объектами
• Хэш-функция дает (должна) равномерное распределение

Структура

• Словарь для хранения ключей
• Хэш-функция (преобразует ключ в уникальный хэш)
• Получение значения по хэшу
• Удаление значения по хэшу

Код

class HashTable { 
  constructor() { 
    this.memory = []
  } 
  
  hashKey(key) { 
    var hash = 0
    for (var index = 0; index < key.length; index++) { 
      // базовая генерация hash
      var code = key.charCodeAt(index)
      hash = ((hash << 5) - hash) + code | 0
    } 
    return hash; 
  }
  
  get(key) { 
    var address = this.hashKey(key)
    return this.memory[address]
  }

  remove(key) { 
    var address = this.hashKey(key)

    if (this.memory[address]) { 
        delete this.memory[address]
    }
  }
}

Пример hash-функций:

function hash(string, max) { 
  let hash = 0 
  
  for (let i = 0; i < string.length; i++) { 
    hash += string.charCodeAt(i) 
  } 
  
  return hash % max 
}

Проблемы

Коллизии

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

Потребление памяти

При большом размере таблица будет использоваться много памяти. При маленьком размере в таблице будет большой коэффициент заполнения, медленный поиск и удаление

Задачи

• https://leetcode.com/problems/single-number (решить за O(1) по памяти)
• https://leetcode.com/problems/two-sum
• https://leetcode.com/problems/4sum
• https://leetcode.com/problems/group-anagrams
• https://leetcode.com/problems/valid-anagram
• https://leetcode.com/problems/find-all-anagrams-in-a-string

Видео

• https://www.youtube.com/watch?v=0UX4MIfOMEs