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

Question

Мне нужно создать хеш-таблицу, которая имеет ключ в виде строки и значение в виде целого числа. Я не могу использовать контейнеры STL на моей цели. Есть ли подходящий класс хеш-таблиц для этой цели?

Answer 1

Вот быстрый грязный хеш, который я только что написал. Компилируется, но не тестируется локально. Тем не менее, идея заключается в том, чтобы вы работали с ним при необходимости Производительность этого полностью зависит от функции 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 &lt&lt kHashPowerofTwo;
static const int kHashMask = kHashSize - 1;

static const int kSmallPrimeNumber = 7;

static HashEntry hashTable[kHashSize];

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

  int hashValue = 0;
  for(int i=0; &lt 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++ &gt= (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

В случае, если вы знаете свой список ключей раньше времени (или какой-то его расширенный набор), вы можете использовать генератор совершенных хеш-функций , например <a href="http://www.gnu.org/software/gperf/" rel="nofollow noreferrer">gperf</a>. gperf выдаст код C или C ++.

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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