C++ хеш-таблица без использования STL

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

Вы можете использовать unordered associative container от Boost, он же. boost::unordered_map, который - это, реализованный в терминах хеш-таблицы.

Answer 3

Это спорный вопрос, поскольку STL не имеет контейнера для хеш-таблиц; std :: map будет альтернативой. Для большинства целей нет оснований не использовать std :: map. Для использования, для которого требуется хэш-таблица, boost :: unordered_map - лучший выбор (и я думаю, что соответствует хеш-таблице, определенной в новом стандарте C++ TR1. Некоторые компиляторы, но я не могу назвать их, могут предоставить хэш-таблицу TR1 как станд :: tr1 :: unordered_map

Answer 4

вы можете проверить GLIB хэш-таблицы
http://library.gnome.org/devel/glib/stable/glib-Hash-Tables.html

Answer 5

в случае, если вы знаете свой список ключей раньше времени (или его надстройкой), вы можете использовать a perfect hash function генератор, такой как gperf. gperf будет выплюнуть код C или C++.

(Вы можете чтобы выполнить некоторую работу, чтобы фактически создать контейнер, учитывая хеш-функцию.)

Answer 6

Если вам нужна максимальная производительность, используйте MCT's closed_hash_map или Google's dense_hash_map. Первый проще в использовании, последний более зрелый. Ваш случай использования звучит так, как будто это выиграет от закрытого хэширования.