CODEWITHSUNDEEP
c++data-structureshashtable
Blade3
Blade3

Reputation: 4380

C++ hash table w/o using 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?

Upvotes: 1

Views: 2678

Answers (6)

user319799
user319799

Reputation:

If you need maximum performance, use MCT's closed_hash_map or Google's dense_hash_map. The former is easier to use, the latter is more mature. Your use case sounds like it would benefit from closed hashing.

Upvotes: 0

Michael Dorgan
Michael Dorgan

Reputation: 12515

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

Upvotes: 2

leander
leander

Reputation: 8737

In the case that you know your list of keys ahead of time (or some superset thereof), you can use a perfect hash function generator like gperf. gperf will spit out either C or C++ code.

(You may need to do some work to actually build a container, given the hash function, though.)

Upvotes: 1

frankc
frankc

Reputation: 11483

You might want to check out glib hash tables
http://library.gnome.org/devel/glib/stable/glib-Hash-Tables.html

Upvotes: 0

c-urchin
c-urchin

Reputation: 4534

It's a moot point since STL has no hash table container; std::map would be the alternative. For most purposes there is no reason not to use std::map. For uses that require a hashtable, boost::unordered_map is the best choice (and I think matches the hashtable defined in the new C++ TR1 proposed standard. Some compilers -- but I can't name them -- may provide the TR1 hashtable as std::tr1::unordered_map

Upvotes: 0

Konrad Rudolph
Konrad Rudolph

Reputation: 546043

You can use the unordered associative container from Boost, aka. boost::unordered_map, which is implemented in terms of a hash table.

Upvotes: 0

Related Questions