Обнаружение столкновений в hash_map STL - PullRequest
Новая
       24

Обнаружение столкновений в hash_map STL

0 голосов
/ 19 июня 2010

Мне нужно создать таблицу поиска для имен функций C (в качестве клавиш), чтобы указатели функций (в качестве значений).Я имею в виду использование контейнера hash_map в STL, поскольку время доступа к хеш-таблице составляет O(1).Есть ли хорошая хэш-функция для этого?В настоящее время я использую (31*H + c) в качестве своей хэш-функции.

Кроме того, hash_map STL заботится о коллизиях, или я должен заботиться о них в своем коде?Пожалуйста, приведите несколько примеров, если это возможно.

Пример кода, над которым я сейчас работаю 

#include <iostream>
#include <ext/hash_map>;

using namespace std;
using namespace __gnu_cxx;

namespace __gnu_cxx {
#ifndef __HASH_STRING__
#define __HASH_STRING__
  template <>
    struct hash<string> {
      size_t operator() (const std::string& s) const
      {
        size_t h = 0;
        std::string::const_iterator p, p_end;
        for(p = s.begin(), p_end = s.end(); p != p_end; ++p)
        {
          h = 31 * h + (*p);
        }
        return h;
      }
    };
#endif
};

int main()
{
  hash_map<string, int> months;

  months["january"] = 1;
  months["february"] = 2;
  months["march"] = 3;
  months["april"] = 4;
  months["may"] = 5;
  months["june"] = 6;
  months["july"] = 7;
  months["august"] = 8;
  months["september"] = 9;
  months["october"] = 10;
  months["november"] = 11;
  months["december"] = 12;

  return 0;
}

Ответы [ 2 ]

0 голосов
/ 19 июня 2010

Предполагая, что у вас есть полный STL, он на самом деле включает хеш-функцию hash<T>, которая во включенной форме имеет значение , подходящее для нескольких различных типов ключей , включая char * (строки C).Я не знаю подробностей о его производительности, но STL, как правило, спроектирован так, чтобы иметь приемлемую производительность для большинства приложений.

Что касается коллизий, то для обработки hash_map вам не нужно беспокоиться об этом..

0 голосов
/ 19 июня 2010

Вам не нужно иметь дело со столкновениями. Кроме того, я думаю, что std :: hash уже определен, поэтому вам не нужно беспокоиться о хэш-функции.

...