使用STL的C++哈希表w/o

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

Answer 2

您可以使用Boost，也就是unordered associative container。 boost::unordered_map，其中是按照哈希表来实现。

Answer 3

由于STL没有散列表容器，所以这是一个有争议的问题; std :: map将是替代方案。对于大多数目的而言，没有理由不使用std :: map。对于需要散列表的应用，boost :: unordered_map是最好的选择（我认为它与在新的C++ TR1标准中定义的散列表相匹配。有些编译器 - 但我不能命名它们 - 可能会将TR1散列表作为的std :: tr1 :: unordered_map

Answer 4

你可能想看看油嘴哈希表
http://library.gnome.org/devel/glib/stable/glib-Hash-Tables.html

Answer 5

在，你知道你的时间提前键列表的情况下（或其某些超集），您可以使用perfect hash function生成器如gperf。gperf将吐出C或C++代码。

（您可能会编辑做一些工作，实际上建立一个容器，虽然给定了散列函数）。

Answer 6

如果您需要最大性能，使用MCT's closed_hash_map或Google's dense_hash_map。前者更易于使用，后者更成熟。你的用例听起来好像会从封闭散列中受益。