title: How can I implement a fixed size hashmap?
body: <p>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 <code>N</code> elements, I could pre-allocate an array with <code>N</code> elements for each bucket of my hashtable, so that I can still store <code>N</code> 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 <code>N</code> this is very inefficient use of memory.</p>
  
  <p>Is it possible to implement a hashmap <strong>efficiently</strong> (in terms of memory) with a fixed amount of memory, e.g. by implementing a smart hashing function?</p>
  
  <p>(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.)</p>
  
  <hr>
  
  <p>I now have an implementation where I have two arrays of length <code>N</code>, one with the elements, and one with the keys that correspond to the element at position <code>i</code> 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.</p>