[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?