title: C++ Hashtable for Strings
body: <p>I'm trying to use a hash table in C++ to store strings i.e a string key and data. I'm using code from the 2003 book Data structures for games programmers.</p>
  <p>While I can implement an int hash table, I'm stuck at what's wrong when I try and do the same with a string one.</p>
  <p>C++ keeps giving me the same error.</p>
  <pre><code>//code
  #include &lt;string&gt;
  #include &lt;iostream&gt;
  #include &quot;HashTable.h&quot;
  
  using namespace std;
  
  //hash table
  //***********************************************************************
  unsigned long int Hash(int i) {
      return i;
  }
  
  unsigned long int StringHash(const char* p_string) {
      unsigned long int hash = 0;
      int i;
      int length = strlen(p_string);
      for(i = 0; i &lt; length; i++) {
          hash += ((i + 1) * p_string[i]);
      }
      return hash;
  }
  
  HashTable&lt;string, string&gt; table(10, StringHash); &lt;&lt;--problem here ERROR BELOW
  HashEntry&lt;string, string&gt;* entry;
  //***********************************************************************
  </code></pre>
  <blockquote>
  <p>Error 6   error C2664:
  'HashTable&lt;KeyType,DataType&gt;::HashTable(int,unsigned
  long (__cdecl *)(KeyType))' : cannot
  convert parameter 2 from 'unsigned
  long (__cdecl *)(const char *)' to
  'unsigned long (__cdecl
  *)(KeyType)'  j:\my_docs\college 2010 -2011\data structures for games\ca3_datastructures_gerry mc
  donnell\ca3_datastructures_gerry mc
  donnell\loginuser.h   31  CA3_DataStructures_gerry
  mc donnell</p>
  </blockquote>
  <p>If anyone can help it would be great.</p>
  <p>The <code>stringhash</code> function was given by the book so I'm not sure what I'm doing wrong.</p>
  <p>Hashtable.h</p>
  <pre class="lang-c prettyprint-override"><code>// ============================================================================
  // Data Structures For Game Programmers
  // Ron Penton
  // HashTable.h
  // This file holds the Linekd Hash Table implementation.
  // ============================================================================
  
  #ifndef HASHTABLE_H
  #define HASHTABLE_H
  
  #include &quot;DLinkedList.h&quot;
  #include &quot;Array.h&quot;
  
  // -------------------------------------------------------
  // Name:        HashEntry
  // Description: This is the hash table entry class. It
  //              stores a key and data pair.
  // -------------------------------------------------------
  template&lt; class KeyType, class DataType &gt;
  class HashEntry {
    public:
      KeyType m_key;
      DataType m_data;
  };
  
  // -------------------------------------------------------
  // Name:        HashTable
  // Description: This is the hashtable class.
  // -------------------------------------------------------
  template&lt; class KeyType, class DataType &gt;
  class HashTable {
    public:
      // typedef the entry class to make is easier to work with.
      typedef HashEntry&lt;KeyType, DataType&gt; Entry;
  
      // ----------------------------------------------------------------
      //  Name:           HashTable
      //  Description:    construct the table with a size, and a hash
      //                  function. The constructor will construct the
      //                  m_table array with the correct size.
      //  Arguments:      p_size: The size of the table
      //                  p_hash: the hashing function.
      //  Return Value:   None
      // ----------------------------------------------------------------
      HashTable(int p_size, unsigned long int (*p_hash)(KeyType))
        : m_table(p_size) {
        // set the size, hash function, and count.
        m_size = p_size;
        m_hash = p_hash;
        m_count = 0;
      }
  
      // ----------------------------------------------------------------
      //  Name:           Insert
      //  Description:    Inserts a new key/data pair into the table.
      //  Arguments:      p_key: the key
      //                  p_data: the data attached to the key.
      //  Return Value:   None
      // ----------------------------------------------------------------
      void Insert(KeyType p_key, DataType p_data) {
        // create an entry structure.
        Entry entry;
        entry.m_data = p_data;
        entry.m_key = p_key;
        // get the hash value from the key, and modulo it
        // so that it fits within the table.
        int index = m_hash(p_key) % m_size;
        // add the entry to the correct index, increment the count.
        m_table[index].Append(entry);
        m_count++;
      }
  
      // ----------------------------------------------------------------
      //  Name:           Find
      //  Description:    Finds a key in the table
      //  Arguments:      p_key: the key to search for
      //  Return Value:   a pointer to the entry that has the key/data,
      //                  or 0 if not found.
      // ----------------------------------------------------------------
      Entry* Find(KeyType p_key) {
        // find out which index the key should exist in
        int index = m_hash(p_key) % m_size;
        // get an iterator for the list in that index.
        DListIterator&lt;Entry&gt; itr = m_table[index].GetIterator();
        // search each item
        while (itr.Valid()) {
          // if the keys match, then return a pointer to the entry
          if (itr.Item().m_key == p_key)
            return &amp;(itr.Item());
          itr.Forth();
        }
        // no match was found, return 0.
        return 0;
      }
  
      // ----------------------------------------------------------------
      //  Name:           Remove
      //  Description:    Removes an entry based on key
      //  Arguments:      p_key: the key
      //  Return Value:   true if removed, false if not found.
      // ----------------------------------------------------------------
      bool Remove(KeyType p_key) {
        // find the index that the key should be in.
        int index = m_hash(p_key) % m_size;
        // get an iterator for the list in that index.
        DListIterator&lt;Entry&gt; itr = m_table[index].GetIterator();
        // search each item
        while (itr.Valid()) {
          // if the keys match, then remove the node, and return true.
          if (itr.Item().m_key == p_key) {
            m_table[index].Remove(itr);
            m_count--;
            return true;
          }
          itr.Forth();
        }
        // item wasn't found, return false.
        return false;
      }
  
      // ----------------------------------------------------------------
      //  Name:           Count
      //  Description:    Gets the number of entries in the table.
      //  Arguments:      None
      //  Return Value:   Number of entries in the table.
      // ----------------------------------------------------------------
      int Count() {
        return m_count;
      }
  
      // ----------------------------------------------------------------
      //  Name:           m_size
      //  Description:    This is the size of the table
      // ----------------------------------------------------------------
      int m_size;
  
      // ----------------------------------------------------------------
      //  Name:           m_count
      //  Description:    This is the number of entries in the table.
      // ----------------------------------------------------------------
      int m_count;
  
      // ----------------------------------------------------------------
      //  Name:           m_table
      //  Description:    This is the actual table, a list of linked
      //                  lists of entries.
      // ----------------------------------------------------------------
      Array&lt; DLinkedList&lt; Entry &gt; &gt; m_table;
  
      // ----------------------------------------------------------------
      //  Name:           m_hash
      //  Description:    a pointer to the hash function.
      // ----------------------------------------------------------------
      unsigned long int (*m_hash)(KeyType);
  };
  
  #endif
  //array.h
  </code></pre>