[tabelele de hash au] O (1) inserare și căutare
Cred că este greșit.
Mai întâi, dacă limitați spațiul de chei pentru a fi finit,
puteți stoca elementele într-o matrice și puteți efectua o scanare
liniară O (1). Sau ai putea shufflesort matricea și apoi face o
scanare liniară în O (1) timpul așteptat. Când lucrurile sunt
finite, lucrurile sunt ușor O (1).
Deci, să spunem că tabela dvs. de hash va stoca orice șir de
biți arbitrari; nu contează prea mult, atâta timp cât există un set
infinit de chei, fiecare dintre acestea fiind finite. Apoi trebuie
să citiți toți biții oricărei interogări și intrări de introducere,
altfel am inserat y0 într-o hash goală și o interogare pe y1, unde
y0 și y1 diferă la o poziție de un singur bit pe care nu te uiți
la.
Dar să presupunem că lungimea cheilor nu este un parametru. Dacă
inserarea și căutarea dvs. iau O (1), în special hashing-ul are o
durată O (1), ceea ce înseamnă că vă uitați doar la o cantitate
finită de ieșire din funcția hash (de la care este probabil să
fi numai o ieșire finită, acordată).
This means that with finitely many buckets, there must be an
infinite set of strings which all have the same hash value. Suppose
I insert a lot, i.e. ω(1), of those, and start querying. This means
that your hash table has to fall back on some other O(1)
insertion/search mechanism to answer my queries. Which one, and why
not just use that directly?