Создание общих хеш-таблиц - C ++

Question

.NET Framework имеет класс Dictionary , который реализован в виде хеш-таблиц и обеспечивает получение данных в постоянное время (O (1)). Я ищу аналогичную реализацию в C ++. Я знаю о std :: map , но на этот поиск данных уходит логарифмическое время. Есть ли хорошая реализация хеш-таблицы в C ++, которая будет извлекать данные в постоянное время?

Если я напишу свой собственный, как я вычислю хеш-код для ключа? Как и в .NET, я думал о методе GetHashCode () для типов.

template<typename TKey,typename TVal>
class Dictionary
{
public:
   void Add(TKey key, TVal val){
       int hashCode = key.GetHashCode();
       /* .... */
   }
}

Если мне понравилось выше, и у данного типа ключа нет метода GetHashCode (), компилятор выдаст ошибку. Но этот метод не будет работать, когда ключ имеет примитивные типы, такие как int . Мне может понадобиться написать оболочку для int , указав GetHashCode .

Интересно, как C ++ это реализует?

Есть мысли?

Answer 1

Кроме того, проверьте Технический отчет C ++ 1 для std::tr1::unordered_map, если требуется строгое соблюдение стандарта C ++.

На самом деле std::hash_map не является стандартом C ++, но в любом случае широко используется.

Answer 2

boost :: unordered_map , вероятно, является вашим лучшим и наиболее широко переносимым решением на данный момент, если у вас нет реализации TR1 под рукой.

Answer 3

Если вы ищете готовую к использованию реализацию, то кроме хеш-таблиц STL / TR1 и Boost есть также google-sparsehash (он содержит две реализации - одну оптимизированную для пространства и одну оптимизированную для скорости).

Если вы хотите написать свой собственный, тогда GetHashCode может быть реализован как отдельный функтор, например,

template < typename TKey, typename TValue, typename THash = someDefaultHash<TKey> >
class Dictionary
{
public:
   void Add(TKey key, TVal val){
       int hashCode = THash()(key);
       /* .... */
   }
}

Вот как SGI's hash_map делает это.

Answer 4

Если вы используете VS 2008 с установленным Feature Pack или пакетом обновления 1, у вас есть реализация TR1, которая включает TR1 :: unordered_map.

OTOH, если вы действительно не создаете огромную коллекцию, есть вероятность, что std :: map будет более конкурентоспособным, чем вы ожидаете. В моих тестах довольно часто они почти связываются друг с другом, и std :: map может выходить быстрее и быстрее.

Answer 5

В C ++ вы бы передавали шаблону тип функтора с хеш-функцией в качестве параметра типа.

Answer 6

Возможно, std :: hash_map ?

Обратите внимание, что это не является частью стандартных спецификаций библиотеки STL, но часто доступно. Это в библиотеках MS и SGI (как следует из ссылки) и в STLport.