使用STL的C ++哈希表 [英] C++ hash table w/o using STL

问题描述

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

I need to create a hash table that has a key as a string, and value as an int. I cannot use STL containers on my target. Is there a suitable hash table class for this purpose?

推荐答案

这里是一个快速的脏C哈希我刚才写。编译，但未本地测试。仍然，这个想法是有你需要运行它。这个性能完全取决于keyToHash函数。我的版本不会有高性能，但再次演示如何做。

Here's a quick a dirty C hash I just wrote. Compiles, but untested locally. Still, the idea is there for you to run with it as needed. The performance of this is completely dependant upon the keyToHash function. My version will not be high performance, but again demonstrates how to do it.

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;
}

这篇关于使用STL的C ++哈希表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！