261 lines
9.1 KiB
Markdown
261 lines
9.1 KiB
Markdown
---
|
||
id: 587d825b367417b2b2512c8e
|
||
title: Створення геш-таблиці
|
||
challengeType: 1
|
||
forumTopicId: 301627
|
||
dashedName: create-a-hash-table
|
||
---
|
||
|
||
# --description--
|
||
|
||
У даному завданні ми вивчимо геш-таблиці. Геш-таблицю використовують для реалізації асоціативних масивів або для зберігання пар (ключ, значення), як-от об'єкти та карти, які ми нещодавно вивчали. Як приклад, ми можемо внести об'єкт JavaScript у вигляді геш-таблиці (практична реалізація чого залежатиме від середовища запуску). Геш-таблиці функціонують таким чином: вони приймають вхідний ключ й конвертують його у числове значення визначеним шляхом. Згодом це числове значення використовується як дійсний ключ, за яким зберігається числове значення, що асоціюється з цим ключем. Якщо ви згодом захочете отримати доступ до того самого ключа ще раз, геш-функція опрацює ключ і поверне те саме числове значення, за допомогою якого можна знайти асоціативне значення. Тому цей процес є ефективним і час його виконання становить в середньому 0(1).
|
||
|
||
Геш-таблиці можна ще реалізувати у вигляді масивів, і тоді вони вираховуватимуть індекси за допомогою геш-функцій відповідно до заданого діапазону. У такому випадку визначення розміру масиву і сама геш-функція однаково важливі. А якщо геш-функція містить однакові значення для двох різних ключів? Що тоді? Такий випадок називається колізією (зіткненням). Як варіант, в такій ситуації можна зберегти обидві пари ключів-значень під одним індексом. Далі при пошуку кожної з них треба повторно переглянути всі елементи, щоб знайти потрібний ключ. Хороша геш-функція мінімізує колізії, щоб зберегти ефективний час пошуку.
|
||
|
||
Поки що ми не будемо детально розглядати гешування чи реалізацію геш-таблиць, але спробуємо зрозуміти загальний принцип їх роботи.
|
||
|
||
# --instructions--
|
||
|
||
Створімо основні функції геш-таблиці. Ми створили для вас просту геш-функцію. Якщо ви задасте дані рядка для функції `hash`, то отримаєте геш-значення, яке можна використати як ключ для зберігання. Збережіть елементи, що базуються на цьому геш-значенні, в об'єкті під назвою `this.collection`. Створіть такі три методи: `add`, `remove`, та `lookup`. Перший повинен отримати пару ключ-значення, щоб додати їх до геш-таблиці. Другий метод повинен видалити пару ключ-значення після перегляду ключа. Третій метод повинен прийняти ключ та повернути пов'язане з ним значення або `null`, якщо ключ не був знайдений.
|
||
|
||
Обов'язково напишіть код з врахуванням колізій!
|
||
|
||
** Зауважте: ** Тестування методу `remove` не буде вважатися завершеним, допоки методи `add` та `lookup` не будуть реалізовані правильно.
|
||
|
||
# --hints--
|
||
|
||
Повинна існувати структура даних HashTable.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
return typeof test === 'object';
|
||
})()
|
||
);
|
||
```
|
||
|
||
HashTable має містити метод add.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
return typeof test.add === 'function';
|
||
})()
|
||
);
|
||
```
|
||
|
||
HashTable має мати метод lookup.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
return typeof test.lookup === 'function';
|
||
})()
|
||
);
|
||
```
|
||
|
||
HashTable має мати метод remove.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
return typeof test.remove === 'function';
|
||
})()
|
||
);
|
||
```
|
||
|
||
Метод add повинен додати пари ключів-значень, а метод lookup повинен повернути значення, пов'язані з заданим ключем.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
test.add('key', 'value');
|
||
return test.lookup('key') === 'value';
|
||
})()
|
||
);
|
||
```
|
||
|
||
Після введення ключа метод remove вилучає асоціативну пару ключ-значення.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
var hashValue = hash('key');
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
test.add('key', 'value');
|
||
|
||
test.remove('key');
|
||
return !test.collection.hasOwnProperty(hashValue);
|
||
})()
|
||
);
|
||
```
|
||
|
||
Метод remove вилучає тільки правильну пару ключ-значення.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
var hashValue = hash('key');
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
test.add('key', 'value');
|
||
test.add('yek', 'value');
|
||
test.add('altKey', 'value');
|
||
|
||
test.remove('yek');
|
||
if (test.lookup('yek') || !test.lookup('key') || !test.lookup('altKey')) {
|
||
return false;
|
||
}
|
||
|
||
test.remove('key');
|
||
|
||
return !test.collection.hasOwnProperty(hashValue) && test.lookup('altKey');
|
||
})()
|
||
);
|
||
```
|
||
|
||
Елементи мають бути додані за допомогою геш-функції.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
called = 0;
|
||
test.add('key1', 'value1');
|
||
test.add('key2', 'value2');
|
||
test.add('key3', 'value3');
|
||
return called >= 3 && called % 3 === 0;
|
||
})()
|
||
);
|
||
```
|
||
|
||
Геш-таблиці повинні опрацьовувати колізії.
|
||
|
||
```js
|
||
assert(
|
||
(function () {
|
||
var test = false;
|
||
if (typeof HashTable !== 'undefined') {
|
||
test = new HashTable();
|
||
}
|
||
called = 0;
|
||
test.add('key1', 'value1');
|
||
test.add('1key', 'value2');
|
||
test.add('ke1y', 'value3');
|
||
return (
|
||
test.lookup('key1') === 'value1' &&
|
||
test.lookup('1key') == 'value2' &&
|
||
test.lookup('ke1y') == 'value3'
|
||
);
|
||
})()
|
||
);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --before-user-code--
|
||
|
||
```js
|
||
var called = 0;
|
||
var hash = string => {
|
||
called++;
|
||
var hash = 0;
|
||
for (var i = 0; i < string.length; i++) {
|
||
hash += string.charCodeAt(i);
|
||
}
|
||
return hash;
|
||
};
|
||
```
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
var called = 0;
|
||
var hash = string => {
|
||
called++;
|
||
var hashed = 0;
|
||
for (var i = 0; i < string.length; i++) {
|
||
hashed += string.charCodeAt(i);
|
||
}
|
||
return hashed;
|
||
};
|
||
var HashTable = function() {
|
||
this.collection = {};
|
||
// Only change code below this line
|
||
|
||
// Only change code above this line
|
||
};
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
var called = 0;
|
||
var hash = (string) => {
|
||
called++;
|
||
var hash = 0;
|
||
for (var i = 0; i < string.length; i++) { hash += string.charCodeAt(i); }
|
||
return hash;
|
||
};
|
||
var HashTable = function() {
|
||
this.collection = {};
|
||
// Only change code below this line
|
||
|
||
this.add = function(key, val) {
|
||
var theHash = hash(key);
|
||
if (!this.collection.hasOwnProperty(theHash)) {
|
||
this.collection[theHash] = {};
|
||
}
|
||
this.collection[theHash][key] = val;
|
||
}
|
||
|
||
this.remove = function(key) {
|
||
var theHash = hash(key);
|
||
var hashedObj = this.collection[theHash];
|
||
if (hashedObj.hasOwnProperty(key)) {
|
||
delete hashedObj[key];
|
||
}
|
||
if (!Object.keys(hashedObj).length) {
|
||
delete this.collection[theHash];
|
||
}
|
||
}
|
||
|
||
this.lookup = function(key) {
|
||
var theHash = hash(key);
|
||
if (this.collection.hasOwnProperty(theHash)) {
|
||
return this.collection[theHash][key];
|
||
}
|
||
return null
|
||
}
|
||
// Only change code above this line
|
||
};
|
||
```
|