hash

Hash Tables

Наши соц. сети: instagram, fb, tg

Хэш-таблица

Существует много способов хранения данных в программировании, один из которых известен как хеш-таблица. Javascript имеет свои собственные варианты хэширования, такие как новая функциональность Map, которая была введена в ECMAScript 2015 или ES6, которая создает ассоциативный массив и запоминает порядок вставки. В отличие от типичного массива, в хеш-таблице ключи передаются через функцию хеширования, а затем числовое значение присваивается данным и помещается в это место в таблице, которое устанавливается внутри так называемого сегмента.Сегмент, в который он вставлен, может содержать только один ассоциативный массив за раз до того, как возникнет коллизия (равенство значений хеш-функции на двух различных блоках данных). Есть несколько способов обработки коллизии.

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

functions

Предположим, что в сегменте 007 есть ассоциативный массив, если второй массив введен из-за того, что выходные данные хеш-функции совпадают с первой. Он станет многомерным массивом, который может вместить другую пару, поэтому теперь в сегменте 007 будут установлены 2 ассоциативных массива в одном и том же сегменте. Этот метод известен как открытое хеширование. Техника закрытого хеширования была бы чем-то вроде линейного зондирования. При линейном зондировании, если сегмент заполнен, будет использоваться следующая для хранения информации. Если используется последовательный, он продолжит работать, пока не найдет открытый сегмент и не поместит его туда.

Давайте поговорим об открытом и закрытом хешировании. Это называется открытым хешированием, потому что при раздельном связывании появляется список, и хеш-таблица становится доступной не только для сегментов. Связанный список или аналогичная структура помещается в сегменты, поэтому в случае коллизии он может просто указывать на следующий узел или индекс. При закрытом хешировании таблица всегда остается неповрежденной, и единственная информация, вводимая в сегменты, - это ассоциативный массив, и нет необходимости вводить какие-либо другие типы данных. Так, каковы хеш-функции, которые определяют, какой сегмент используется? Это полностью зависит от кодера, пишущего функцию. Хеш-функции могут быть простыми или сложными, но по мере расширения таблицы вы хотите убедиться, что у вас будет как можно меньше коллизий.

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

"eggs" => "1 dozen"

Но по какой-то странной причине вы хотите сделать это с нуля вместо того, чтобы использовать один из ранее существующих методов для хранения этого. Как бы вы это сделали? Для этого мы будем использовать массив в качестве таблицы, в которую мы вставляем данные. Мы передадим строку «eggs» через функцию хеширования, и на выходе будет индекс, где будет храниться этот ключ. Хеш-функция, когда ключ дается несколько раз, всегда должна указывать на одно и то же место в массиве. Поэтому, если «eggs» хранится в индексе 1, в следующий раз, когда я введу яйца в хеш-функцию, я должен получить тот же индекс. Это называется «детерминирование» (при одинаковых данных, ты будешь получать один и тот же результат). Если вы не получите то же самое значение обратно, тогда что-то пошло не так с хэш-функцией, потому что выходные данные определяются (детерминированными) входными данными. Так как же выглядит простая хеш-функция? Опять же, хеш-функции различаются по сложности, и есть много разных штуковин, которые вы можете включить в хеш-функцию. Имейте в виду, вы хотите, чтобы в выводе были какие-то изменения, чтобы разные сегменты выбирались чаще. Вот очень простая хеш-функция.

class HashTable {
constructor(size=10) {
this.map = new Array(size);
}
_hash(key) {
let total = 0;
for (let i = 0; i < key.length; i++) {
const value = key[i].charCodeAt(0) - 96;
total += total + value;
}
return total % this.map.length;
}
}
const hashTable = new HashTable();
console.log(hashTable._hash("eggs")); // 1
console.log(hashTable._hash("eggs")); // 1
console.log(hashTable._hash("bacon")); // 6
console.log(hashTable._hash("bacon")); // 6

Эта функция будет использоваться для хеширования наших ключей и присвоения им номера. Я назначил его классу с именем HashTable, чтобы мы могли использовать его снова и снова. Подчеркивание перед хешем (ключом) означает, что это приватная функция. Как вы можете видеть, если “eggs” является входным параметром, то функция дает тот же результат; то же самое для бекона. Это хороший признак того, что хеш-функция работает должным образом. Итак, теперь, когда хеш-функция работает, пришло время приступить к настройке пар ключ значения, чтобы мы могли запомнить, сколько нам нужно для нашего рецепта. Метод будет называться set, а параметры будут key и value. Это отобразит значение в сегмент, которая назначена ключу, и будет сохранена там для последующего извлечения. Например, когда мы вставляем яйца в качестве ключа со значением dozen, это должно привести нас к значению 1, которое является индексом массива, в котором находится сегмент. Итак, здесь идет метод set для таблицы и ее результаты.

