SHA e altri noti algoritmi Hash O(n) dove n dimensione input... se vuoi provare a tenere basse le collisioni...
Hash table - Worst case O(n) ecco perchè adoro gli indici ad albero :-D...
http://en.wikipedia.org/wiki/Hash_table
Chi gestisce il dato non si può permettere una tabella hash talmente grande da tenere il costo a O(1), per questo meglio mediare su strutture ad albero che garantiscono O(log n)