In this cheat sheet, average time complexity for access to a hash table is listed as N/A.
I'm curious as to why. Since a hash table is mostly mathematical, I would assume it would be O(1) like the other operations ... Search, Insertion, Delete.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ While that cheat sheet is not wrong (I don't think), it's less useful than you seem to think. $\endgroup$– Raphael ♦Oct 18, 2017 at 21:25
-
1$\begingroup$ "Since a hash table is mostly mathematical with out looping" -- I don't know what that's even supposed to mean. $\endgroup$– Raphael ♦Oct 18, 2017 at 21:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The chart is underspecified. I assume they mean by "Access" to "retrieve the $i$-th element¹.
In hashtables, there is no notion of order. While you could pick the $i$-th element in the underlying array, that would have no meaning at all. Hence, this operation does not make sense on hashtables -- n/a.
- Which is of course underspecified or unfair, depending on how you look at it: in a BST, "Access" gives you also the $i$-th smallest element, whereas in a plain array you get just some element.
answered Oct 18, 2017 at 21:40
$\begingroup$
$\endgroup$
There is no access method per se, it is the array with a function to calculate the place. There is no special structure, maybe linked lists would count, but nothing prevents from using for example tree here or second level tier hash in the array.
Also it fully depends on particular has function used, type of elements, collision resolution. To write it in Landau notation It would require to create multivariable complexity, which is fixed for particular choice of the hashtable type used.
There is no available accessor to get predecessor or successor of given value.
The complexity is expected $\mathcal O(1)$ but may degrade to $\mathcal O(n)$ unless it is a perfect setting then should be deterministic $\mathcal \Theta(1)$. But the hash gunction is slightly dependent on array size used, for huge, saturated table with guarantees of good lookup it may require $\mathcal O(\log n)$ bits to compute the hash.
Going a step further, there is also no access for the splay tree, because the accessed element via search changes place and also there is no order invariant, so the access operation would give no meaningful data. The same story goes for the Cartesian tree, where inorder traversal yields the original sequence, which is not sorted so picked element is not ordered.