set(key, value) {
let index;
if (!this.map[index]) {
this.map[index] = [];
}
this.map[index].push([key, value]);
}

Для метода set в hashTable мы передаем ключ и значение. Функция принимает ключевой параметр и передает его через функцию хеширования, которую мы создали ранее. Это даст индекс = 1, и если нет массива с индексом 1, то он установит его. Помните, что это один из способов. Мы используем отдельную цепочку вместо линейного зондирования, поэтому, если массив уже существует в этом месте, мы просто создаем новый массив и кликаем на него, чтобы создать вложенный массив в этом индексе. Когда hashTable регистрируется в консоли после установки [“eggs”, “1 dozen”], это будет выглядеть следующим образом.

console.log(hashTable); // [[],["eggs", "1 dozen"], [], [], [], [], [], [], [], []]

Теперь я знаю, о чем ты думаешь. Кому в этом мире захочется создавать таблицу и заполнить ее массивами, если я могу просто сохранить пару ключ-значение в собственном объекте JavaScript? Давайте установим еще пару объектов и посмотрим, насколько это может быть верным решением для извлечения данных при работе с большим количеством пар.

class HashTable {

...

print() {
this.map.forEach((el, index) => console.log(index, el));
}
}

 

const hasTable = new HashTable();

 

hasTable.set('eggs', '1 dozen');
hasTable.set('baccon', '2 packs');
hasTable.set('cherry coke zero', '3 12-packs');
hasTable.set('hor sauce', '1 bottle');

 

hasTable.print();

 

Результат:

/**

1 [ ['eggs', '1 dozen'] ]

6 [ ['baccon', '2 packs'] ]

7 [ ['cherry coke zero', '3 12-packs'] ]

[ ['hor sauce', '1 bottle'] ]

*/

Теперь, когда здесь есть несколько объектов, мы видим, что по большей части - каждая пара ключ-значение имеет свой собственный сегмент; яйца находятся в сегменте с индексом 1, бекон находится в сегменте с индексом 6, и мы столкнулись с нашим первым индексом 7, где проживают как Coca-Cola Zero Cherry (жуть), так и острый соус. В этой конкретной статье мы решаем эту проблему путем добавления в существующий сегмент (отдельная цепочка). Теперь, когда мы проиндексировали все эти элементы, единственное, что нам нужно сделать для извлечения ассоциативного массива, - это ввести ключ, и мы точно знаем, какой сегмент искать, потому что он будет таким же, как при его установке! Итак, давайте получим значение ассоциативного массива на основе ключа.

get(key) {
let index = this._hash(key);
if (this.map[index]) {
for (let i = 0; i < this.map[index].length; i++) {
if (this.map[index][i][1] === key) {

 

return this.keyMap[index][i][1];
}
}
}

 

return undefined;
}

Это последний метод, который нам понадобится для класса хэш-таблиц в этой статье. Я знаю, что информации достаточно много, но давайте быстро пройдемся по этому вопросу, чтобы понять, как работает метод get. Когда передается строка «eggs» в качестве параметра, что происходит? Ну, для индекса установлено значение, данное нашей хеш-функцией, мы знаем, что для яиц это 1, затем, если индекс находится в пределах нашего диапазона, выполнить цикл for. Цикл for находит массив по нашему заданному индексу, поэтому он будет

for (let i = 0; i < this.map[1][i].length; i++) {}

Мы находимся во вложенном массиве, где конкретный массив является определенным индексом, для яиц он имеет только один элемент, вложенный внутрь корзины. Условные говоря, если первый индексированный элемент, который является нашим ключом, совпадает с переданным параметром в метод get, возвращает второй индекс этого массива, который является его значением.

if (this.map[1][0][0] === "eggs") {
return this.map[1][0][1] // which is "1 dozen"
}

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

Основным преимуществом хеш-таблиц перед массивами является значительная производительность. Конечно остаются некоторые проблемы с коллизиями, но в большинстве случаев их можно решить хорошей хеш-функцией. Среднее время поиска, вставки и удаления составляет O (1) или постоянное время, наихудшие сценарии - O (n) или линейное время, что было бы в случае, если все введенные вами пары были выгружены в один и тот же сегмент, но если вы настроите достаточно хорошую таблицу и хеш-функцию, вы не должны столкнуться с худшим случаем. Итак, у вас есть новый способ сохранить список покупок в вашей собственной хэш-таблице.

Надеюсь тебе было полезно, вот ещё некоторый материал по структурам данных.