Skip to main content

Що таке «bucket» (кошик) у контексті хеш-таблиці?

Структури данихJunior~1 хв читання
Запропонувати правку

Bucket (кошик) - це комірка в хеш-таблиці, де зберігаються елементи, чиї ключі після хешування дали один і той самий індекс.

Як це працює

  1. Хеш-функція обчислює індекс для ключа:
javascript
index = hash(key) % N
  1. Усі елементи, для яких цей індекс збігається, потрапляють в один і той самий кошик.
  2. Якщо таких елементів кілька - це колізія, і кошик зберігає їх усі (наприклад, у вигляді списку).

Приклад

Якщо hash("cat") % 10 = 3 і hash("dog") % 10 = 3, обидва елементи будуть лежати в кошику з індексом 3.

javascript
bucket[3] → [("cat", "meow"), ("dog", "woof")]

Призначення

Кошики потрібні, щоб вирішувати колізії: зберігати кілька елементів, які потрапили в одну комірку.

Іншими словами, bucket - це міні-сховище всередині хеш-таблиці, де можуть перебувати одна або кілька пар "ключ → значення" з однаковим хеш-індексом.

Коротка відповідь

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Запропонувати правку