title: simple hash map with vectors in C++
body: <p>I'm in my first semester of studies and as a part of my comp. science assignment I have to implement a simple hash map using vectors, but I have some problems understanding the concept. </p>
  
  <p>First of all I have to implement a hash function. To avoid collisions I thought it would be better to use double hashing, as follows:</p>
  
  <pre><code>do {
      h = (k % m + j*(1+(k % (m-2)));
      j++;
  } while ( j % m != 0 );
  </code></pre>
  
  <p>where h is the hash to be returned, k is the key and m is the size of hash_map (and a prime number; they are all of type int).</p>
  
  <p>This was easy, but then I need to be able to insert or remove a pair of key and the corresponding value in the map.</p>
  
  <p>The signature of the two functions should be bool, so I have to return either true or flase, and I'm guessing that I should return true when there is no element at position h in the vector. (But I have no idea why remove should be bool as well).</p>
  
  <p>My problem is what to do when the insert function returns false (i.e. when there is already a key-value pair saved on position h - I implemented this as a function named find). I could obviously move it to the next free place by simply increasing j, but then the hash calculated by my hash function wouldn't tell us anymore at which place a certain key is saved, causing wrong behaviour of remove function.</p>
  
  <p>Is there any good example online, that doesn't use the pre defined STD methods? (My Google behaves wierdly in the past few days and only reutrns me unuseful hits in the local language)</p>