Структуры данных. Хеш-таблицы

16 декабря 2023 г.

Основная информация

Это краткий дополненный конспект части о хэш-таблицах в книге Гид по Computer Science, Вильям Спрингер.

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

Первая часть хеш-таблицы — это хеш-функция; она преобразует ключ элемента, который помещается в хеш – строку или число фиксированной длины и приводит его к индексу массива. Этому ключу соответствует определенное место в таблице.

Некоторые алгоритмы хеширования:

• CRC32,
• MD5,
• SHA

Допускается хранить только один экземпляр каждого элемента;

В JavaScript c 2015 года добавлен Map()— хэш-карта. Она обеспечивает функциональность ключа/значения. В хэш карте в качестве ключей можно использовать любой тип данных , а не только строки и целые числа, как в хэш-таблицах.

В свою очередь, хэш-карты нельзя преобразовать в JSON.

Решение коллизий

1) Метод цепочек - каждая ячейка рассматривается, как группа объектов, представленных в виде связного списка (который нужно пройти, чтобы найти правильное значение).

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

2) Открытая адресация - можно просмотреть близлежащие ячейки, найти свободную и поместить новое значение туда. В этом случае таблица имеет фиксированный максимальный размер. Как только все ячейки будут заполнены, в таблицу нельзя будет вставить новые элементы.

Более подробно про эти способы можно прочитать, например, в этой статье.

Применение

Используют

Когда нужен прямой доступ к неотсортированным данным на основе ключа и при этом существует быстродействующая функция генерации ключа для каждого объекта (при условии, что сами объекты не являются такими ключами).

Например, для индексации больших объемов информации (баз данных), авторизации, поиска или кэширования, реализации неупорядоченных множеств.

Не используют

• когда нужно сохранять порядок сортировки
• элементы не распределены (то есть много элементов хешируется в малое количество ячеек),
• часто необходим доступ к блокам последовательно размещенных элементов.

Реализация на JavaScript

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

Чем больше места выделено под таблицу, тем меньше вероятность коллизий. Если нет коллизий - сохранение или извлечение элемента занимает O(1) времени. Если же они есть то наихудшее время выполнения этих операций -O(n).

Пример реализации взят из этой статьи.

1// для размера хеш-таблицы часто используются простые числа (которые делятся только на единицу и на себя). Считается, что при этом возникает меньше коллизий.
2const hashTableSize = 32;
3
4class HashTable {
5	constructor() {
6		this.table = new Array(hashTableSize);
7	}
8
9	// Хэш-функция
10	hashFunction(key) {
11		let hash = Array.from(key).reduce((sum, key) => {
12			// Метод charCodeAt() возвращает числовое значение Юникода для символа по указанному индексу (за исключением кодовых точек Юникода, больших 0x10000).
13			return sum + key.charCodeAt(0);
14		}, 0);
15		return hash % hashTableSize;
16	}
17
18	// добавление новой пары ключ-значение
19	set(key, value) {
20		// вычисляем хеш для ключа
21		let memoryLocation = this.hashFunction(key);
22		// если для данного хеша еще нет списка, создаем
23		if (!this.table[memoryLocation]) {
24			this.table[memoryLocation] = [];
25		}
26
27		// проверяем, не добавлен ли ключ ранее
28		let node = this.table[memoryLocation].find((array) => array[0] === key);
29
30		if (node) {
31			node[1] = value; // обновляем значение для ключа
32		} else {
33			this.table[memoryLocation].push([key, value]); // добавляем новый элемент в конец списка
34		}
35	}
36
37	// поиск значения по ключу
38	get(key) {
39		let memoryLocation = this.hashFunction(key);
40		if (!this.table[memoryLocation]) return null;
41
42		return this.table[memoryLocation].find((x) => x[0] === key)[1];
43	}
44}

Пример с использованием метода цепочек на основе связного списка.