不使用 STL 的 C++ 哈希表

Question

我需要创建一个哈希表，其中的键是字符串，值是 int。我不能在我的目标上使用 STL 容器。是否有适合此目的的哈希表类？

Answer 1

这是我刚刚编写的一个快速的脏 C 散列。编译，但未经本地测试。尽管如此，您仍然可以根据需要运行这个想法。其性能完全取决于 keyToHash 函数。我的版本不会是高性能的，但会再次演示如何做到这一点。

static const int kMaxKeyLength = 31;
static const int kMaxKeyStringLength = kMaxKeyLength + 1;

struct HashEntry
{
  int value;
  char key[kMaxKeyLength];
};

static const char kEmptyHash[2] = "";

static const int kHashPowerofTwo = 10;
static const int kHashSize = 1 << kHashPowerofTwo;
static const int kHashMask = kHashSize - 1;

static const int kSmallPrimeNumber = 7;

static HashEntry hashTable[kHashSize];

int keyToHash(const char key[])
{
  assert(strlen(key) < kMaxKeyLength);

  int hashValue = 0;
  for(int i=0; < strlen(key); i++)
  {
    hashValue += key[i];
  }

  return hashValue;
}

bool hashAdd(const char key[], const int value)
{
  int hashValue = keyToHash(key);

  int hashFullSentinal = 0;
  while(strcmp(hashTable[hashValue & kHashMask].key, kEmptyHash))
  {
    hashValue += kSmallPrimeNumber;

    if(hashFullSentinal++ >= (kHashSize - 1))
    {
      return false;
    }
  }

  strcpy(hashTable[hashValue & kHashMask].key, key);
  hashTable[hashValue & kHashMask].value = value;

  return true;
}   

bool hashFind(const char key[], int *value)
{
  int hashValue = keyToHash(key);

  while(strcmp(hashTable[hashValue & kHashMask].key, kEmptyHash))
  {
    if(!strcmp(hashTable[hashValue & kHashMask].key, key))
    {
      *value = hashTable[hashValue & kHashMask].value;
      return true;
    }
  }

  return false;
}

bool hashRemove(const char key[])
{
  int hashValue = keyToHash(key);

  while(strcmp(hashTable[hashValue & kHashMask].key, kEmptyHash))
  {
    if(!strcmp(hashTable[hashValue & kHashMask].key, key))
    {
      hashTable[hashValue & kHashMask].value = 0;
      hashTable[hashValue & kHashMask].key[0] = 0;
      return true;
    }
  }

  return false;
}