C++ hashmap 解析

我看的版本大概有两个,一个是SGI实现的,一个是Free Software Foundation,如果代码上有什么不一样,希望不要在意那些细节~实现都是很相似的

底层实现

我个人的理解,STL中,unordered_map和unordered_set都是一个adapter,里面包裹了一个底层的hashtable的对象,所有类的操作全部是依靠他来完成

hashtable,它使用的是开链法(separate chaining),他的泛型设计非常有意思
一般可能我们设计一个与map类似的泛型类,我们可能会以下面这种方式来定义

template <class Key, class Value>
class UserMap {
    Key   key;
    Value val;
};

但hashtable把 value type 作为第一个泛型类型参数,我们看到的实现可能是这样的

template <class Value, class Key, class HashFcn,
         class ExtractKey, class EuqalKey,
         class Alloc>
class hashtable {
    typedef __hashtable_node<Value> node;
    // ...
};

看到了吗?Value Type 在第一位

这个是内部的底层实现机制,类似 map<K, V>set<V> 中的RB_Tree,这样写的好处是可以方便来拓展,即变化为 unordered_mapunordered_set

对与第一个偏特化参数是肯定要有的,set里面只有value,保证值不重复,但没有key,所以把value参数作为模板第一个参数,也是一个非常好的技巧
可以参考一下hash_set和hash_map的定义

// hash_set
// here change to v template
template <class Value,
         class HashFcn = hash<Key>, // std::hash
         class EqualKey = equal_to<Key>,
         class Alloc = alloc>
class hash_set {
private:
    typedef hashtable<Value, Value, HashFcn, identity<Value>,
                      EqualKey, Alloc> ht;
    ht rep;
};

// hash_map
// here change to k, v template

template <class Key,
         class T,
         class HashFcn = hash<Key>, // std::hash
         class EqualKey = equal_to<Key>,
         class Alloc = alloc>
class hash_map {
private:
    typedef hashtable<pair<const Key, T>, Key, HashFcn,
                      select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
    ht rep; // base is hashtable
};

插入

unordered_set, unordered_map里面使用的是 insert_unique 来保证不重复插入

unordered_multiset, unordered_multimap里面使用的是 insert_equal 来保证允许重复插入

Hash Function 算法实现

所有的hash值是依赖一个hash的struct,或者说仿函数(functors)来实现的

template <class Key> struct hash { };
inline size_t __stl_hash_string(const char* s) {
    unsigned long h = 0;
    for ( ; *s; ++s)
        h = 5*h + *s;
    return size_t(h);
}

__STL_TEMPLATE_NULL struct hash<const char*> {
    size_t operator()(const char* s) const { return _stl_hash_string(s); }
};

这里拿const char *类型举例,所有的基本类型,比如字符串,int,long等等都会用traits机制作偏特化处理,因为int、long这种类型很简单,可以直接转化为size_t来实现hashkey,这就是SGI的一个实现版本

我们来看看FreeSoftware的实现


template<size_t>
struct _Fnv_hash_base {
    template<typename _Tp>
    static size_t hash(const _Tp* __ptr, size_t __clength) {
        size_t __result = 0;
        const char* __cptr = reinterpret_cast<const char*>(__ptr);
        for (; __clength; --__clength)
            __result = (__result * 131) + *__cptr++;
        return __result;
    }
};


template<>
struct _Fnv_hash_base<4> {
    template<typename _Tp>
    static size_t hash(const _Tp* __ptr, size_t __clength) {
        size_t __result = static_cast<size_t>(2166136261UL);
        const char* __cptr = reinterpret_cast<const char*>(__ptr);
        for (; __clength; --__clength) {
            __result ^= static_cast<size_t>(*__cptr++);
            __result *= static_cast<size_t>(16777619UL);
        }
        return __result;
    }
};

template<>
struct _Fnv_hash_base<8> {
    template<typename _Tp>
    static size_t
    hash(const _Tp* __ptr, size_t __clength) {
        size_t __result = static_cast<size_t>(14695981039346656037ULL);
        const char* __cptr = reinterpret_cast<const char*>(__ptr);
        for (; __clength; --__clength) {
            __result ^= static_cast<size_t>(*__cptr++);
            __result *= static_cast<size_t>(1099511628211ULL);
        }
        return __result;
    }
};

struct _Fnv_hash : public _Fnv_hash_base<sizeof(size_t)> {
    using _Fnv_hash_base<sizeof(size_t)>::hash;
    template<typename _Tp>
      static size_t
      hash(const _Tp& __val) { return hash(&__val, sizeof(__val)); }
};

这个算法用sizeof(size_t)作偏特化,这个应该就会利用值偏特化而不是利用size_t类型,所以可以看到上面偏特化参数都是4,8等,针对了不同参数类型的长度,比如float是4,double是8,那么float按照以4偏特化的函数进行hash,double按照8的版本hash。

如果你想了解reinterpret_cast到底干了什么,你可以试试下面这段我写的代码的输出

double value = 3.14; // test value
size_t len = sizeof(value);
const char *str = reinterpret_cast<const char *>(&value); // cast to a pointer
for (int i = 0; i < len; i++) {
    cout << static_cast<size_t>(*str++) << endl;
}

那个与运算和乘法就类似与上面SGI版本给字符串做hash的过程,把他变成一个非常大的size_t的值,来代表一个值,避免了大量冲突碰撞

用户自定义hasher


class A { };

namespace std {
    template <> struct hash<A> {
        size_t operator()(const A & x) const {
          /* your code here, e.g. "return hash<int>()(x.value);" */
          return 3;
        }
    };
};

int main() { _
    std::hash<A> h;
    A obj;
    cout << h(obj) << endl;
    return 0;
}