patternMinor
Does my simple, static hash table have O(1) worst case lookup?
Viewed 0 times
casesimplehavehashdoeslookupworsttablestatic
Problem
Will the following simple hash table construction algorithm be able to construct a
static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the problems, and is there a simple solution?
Construction
Let's assume we have a static set of $n$ keys.
We also have a fully random universal hash function $h_i(x)$ (let's say we use SHA-2 with $i$ as the IV).
Now we try to partition the set of keys into $m$ buckets, where $m = \lceil n/100 \rceil$.
First we try with $i$ 0. If one bucket has more than 1000 entries
(this is possible, but extremely unlikely, much less likely than to get a SHA-2 hash collision), start from scratch, that is re-build the hash table but use a different hash function, that is $h_1(x)$. Do this in a loop until we find an index $i$ that works.
Now the largest bucket has less than 1000 entries.
Each bucket is stored as a list, sorted by hash value.
The index $i$ is also stored.
Evaluation
For the static hash table constructed above, with the stored index $i$, calculate $h_i(x)$. Calculate the bucket, and in this bucket, do a binary search. I believe (hope) that this is an O(1) operation, because there are at most 1000 entries in this bucket.
Closely related: (When) is hash table lookup O(1)?. But I have a static set, and I have a fully random universal hash function. I know about FKS hashing, but I can't use it in my case, because it would require too much memory, and I would like to have a simpler algorithm. I understand my algorithm is terribly inefficient, but I'm mostly interested in a guaranteed $O(1)$ worst case access time.
static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the problems, and is there a simple solution?
Construction
Let's assume we have a static set of $n$ keys.
We also have a fully random universal hash function $h_i(x)$ (let's say we use SHA-2 with $i$ as the IV).
Now we try to partition the set of keys into $m$ buckets, where $m = \lceil n/100 \rceil$.
First we try with $i$ 0. If one bucket has more than 1000 entries
(this is possible, but extremely unlikely, much less likely than to get a SHA-2 hash collision), start from scratch, that is re-build the hash table but use a different hash function, that is $h_1(x)$. Do this in a loop until we find an index $i$ that works.
Now the largest bucket has less than 1000 entries.
Each bucket is stored as a list, sorted by hash value.
The index $i$ is also stored.
Evaluation
For the static hash table constructed above, with the stored index $i$, calculate $h_i(x)$. Calculate the bucket, and in this bucket, do a binary search. I believe (hope) that this is an O(1) operation, because there are at most 1000 entries in this bucket.
Closely related: (When) is hash table lookup O(1)?. But I have a static set, and I have a fully random universal hash function. I know about FKS hashing, but I can't use it in my case, because it would require too much memory, and I would like to have a simpler algorithm. I understand my algorithm is terribly inefficient, but I'm mostly interested in a guaranteed $O(1)$ worst case access time.
Solution
Yes, your access time is $\mathcal{O}(1)$. Your construction time is a bit more complicated. Let $P(k)$ be the propability, that a set structure containing $k$ elements has a bucket with more than 1000 entries. If there is an overflow after the initial construction in $\mathcal{O}(k)$, everything is rearranged with costs of $\mathcal{O}(k)$. But this might clash again. Thus you get expected costs of $\mathcal{O}(k) + \sum \limits^\infty_{j=1}P(k)^j\mathcal{O}(k)=\mathcal{O}\left(\frac{k}{1-P(k)}\right)$.
Context
StackExchange Computer Science Q#55493, answer score: 4
Revisions (0)
No revisions yet.