Почему hash table имеет сложность O(1)?

[jaroslav.tavgen]

Лично я представляю Hash Table примерно так:

let array = Array.from({length:5}, _=>Math.floor(Math.random()*100));
let keys = [];
for(let i = 0; i < 100; i++){
  keys[i] = array.includes(i)?i:0;
}
// Дальше уже делаем с массивом то, что хотели: сортируем или находим сумму элементов или ещё что-нибудь

В данном конкретном примере это куда как ближе к O(n^2) (O(n^2 + 75) = O(n^2)), чем к O(1).

Почему же считается O(1)? Только потому что 100 - константа? Или я вообще всё неправильно понимаю?

[Aetae]

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