Хеш-таблица – это структура данных, используемая для быстрого хранения и извлечения данных. Он работает с использованием хеш-функции для сопоставления ключей сохраняемых элементов с определенными индексами в массиве, что позволяет получать доступ к данным за постоянное время, независимо от размера набора данных. .
В хеш-таблице данные хранятся в виде пар ключ-значение. Когда вы хотите добавить или извлечь элемент из таблицы, вы предоставляете ключ, а хеш-функция сопоставляет ключ с определенным индексом в массиве. Затем значение сохраняется в этом индексе или извлекается из этого индекса, в зависимости от обстоятельств.
Хеш-таблицы очень эффективны для хранения и извлечения данных и широко используются в различных приложениях, таких как базы данных, кэши и хэш-карты в языках программирования. Они предлагают быстрый поиск, вставку и удаление, что делает их популярным выбором для реализации ассоциативных массивов, наборов и карт.
Эта реализация имеет фиксированный размер хеш-таблицы, который указывается при создании объекта HashTable. Он имеет метод hash(), который принимает ключ в качестве входных данных и возвращает индекс в массиве, где значение должно быть сохранено или извлечено. Методы insert(), get() и remove() используют метод hash() для поиска индекса, а затем выполняют соответствующую операцию над значением, хранящимся в этом индексе.
class HashTable {
constructor(size) {
this.size = size;
this.buckets = new Array(size);
}
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size;
}
insert(key, value) {
let index = this.hash(key);
if (!this.buckets[index]) {
this.buckets[index] = [];
}
this.buckets[index].push({key, value});
}
get(key) {
let index = this.hash(key);
if (!this.buckets[index]) return null;
for (let i = 0; i < this.buckets[index].length; i++) {
if (this.buckets[index][i].key === key) {
return this.buckets[index][i].value;
}
}
return null;
}
remove(key) {
let index = this.hash(key);
if (!this.buckets[index]) return null;
for (let i = 0; i < this.buckets[index].length; i++) {
if (this.buckets[index][i].key === key) {
this.buckets[index].splice(i, 1);
return;
}
}
}
}
const hashTable = new HashTable(10);
hashTable.insert('abc', 123);
hashTable.insert('def', 456);
console.log(hashTable.get('abc')); // 123
console.log(hashTable.get('def')); // 456
hashTable.remove('abc');
console.log(hashTable.get('abc')); // null
Хэш-функция
Хеш-функция — это функция, которая принимает входные данные (называемые «ключом») и возвращает выходные данные фиксированного размера (называемые «хэш-значением» или «хэш-кодом»), которые вычисляются на основе ключа. Основная цель хэш-функции состоит в том, чтобы взять большие входные данные и сопоставить их с меньшими выходными данными таким образом, чтобы было относительно легко найти исходный ключ на основе хеш-значения, но невозможно сгенерировать исходный ключ на основе хеш-значения. только по хэш-значению.
Основные свойства хорошей хеш-функции:
- Эффективность вычислений: хэш-функция должна быть быстрой для вычислений и не должна требовать много ресурсов.
- Детерминированный: один и тот же ввод всегда должен давать один и тот же вывод, чтобы можно было легко найти один и тот же ключ, используя одно и то же значение хеш-функции.
- Равномерное распределение: выходные данные хеш-функции должны быть равномерно распределены по диапазону возможных хеш-значений, чтобы ключи распределялись равномерно по хеш-таблице.
- Устойчивость к коллизиям: хеш-функция должна минимизировать вероятность того, что два разных ключа будут иметь одинаковое хэш-значение, также известное как коллизия.
Хеш-функции широко используются в различных приложениях, таких как хранение и поиск данных, криптография и интеллектуальный анализ данных. В контексте хеш-таблиц хорошая хэш-функция должна уметь сопоставлять ключи сохраняемых элементов с уникальными индексами в массиве хэш-таблицы, чтобы каждый ключ можно было легко вставлять и извлекать.
Существует множество различных хэш-функций, которые можно использовать, и выбор хэш-функции зависит от конкретных требований приложения. Некоторые распространенные хэш-функции включают хэш по модулю, универсальный хеш и криптографический хэш.
Вот еще несколько примеров хеш-функций, которые можно использовать в хэш-таблице:
Хэш по модулю
Эта хеш-функция использует оператор по модулю для сопоставления ключа с индексом в массиве хэш-таблицы. Например:
function moduloHash(key, size) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % size;
}
Криптографический хэш
Это тип хеш-функции, который использует случайно сгенерированную хеш-функцию для каждого ключа, что делает его более устойчивым к атакам столкновений. Вот пример универсальной хэш-функции:
const crypto = require('crypto');
function cryptographicHash(key) {
return crypto.createHash('sha1').update(key).digest('hex');
}
Хеш-таблица с динамическим размером
Хеш-таблицу можно реализовать с помощью массива с динамическим изменением размера, что означает, что размер массива может меняться в зависимости от количества элементов в таблице.
Одним из распространенных способов реализации хеш-таблицы динамического размера является использование коэффициента загрузки, который является мерой того, насколько заполнена хэш-таблица. Когда количество элементов в хеш-таблице превышает определенный порог (определяемый коэффициентом загрузки), размер массива изменяется до большего размера, чтобы освободить место для большего количества элементов. Точно так же, когда количество элементов падает ниже определенного порога, размер массива уменьшается до меньшего размера для экономии места.
Вот пример того, как хэш-таблица динамического размера может быть реализована в JavaScript с использованием синтаксиса ES6:
class HashTable {
constructor() {
this.size = 8;
this.buckets = new Array(this.size);
this.numElements = 0;
}
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size;
}
insert(key, value) {
this.numElements++;
let index = this.hash(key);
if (!this.buckets[index]) {
this.buckets[index] = [];
}
this.buckets[index].push({ key, value });
if (this.numElements > this.size * 0.75) {
this.resize(this.size * 2);
}
}
get(key) {
let index = this.hash(key);
if (!this.buckets[index]) return null;
for (let i = 0; i < this.buckets[index].length; i++) {
if (this.buckets[index][i].key === key) {
return this.buckets[index][i].value;
}
}
return null;
}
remove(key) {
this.numElements--;
let index = this.hash(key);
if (!this.buckets[index]) return null;
for (let i = 0; i < this.buckets[index].length; i++) {
if (this.buckets[index][i].key === key) {
this.buckets[index].splice(i, 1);
if (this.numElements < this.size * 0.25) {
this.resize(this.size / 2);
}
return;
}
}
}
resize(newSize) {
let oldBuckets = this.buckets;
this.size = newSize;
this.buckets = new Array(this.size);
this.numElements = 0;
for (let i = 0; i < oldBuckets.length; i++) {
if (oldBuckets[i]) {
for (let j = 0; j < oldBuckets[i].length; j++) {
this.insert(oldBuckets[i][j].key, oldBuckets[i][j].value);
}
}
}
}
}
Встроенные реализации хэш-таблицы
В JavaScript есть несколько встроенных классов, которые используют хеш-таблицы для эффективного хранения и извлечения данных. Вот некоторые примеры:
- Map. Класс Map представляет собой набор пар ключ-значение, которые можно повторять в том порядке, в котором они были добавлены. Он использует хэш-таблицу для хранения данных и обеспечивает эффективное время вставки, удаления и поиска O(1).
- Set. Класс Set представляет собой набор уникальных значений, которые можно повторять в том порядке, в котором они были добавлены. Он также использует хеш-таблицу для хранения данных и обеспечивает эффективное время вставки, удаления и поиска O(1).
Эти встроенные классы обеспечивают удобный способ использования хэш-таблиц в JavaScript и могут быть очень полезны для эффективного хранения данных и управления ими.
В целом, хеш-таблицы представляют собой мощную и эффективную структуру данных, которая может значительно повысить производительность многих приложений. Если вы работаете над проектом, в котором вам необходимо эффективно хранить и извлекать данные, рассмотрите возможность использования хэш-таблицы, чтобы помочь вам достичь своих целей.
