Хешування — це популярна техніка, яка використовується для якнайшвидшого зберігання та отримання даних. Основна причина використання хешування полягає в тому, що воно виконує вставку, видалення, пошук та інші операції

Навіщо використовувати хешування?

У хешуванні всі операції, такі як вставка, пошук і видалення, можуть виконуватися за O(1), тобто постійний час. Найгірша часова складність для хешування залишається O(n), але середня часова складність випадку дорівнює O(1).

HashTable

Використовується для створення нової хеш-таблиці.

Синтаксис:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Основні операції з синтаксисом

отримати:

Використовується для пошуку ключа в хеш-таблиці та повернення значення, пов’язаного з цим ключем.

Синтаксис:

// function inside hashtable class to  // access a value using its key get(key) {  const target = this._setKey(key);  return this.table[target]; } 

Вставити:

Використовується для вставки нової пари ключ-значення в хеш-таблицю.

Синтаксис:

// function to insert a value in the  // hash table using setKey function insert(value) {  const index = this._setKey(value);  this.table[index] = value;  this.size++; } 

пошук:

Використовується для пошуку значення.

Синтаксис:

// search a value (by getting its  // key using setKey function) search(value){  const index = this._setKey(value);  if(this.table[index]==value)  console.log('The value is found at index : ',index);  else  console.log('Not found'); } 

Видалити:

Використовується для видалення певної пари ключ-значення з хеш-таблиці.

Синтаксис:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Компоненти хешування в Javascript

1. Хеш-таблиця: Хеш-таблиця є узагальненням масиву. Це надає функціональні можливості, у яких колекція даних зберігається таким чином, що можна легко знайти ці елементи пізніше, якщо потрібно. Це робить пошук елемента дуже ефективним.

2. Хеш-функція: Хеш-функція використовується для перетворення даного ключа в певний індекс слота. він використовується для відображення кожного можливого ключа в унікальний індекс слота. Якщо кожен ключ відображається в унікальному індексі слота, тоді хеш-функція відома як ідеальна хеш-функція. Дуже складно створити ідеальну хеш-функцію, але наша робота як програміста полягає в тому, щоб створити таку хеш-функцію, за допомогою якої буде якомога менше колізій.

Хороша хеш-функція повинна мати такі властивості:

• Ефективно обчислюється.
• Слід рівномірно розподілити ключі (Кожна позиція таблиці однаково ймовірна для кожної).
• Слід звести до мінімуму зіткнення.
• Повинен мати низький коефіцієнт завантаження (кількість елементів у таблиці поділена на розмір таблиці).

3. Усунення зіткнень: Оскільки хеш-функція отримує невелике число для великого ключа, існує ймовірність того, що два ключі дадуть одне й те саме значення. Ситуація, коли щойно вставлений ключ відображається на вже зайнятий слот у хеш-таблиці, називається зіткненням і має бути оброблено за допомогою певної техніки обробки зіткнень. Нижче наведено способи вирішення конфліктів:

• Зв'язування: Ідея полягає в тому, щоб кожна клітинка хеш-таблиці вказувала на пов’язаний список записів, які мають однакове значення хеш-функції. Зв'язування є простим, але вимагає додаткової пам'яті поза таблицею.
• Відкрита адресація: При відкритій адресації всі елементи зберігаються в самій хеш-таблиці. Кожен запис таблиці містить або запис, або NIL. Під час пошуку елемента ми розглядаємо слоти таблиці по черзі, поки не знайдемо потрібний елемент або не стане ясно, що елемента немає в таблиці.

Реалізація з прикладом:

Крок 1: Створіть клас HashTable із початковими властивостями таблиці та розміру.

крок 2: Додайте приватну функцію setKey(key), щоб перетворити ключі на індекси.

крок 3: Додайте функції insert() і get() для додавання та доступу до пар ключ-значення з таблиці.

крок 4: Додайте функцію remove(), щоб видалити ключ із хеш-таблиці.

приклад 1: Припустимо, ми маємо зберегти 5 чисел 100, 87, 86, 12, 25 і 9 у хеш-таблиці. У цьому випадку ми створимо функцію setKey, у якій ми візьмемо значення як аргумент і перетворимо його на індекс хеш-таблиці. Нижче наведено реалізацію.

Javascript

Вихід:

[ 100,  ,  12,  ,  86,  87,  ,  9 ] The value is found at index : 7 Not found [ 100,  ,  [],  ,  86,  87,  ,  9 ] 

У вихідних даних або показує, що таблиця має 1 або 3 послідовні порожні місця/індекси.

приклад 2: Припустімо, ми хочемо зберегти контактні номери сім’ї з 5 членів у хеш-таблиці. Для цього ми створимо хеш-таблицю розміром 10 і збережемо контактні дані. Індекс буде встановлено за допомогою приватної функції setKey, яка перетворить останню цифру контактного номера в індекс хеш-таблиці.

Javascript

Вихід:

[ ,  92752521,  98747512,  94755523,  ,  98754525,  ,  98556529 ] The contact number is found at index : 1 Contact Number not found [ ,  [],  98747512,  94755523,  ,  98754525,  ,  98556529 ] 

У вихідних даних або показує, що таблиця має 1 або 3 послідовні порожні місця/індекси.