使用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。前者更易於使用，後者更成熟。你的用例聽起來好像會從封閉散列中受益。