Search code examples
hashtable

hash table lookup time

When we are insert/lookup an key in a hash table, textbook said it is O(1) time. Yet, how is possible to have an O(1) lookup time? If the hash table store the key in a vector, it will cost O(N), if in a binary tree, it will be O(logN). I just can't image some data structure with O(1) accessing time.

Thanks!

Solution

  • The hashtable hashes your key and put it in array.

    For example, hash(x) = 3, where x is your key. The table then puts it into array[3]. Accessing from array is O(1).