Prevent Duplicate Entry into HashTable C++

Question

Hello, I was wondering if i could get some help to prevent a duplicate entry into my hashtable:

bool hashmap::put(const stock& s, int& usedIndex, int& hashIndex, int& symbolHash)
{
    hashIndex = this->hashStr( s.m_symbol ); // Get remainder, Insert at that index.
    symbolHash = (int&)s.m_symbol;
    usedIndex = hashIndex;

    while ( hashTable[hashIndex].m_symbol != NULL ) // collision found
    {
     ++usedIndex %= maxSize; // if necessary wrap index around
     if ( hashTable[usedIndex].m_symbol == NULL )
     {
      hashTable[usedIndex] = s;
      return true;
     }
    }
    hashTable[hashIndex] = s; // insert if no collision 
    return true;

}

The paramater hashIndex uses a java algorithm to generate an appropriate index to insert into the table. The usedIndex paramater is where I insert into the table when a collision is found; symbolHash just gets the address of the name passed in. stock is a class object.

My question is just, how do i prevent a duplicate entry?

Answer 1

Just look at the objects you're storing in that index. If you have to move the index because of a collision check those also. If they match what you're trying to store, throw an exception or something.

I'm guessing at your code so...

bool hashmap::put(const stock& s, int& usedIndex, int& hashIndex, int& symbolHash)
{
    hashIndex = this->hashStr( s.m_symbol ); // Get remainder, Insert at that index.
    symbolHash = (int&)s.m_symbol;
    usedIndex = hashIndex;

    if(hastTable[usedIndex].m_symbol == s.m_symbol){
        return false;
    }
    while ( hashTable[hashIndex].m_symbol != NULL ) // collision found
    {
            ++usedIndex %= maxSize; // if necessary wrap index around
            if ( hashTable[usedIndex].m_symbol == NULL )
            {
                    hashTable[usedIndex] = s;
                    return true;
            }else if(hastTable[usedIndex].m_symbol == s.m_symbol){
                 return false;
            }
    }
    hashTable[hashIndex] = s; // insert if no collision 
    return true;

}

Answer 2

When you detect a collision, you know the entries hash to the same value.

At this point compare the entry you are inserting with all the entries stored using the same hash. If any entry already stored is equal to the one you are inserting, don't insert it.

Answer 3

The hashes of identical data are identical. Identical will be inserted in the same place unless you handle otherwise (which you do, by finding an unused index).

If a collision occurs between the hash of the data to insert and the hash of existing data, check to see if the data match (because if the data match, the hashes match). The check would occur for every collision, so while you're iterating you need to check the data.

After the if in the while loop, add a check for if hashTable[usedIndex] == s and if that condition is true there's a duplicate (so handle how you wish, e.g. replace or throw an exception).

You may want to replace the innards of your if with a break; so code isn't duplicated. You also need to check if usedIndex == hashIndex because you may experience an infinite loop.