CODEWITHSUNDEEP
javahashtablehash-collision
user4780686
user4780686

Reputation:

Hash Table With Coalesced Hashing

I am trying to figure out how to convert an add method of a hash table class implemented with quadratic probing as a collision solution method to use coalesced hashing instead. I know that it has something to do with linked lists however because I am a newbie with hash tables I am not sure where to start.

Here is the add method in question,

public boolean add(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(array, currentPos))
        return false;
    if (array[currentPos] == null)
        occupied++;
    array[currentPos] = new HashEntry(x, true);
    currentSize++;
    modCount++;
    if (occupied > array.length / 2)
        rehash();
    return true;
}

If anybody could show me how this method could be converted to use coalesced hashing I would greatly appreciate it.

Upvotes: 0

Views: 1494

Answers (1)

Mahsa2
Mahsa2

Reputation: 462

So, after I followed the wikipedia guideline and code here and I modified the code there to the following. I explain each portion with comments.

public boolean add(AnyType x) {
    // Finds the place that you want to insert into your table.
    // I believe the function contains the hash mapping
    int currentPos = findPos(x);
    // if the place is empty, you will insert your hash in there
    if (array[currentPos] == null) {
        array[currentPos] = new HashEntry(x, true);
    } else {
        // The place has been occupied (collision occured), so we will 
        // add it as a second item like a link list.
        // But, we do not want to allocate a new space and we use the 
        // empty spaces we have in our hash table instead.
        // That is the differece between coalesced hash and speparate chaining

        // the indexes are from 0 to HASH_TABLE_SIZE -1
        int cursor = HASH_TABLE_SIZE - 1; 
        /* Find the first empty bucket for the new entry */
        while ( cursor >= 0 && array[cursor] != NULL )
            --cursor;

        /* The table is full, terminate unsuccessfully */
        if ( cursor == -1 )
          return false;

        // Initial your new value in an empty bucket we found in the table
        array[cursor] = new HashEntry(x, true);

        /* Find the last node in the chain and point to it */
        // Here we need to find the tail of the link list in our hash table
        // We do not want to miss the link list that we made from the past,
        // therefore, we need to do the following
        struct node* it = array[currentPos];
        while ( it->next != NULL )
          it = it->next;
        // Now we assign the 
        it->next = array[cursor];       
    }
    return true;
}

I hope it helps.

Upvotes: 1

Related Questions