void rehash( ) { vector<HashEntry> oldArray = array; // Create new double-sized,

Question

void rehash( )
{
    vector<HashEntry> oldArray = array;

    // Create new double-sized, empty table
    array.resize( 2 * oldArray.size( ) );
    for( auto & entry : array )
       entry.info = EMPTY;

// Copy table over
    currentSize = 0;
    for( auto & entry : oldArray )
       if( entry.info == ACTIVE )
           insert( std::move( entry.element ) );
}

I grabbed some code from the Internet for my linear probing based hash table because the Internet's always right The hash table works but once I put more than a few thousand entries the whole thing starts to slow down Searches inserts, and contains calls start taking *way* longer than 0(1) time and my boss is pissed because it's slowing down the whole application services backend I'm in charge of. I think the bug's in my rehash code but I'm not sure where Any ideas why my hash table starts to suck as it grows bigger?/* * * Rehashing for linear probing hash table */void rehash() vector oldArray = array;//Create new double-sized empty table array re size(2 * ols array size ()) for (auto & entry: array) entry info = EMPTY;//Copy table Over current size for (auto & entry: oldArray) if(entry .info == ACTIVE) insert (std::move (entry element));}

Explanation / Answer

However, it has many more possible search keys than there are hash elements. It is inevitable that some keys will resolve to the same hash code. This is known as a hash collision, and it must be handled properly.

Hash collisions will always occur, but we can be avoid it by spreading the data evenly across the entire table, on the whole so there is a smaller chance of collisions occuring.

If you faced with a collision situation,then the linear probing table will look onto to subsequent hash elements until the first free space is found. This way of traversal is known as probing the table

Related Questions

Navigate

• Browse (All)
• Browse V
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.