I'm new to Hash Maps and I have an assignment due tomorrow. I implemented everything and it all worked out fine, except for when I get a collision. I cant quite understand the idea of linear probing, I did try to implement it based on what I understood, but the program stopped working for table size < 157, for some reason.
void hashEntry(string key, string value, entry HashTable[], int p) {key_de = key;val_en = value;for (int i = 0; i < sizeof(HashTable); i++){HashTable[Hash(key, p) + i].key_de = value;}}I thought that by adding a number each time to the hash function, 2 buckets would never get the same Hash index. But that didn't work.
Best Answer
A hash table with linear probing requires you
- Initiate a linear search starting at the hashed-to location for an empty slot in which to store your key+value.
- If the slot encountered is empty, store your key+value; you're done.
- Otherwise, if they keys match, replace the value; you're done.
- Otherwise, move to the next slot, hunting for any empty or key-matching slot, at which point (2) or (3) transpires.
- To prevent overrun, the loop doing all of this wraps modulo the table size.
- If you run all the way back to the original hashed-to location and still have no empty slot or matching-key overwrite, your table is completely populated (100% load) and you cannot insert more key+value pairs.
That's it. In practice it looks something like this:
bool hashEntry(string key, string value, entry HashTable[], int p){bool inserted = false;int hval = Hash(key, p);for (int i = 0; !inserted && i < p; i++){if (HashTable[(hval + i) % p].key_de.empty()){HashTable[(hval + i) % p].key_de = key;}if (HashTable[(hval + i) % p].key_de == key){HashTable[(hval + i) % p].val_en = value;inserted = true;}}return inserted;}Note that expanding the table in a linear-probing hash algorithm is tedious. I suspect that will be forthcoming in your studies. Eventually you need to track how many slots are taken so when the table exceeds a specified load factor (say, 80%), you expand the table, rehashing all entries on the new p size, which will change where they all end up residing.
Anyway, hope it makes sense.