C++字符串的哈希表

Question

我正在尝试使用 C++ 中的哈希表来存储字符串，即字符串键和数据。我正在使用 2003 年出版的《游戏程序员的数据结构》一书中的代码。

虽然我可以实现一个 int 哈希表，但当我尝试对字符串哈希表执行相同操作时，我却陷入了错误。

C++ 总是给我同样的错误。

//code
#include <string>
#include <iostream>
#include "HashTable.h"

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 < length; i++) {
        hash += ((i + 1) * p_string[i]);
    }
    return hash;
}

HashTable<string, string> table(10, StringHash); <<--problem here ERROR BELOW
HashEntry<string, string>* entry;
//***********************************************************************

错误 6 错误 C2664： 'HashTable::HashTable(int,无符号 long (__cdecl *)(KeyType))' ：不能 将参数 2 从 'unsigned long (__cdecl *)(const char *)' 到 '无符号长整型（__cdecl *)(KeyType)' j:\my_docs\college 2010 -2011\游戏数据结构\ca3_datastructs_gerry mc 唐纳尔\ca3_datastructs_gerry mc donnell\loginuser.h 31 CA3_DataStructures_gerry 麦克唐纳

如果有人能提供帮助那就太好了。

stringhash 函数是书中给出的，所以我不确定我做错了什么。

哈希表.h

// ============================================================================
// Data Structures For Game Programmers
// Ron Penton
// HashTable.h
// This file holds the Linekd Hash Table implementation.
// ============================================================================

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include "DLinkedList.h"
#include "Array.h"

// -------------------------------------------------------
// Name:        HashEntry
// Description: This is the hash table entry class. It
//              stores a key and data pair.
// -------------------------------------------------------
template< class KeyType, class DataType >
class HashEntry {
  public:
    KeyType m_key;
    DataType m_data;
};

// -------------------------------------------------------
// Name:        HashTable
// Description: This is the hashtable class.
// -------------------------------------------------------
template< class KeyType, class DataType >
class HashTable {
  public:
    // typedef the entry class to make is easier to work with.
    typedef HashEntry<KeyType, DataType> 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<Entry> 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 &(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<Entry> 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< DLinkedList< Entry > > m_table;

    // ----------------------------------------------------------------
    //  Name:           m_hash
    //  Description:    a pointer to the hash function.
    // ----------------------------------------------------------------
    unsigned long int (*m_hash)(KeyType);
};

#endif
//array.h

Answer 1

您的 Hashtable 构造函数要求哈希函数采用 KeyType 参数。

您正在创建一个 Hashtable，其中 std::string 作为 KeyType，但传递一个采用 char* 的哈希函数代码>参数。这些不兼容。

使用 char* 键类型创建哈希，或者更改哈希函数以使用 std::string。

Answer 2

在 HashTable.h 中，哈希函数具有函数签名 unsigned long int (*p_hash)(KeyType)。也就是说，如果您的哈希表是 HashTable，则哈希函数的预期形式是 unsigned long int (*p_hash)(string)，而不是 <代码>unsigned long int (*p_hash)(const char*) 如发布。

Answer 3

HashTable<string, string> table( 10, StringHash );

string（第二个模板参数）是您的 KeyType，但您的哈希函数需要 const char *

或

unsigned long int StringHash( const string & p_string )

或

 HashTable<string, const char *> table( 10, StringHash );

应该可以工作。 （尚未编译或测试）