Hash function to hash 6-digit positive integers

Question

Let UID denote a unique identifier. UID's are represented as 6-digit positive integers.

I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for example, 524309).

If I am not mistaken, since $M$ is prime, dividing an UID with $M$ generates a unique remainder, as there is no common factor, except 1.

Example 1: UID = 222222 and $M$ = 524309.

Example 2: UID = 524309 and $M$ = 524309. In this example, the UID is hashed to bucket number zero in the hash table. The hash function is h(UID) = UID % M.

The question is: can hash function h avoid collisions for any 6-digit UID?

If yes, what is the mathematical approach to prove it?

Answer 1

A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that maps hash codes to locations in the hash table where the item would be stored.

Hashing every UID to a different 32 bit hash code is trivial - just hash every UID to itself. No collisions. The mapping function of the hash table should be implemented in a way that common hash functions don't lead to many collisions. Many hash functions either produce results that look like random, or like in this case might produce many consecutive values, so using a prime number as the hash table size and (hash code modulo hash table size) as the first location for the location in the table works quite well.

Since you have one million items, and 524309 entries, it's impossible to guarantee no collisions. In practice, that's not a problem. What counts is the time for calculating the hash code, plus the average time for finding and checking one or more locations in your hash table. As long as the average number of collisions is small, you are fine. And there is a simple way that usually keeps the number of collisions small: Use a generous size for the hash table.

Answer 2

I think you've missed the point of hash tables. Hash tables are used to give array-like access to a dataset that's too big and sparse to store in an array. So, for example, it sounds like you're trying to store a mapping of UIDs to usernames or something like that. The naive way of doing that would be to just have an array with one entry for each possible UID so, in this case, an array of 1,000,000 strings. The advantage of that approach is that you can look up the name associated with a UID in constant time: you just write something like username[uid] to retrieve it from the array. The problem is that in most applications, you only have maybe a few thousand users at most, so most of your array is empty and you're wasting a lot of space.

You can avoid wasting the space by, for example, storing pairs of UID and username in a linked list: now you only have one entry in the list for each user so you're much more memory-efficient. However, retrieving a username now requires a linear search through the list, as does adding a new username. Using something like a search tree would allow logarithmic look-up and insertion but that's still quite a bit slower than an array.

The point of using a hash table is that it gives you nearly constant look-up and insertion time, like an array, but it doesn't waste as much space. The idea is that, instead of storing a UID's username at username[uid], you store it at username[h(uid)] for some function h which is fairly easy to compute. You choose a function with a range that is the size of the hash table you're going to use, and the point is to make this a good deal smaller than the number of possible UIDs.

However, doing this guarantees that h will map at least two UIDs to the same slot in the hash table: this is exactly the pigeonhole principle. Unless you know in advance exaclty what data you're going to be storing, you it's impossible to guarantee that this won't happen; all you can do is try to make it unlikely and deal with the inevitable collisions when they happen.

In a comment, you ask if using a hash table with size 999,983 would work. That wouldn't be a sensible hash table, since it's almost as big as just using an array of size 1,000,000 and forgetting about hashing. In fact, it's bigger because dealing with collisions would require you to store both the UID and username for each entry in the hash table, whereas in an array, you just need to store the username.

In the question, you say

since $M$ is prime, dividing an UID with $M$ generates a unique remainder

That has nothing to do with whether or not $M$ is prime. Dividing any positive integer by any other positive integer produces a single, well-defined, unique remainder.

Answer 3

A hash function cannot avoid collisions when the size $M$ of the hash table is smaller than the size of the universal set $U$ that you are hashing. This is a consequence of the compression step. In your case, $U$ is the set of UIDs. Since $|U|=1000000$ and $M= 524309$, then $M < |U|$ and, therefore, collisions will inevitably occur (see Pigeonhole principle).

As an answer to your comment:

When you say generous size for the hash table, Is M = 999,983 fine?

What really determines the performance of a hash table is the load factor, which is the ratio $\alpha = k / M$, where $k$ is the number of items stored in the hash table. The load factor can be controlled by dynamically increasing (or decreasing) $M$, as items are inserted into (or deleted from) the hash table. When to increase/decrease $M$ depends on the hash table implementation:

• In open addressing, keep a load factor of, roughly, $\alpha \leq 0.7$.

• In separate chaining, keep $\alpha$ as a small constant (ideally close to 1). This will guarantee constant-time insertions, deletions, and look-ups.

With these rules of thumb in mind, you can find an appropriate $M$ using existing algorithms for primality testing.