Why do hash tables have no access/indexing complexity but have $O(1)$ search complexity?

Question

Sources:

• https://en.wikipedia.org/wiki/Best,_worst_and_average_case
• https://www.bigocheatsheet.com/

It can be seen that a Hash Table has no access/indexing complexity given the above sources. This doesn't make sense to me, since given a key, I can look it up in constant time by hashing it and iterating through the associated bucket (assuming the key space is less than the number of buckets, and on average). If this isn't the definition of an access/index, then how come a Binary Search Tree for example has $O(\log n)$ for access/indexing? It also doesn't do direct memory addressing and must also find the key outside that.

Also how can a Hash Table have $O(1)$ search complexity? If I'm looking to search for something, given that a Hash Table is unordered, I will on average have to search through $n/2$ nodes, giving $O(n)$ complexity. If this isn't the definition of search, then how come an array for example has $O(1)$ for access/indexing and $O(n)$ for search?

Answer 1

I think you have interchanged the idea of index and search.

Access/index here means given a position or index, like in an ordinary array or list, return the element in that index. This is why arrays support this operation in $O(1)$ time. Index or access is supported by BST because you can use them to implement sorted list. See order statistic tree for reference on how to do this. Hash table does not support index/access since the idea behind them is to "systematically scatter" elements in the structure to prevent/reduce collision, and with that, we do not expect to use such structures to maintain order of elements to support position based access.

Search on the other hand, means given an element, find it in the structure. So the $O(1)$ average search time for hashtables come from the way it searches - compute the hash of the element and perform some extra search in the bucket or probing. For arrays, with no assumptions about the elements, the only possible search is via linear search, thus the $O(n)$ running-time.