Return to Question

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.

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.

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.

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.

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)$. Now we try to partition the set of keys into $m$ buckets, where $m = n/100$. First we try with $i$ 0. If one bucket has more than 1000 entries (this is extremely unlikely, but possible), 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.

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.