I want to implement a hashmap, but I am not allowed to let it expand. Since I do know that I need to store at most N elements, I could pre-allocate an array with N elements for each bucket of my hashtable, so that I can still store N elements in the worst case where all keys are hashed on the same bucket. But the elements that I need to store are rather big, so for large N this is very inefficient use of memory.
Is it possible to implement a hashmap efficiently (in terms of memory) with a fixed amount of memory, e.g. by implementing a smart hashing function?
(P.S.: the key is an unsigned 32-bit integer, and I have no prior knowledge about the keys except that the key values I will receive are in a fairly small subset of the range, and this subset moves very slowly up in the range.)
I now have an implementation where I have two arrays of length N, one with the elements, and one with the keys that correspond to the element at position i in both arrays. I use the modulo operation as a hash function to determine where the element should be inserted/present, and a linear probe to find the nearest empty spot in case of a collision. I think this is of complexity O(N), and I think this will work reasonably fast for the amounts of data that I am expecting. I asked the question to see if it can be done better.
For hashing, you could use following snippet, which btw Linux kernel uses to hash PIDs:
unsigned long hash_long(unsigned long val, unsigned int bits)
{
unsigned long hash = val * 0x9e370001UL;
return hash >> (32 - bits);
}
The magic number 0x9e370001UL is a large prime number. Here's an extract from Understanding Linux Kernel explaining the magic number:
You might wonder where the 0x9e370001 constant (= 2,654,404,609) comes
from. This hash function is based on a multiplication of the index by
a suitable large number, so that the result overflows and the value
remaining in the 32-bit variable can be considered as the result of a
modulus operation. Knuth suggested that good results are obtained
when the large multiplier is a prime approximately in golden ratio to
232 (32 bit being the size of the 80×86’s registers). Now,
2,654,404,609 is a prime near to that can also be easily multiplied
by additions and bit shifts, because it is equal to 2^31 + 2^29 -
2^25 + 2^22 - 2^19 - 2^16 + 1.
The right shift hash >> (32 - bits); just says keep bits number of bits in the hash value. Other bits will be zeroed out. In your case, bits will be determined by the limit N. For this to work as it is, N needs to be such that all its bits after its most significant set bit are set too, e.g. for N = 7 (where last three bits are all set and all other bits are zero) and bits will be 3. Or N = 63 where the least significant six bits are all set and all other bits are zero. Here bits will be 6.
Value returned by hash_long function will form index into your array.
Handling Collisions
To handle collisions, keep just one array but make it an array of linked list nodes. So every element in the array points to a linked list. When there is a collision, just append the new entry to the end of the linked list corresponding to that slot in your array.
Handling Collisions (Update)
If you cannot allocate new memory dynamically then the solution you posted seems fine, although I'm not sure what's the purpose of array which contains just keys (shouldn't a key be a member of the element that it belongs to?). Here is suggestion towards your solution:
To have a 1-D array means that in case of a collision, we perform linear probe both when inserting as well as when retrieving. An alternative would be to have a 2-D array where inner array acts as a linked list. We will need to index of last element inserted in each of the inner arrays. The down side compared to 1-D array is that if too many collisions happen on the same index then we may run out of space in one of the inner arrays, unless we make each inner array of length N as well, which will lead to a lot of wasted space. The advantage is that when inserting, we don't need to perform a linear probe. We just check the index of last element in the inner array and increment it by one to get next slot to insert the new element in.
