Austen944's Profile User Rating: -----

Reputation: 1 Apprentice
Group:
Members
Active Posts:
39 (0.04 per day)
Joined:
08-February 13
Profile Views:
995
Last Active:
User is offline Aug 01 2013 06:17 PM
Currently:
Offline

Previous Fields

Dream Kudos:
0
Icon   Austen944 has not set their status

Posts I've Made

  1. In Topic: C++ Hash Table Class Error "undefined reference to"

    Posted 1 Aug 2013

    Never mind. Just realized that it was only incrementing when a duplicated string appeared. Moved the incrementor to the "if statement" in put() and it now displays correctly.
  2. In Topic: C++ Hash Table Class Error "undefined reference to"

    Posted 1 Aug 2013

    After messing around I decided to do this for counting the collisions at each slot in the hash table.

    I declared a array "int collisionArray[SIZE]" in hashtable.h and set it equal to 0 in "HashTable()".
    Next in "put(string s)" I made a else statement to increment the appropriate element when a collision is found.

    hashtable.cpp
    #include <iostream>
    #include <string>
    #include "listtools.h"
    #include "listtools.cpp"
    #include "hashtable.h"
    
    using LinkedListSavitch::Node;
    using LinkedListSavitch::search;
    using LinkedListSavitch::headInsert;
    using namespace std;
    
    #define HASH_WEIGHT 31
    
    namespace HashTableSavitch
    {
       HashTable::HashTable()
       {
        for (int i = 0; i < SIZE; i++)
        {
         hashArray[i] = NULL;
         collisionArray[i] = 0;
        }
       }
    
       HashTable::~HashTable()
       {
         for (int i=0; i<SIZE; i++)
         {
           Node<string> *next = hashArray[i];
           while (next != NULL)
           {
             Node<string> *discard = next;
    	 next = next->getLink( );
    	 delete discard;
           }
         }
       }
    
       unsigned int HashTable::computeHash(string s) const
       {
        unsigned int hash = 0;
        for (unsigned int i = 0; i < s.length( ); i++)
        {
        	hash = HASH_WEIGHT * hash + s[i];
        }
        return hash % SIZE;
       }
    
       bool HashTable::containsString(string target) const
       {
        int hash = this->computeHash(target);
        Node<string>* result = search(hashArray[hash], target);
        if (result == NULL)
           return false;
        else
           return true;
       }
    
       void HashTable::put(string s)
       {
    	   int hash = computeHash(s);
    	   if (search(hashArray[hash], s) == NULL)
           {
    		   // Only add the target if it's not in the list
    		   headInsert(hashArray[hash], s);
           }
    	   else
    	   {
    		   collisionArray[hash]++;
    	   }
       }
    
       void HashTable::printArray()
       {
    	   int number;
    	   for(int i = 0; i < SIZE; i++)
    	   {
    		   number = collisionArray[i];
    		   cout << "----------------\n";
    		   cout << "index = " << i << endl;
    		   cout << "Collisions = " << number << endl;
    		   cout << "----------------\n";
    	   }
       }
    } // HashTableSavitch
    
    


    I made a void function called "printArray()" to print out the number of collisions at each slot, but it displays 0 collisions for each slot.

    Is my code wrong for counting the number of collisions at each slot or am I missing something really simple here? Thanks for explaining what a hash collision is btw.

My Information

Member Title:
New D.I.C Head
Age:
Age Unknown
Birthday:
Birthday Unknown
Gender:

Contact Information

E-mail:
Private

Friends

Comments

Page 1 of 1
  1. Photo

    burakaltr Icon

    16 Feb 2013 - 17:57
    Hey check out the JAVA Forum. I've come up with an answer for your question.
Page 1 of 1