Hash table lookup time
Posted on 2007-11-18
I know that a regular hash table usually has O(1) lookup time, but of course this sometimes degrades due to collisions.
But the original paper on Linear Hashing says that Linear Hashing usually gets O(1) lookup time:
"A new bucket has therefore been appended to the last bucket of the file to which all the records have been moved in one access. Since for all these records the bucket 100 is henceforward the primary bucket, they are all accessible in one access."
This seems to be saying that all the records which reside in buckets which were appended due to splits are accessible in O(1) time. But this doesn't seem to be the case. In order to access data in an appended bucket, first you need to look in the base region, and only then, if the key is not found, perform the second hash function and look in the extended region. But how is this "one access", as the above quote says? Shouldn't all records in the extended region require O(2) access time?