hashmap C++实现分析及std::unordered_map拓展

今天想到哈希函数，好像解决冲突的只了解了一种链地址法而且也很模糊，就查了些资料复习一下

1、哈希
Hash 就是把任意长度的输入，通过哈希算法，变换成固定长度的输出（通常是整型），该输出就是哈希值。

这种转换是一种压缩映射，也就是说，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，因此不能从散列值来唯一地确定输入值。

简单的说，哈希就是一种将任意长度的消息压缩到某一固定长度的信息摘要函数。

2、哈希表
2.1哈希表有多种不同的实现，其核心问题是如何解决冲突，即不同输入产生相同输出时，应该如何存储。

最经典的一种实现方法就是拉链法，它的数据结构是链表的数组：

数组的特点是：寻址容易，插入和删除困难。

链表的特点是：寻址困难，插入和删除容易。

对于某个元素，我们通过哈希算法，根据元素特征计算元素在数组中的下标，从而将元素分配、插入到不同的链表中去。在查找时，我们同样通过元素特征找到正确的链表，再从链表中找出正确的元素。
2.2 还有种方法是开放地址法，用开放地址处理冲突就是当冲突发生时，形成一个地址序列，沿着这个序列逐个深测，直到找到一个“空”的开放地址，将发生冲突的关键字值存放到该地址中去。这里就不详细介绍了

3、HashMap 的数据结构　　　　　　　　　　　　　
HashMap 实际上就是一个链表的数组，对于每个 key-value对元素，根据其key的哈希，该元素被分配到某个桶当中，桶使用链表实现，链表的节点包含了一个key，一个value，以及一个指向下一个节点的指针。

三、几个核心问题
1. 找下标：如何高效运算以及减少碰撞
当我们拿到一个hashCode之后，需要将整型的hashCode转换成链表数组中的下标，比如数组大小为n，则下标为：

index = hashCode % n;
1
这里的取模运算效率较低，如果能够使用位运算(&)来代替取模运算(%)，效率将有所提升。位运算直接对内存数据进行操作，不需要转成十进制，处理速度非常快。

我们可以使用以下方法来实现：

index = hashCode & (n-1);
1
hashCode 与 n-1 进行按位与操作，得到的结果必定是小于n的。

但是，以上按位与的操作跟取模运算并不等价，这可能会带来index分布不均匀问题。

举个例子，假设数组大小为15，则hash值在与14（即 1110）进行&运算时，得到的结果最后一位永远都是0，即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。这样，空间的减少会导致碰撞几率的进一步增加，从而就会导致查询速度慢。

如果能够保证按位与的操作跟取模运算是等价的，那么不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。

那么，为什么如何实现位运算(&)跟取模运算(%)的等价呢？我们看以下等式：

X % 2^n = X & (2^n – 1)
1
2^n表示2的n次方，也就是说，一个数对2^n取模 == 一个数和(2^n – 1)做按位与运算 。

假设n为3，则2^3 = 8，表示成二进制就是1000。2^3-1 = 7 ，表示成二进制就是0111。

此时X & (2^3 – 1) 就相当于取X的二进制的最后三位数。

从二进制角度来看，X / 2^n 相当于 X >> n，即把X右移n位，被移掉的部分(后n位)，则是X % 2^n，也就是余数。

因此，计算 X % 2^n，实际上就是要获取 X 的后n位。

我们注意到，2^n 的后 n+1 位都是1，其余为0，于是 2^n-1 的后 n 位都是1，其余为0。

因此，X 跟 2^n-1 做按位与运算，将得到X 的后n位。

所以，只要保证数组的大小是2^n，就可以使用位运算来替代取模运算了。

因此，当拿到一个用户指定的数组大小时，我们总是会再做一层处理，以保证实际的数组大小为 2^n：

size_t getTableSize(size_t capacity) {
    // 计算超过 capacity 的最小 2^n 
    size_t ssize = 1;
    while (ssize < capacity) {
        ssize <<= 1;
    }
    return ssize;
}

2. 哈希策略：如何将元素均匀地分配到各个桶内

由于我们将使用key的hashCode来计算该元素在数组中的下标，所以我们希望hashCode是一个size_t类型。所以我们的哈希函数最首要的就是要把各种类型的key转换成size_t类型，以下是代码实现：

#ifndef cache_hash_func_H__
#define cache_hash_func_H__

#include <string>

namespace HashMap {

/**
 * hash算法仿函数
 */
template<class KeyType>
struct cache_hash_func {
};

inline std::size_t cache_hash_string(const char* __s) {
    unsigned long __h = 0;
    for (; *__s; ++__s)
        __h = 5 * __h + *__s;
    return std::size_t(__h);
}

template<>
struct cache_hash_func<std::string> {
    std::size_t operator()(const std::string & __s) const {
        return cache_hash_string(__s.c_str());
    }
};

template<>
struct cache_hash_func<char*> {
    std::size_t operator()(const char* __s) const {
        return cache_hash_string(__s);
    }
};

template<>
struct cache_hash_func<const char*> {
    std::size_t operator()(const char* __s) const {
        return cache_hash_string(__s);
    }
};

template<>
struct cache_hash_func<char> {
    std::size_t operator()(char __x) const {
        return __x;
    }
};

template<>
struct cache_hash_func<unsigned char> {
    std::size_t operator()(unsigned char __x) const {
        return __x;
    }
};

template<>
struct cache_hash_func<signed char> {
    std::size_t operator()(unsigned char __x) const {
        return __x;
    }
};

template<>
struct cache_hash_func<short> {
    std::size_t operator()(short __x) const {
        return __x;
    }
};

template<>
struct cache_hash_func<unsigned short> {
    std::size_t operator()(unsigned short __x) const {
        return __x;
    }
};

template<>
struct cache_hash_func<int> {
    std::size_t operator()(int __x) const {
        return __x;
    }
};

template<>
struct cache_hash_func<unsigned int> {
    std::size_t operator()(unsigned int __x) const {
        return __x;
    }
};

template<>
struct cache_hash_func<long> {
    std::size_t operator()(long __x) const {
        return __x ^ (__x >> 32);
    }
};

template<>
struct cache_hash_func<unsigned long> {
    std::size_t operator()(unsigned long __x) const {
        return __x ^ (__x >> 32);
    }
};

}

可以看到，上面实现的hash函数比较随意，难以产生较为均匀（即冲突少）的hashCode。

为了防止质量低下的hashCode()函数实现，我们使用getHash()方法对一个对象的hashCode进行重新计算：(下面这个就是hash方法的精髓)

size_t getHash(size_t h) const {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

这段代码对key的hashCode进行扰动计算，防止不同hashCode的高位不同但低位相同导致的hash冲突。也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。

getHash的更多实现解析可参考：

全网把Map中的hash()分析的最透彻的文章，别无二家。http://www.hollischuang.com/archives/2091

3. 多线程：如何实现无读锁，低写锁
在数据结构上，我们使用多个桶来存放数据，当哈希足够均匀时，冲突将比较少。当多线程操作不同的链表时，完全不需要加锁，但是如果操作的是同一个链表，则需要加锁来保证正确性。因此多个桶的设计，从降低锁的粒度的角度，已经减少了很多不必要的加锁操作。

同时，单向链表的使用，给我们带来了一个意想不到的好处：多个读线程和一个写线程并发操作不会出问题。

假设链表中目前包含A和B节点，此时要在它们之间插入C节点，步骤如下：
1. 创建C节点
2. 将C的next指向B
3. 将A的next指向C

在完成1和2两步之后，读线程查询链表只能看到A和B，链表是完整的。
在第3 步，修改next指针的操作是原子的，因此无论什么时候，读线程看到的链表都是完整的，数据没有丢失。因此读操作是不需要加锁的。

读操作代码：

entry_ptr get(const KeyType & key) {
if (m_count != 0) { // read-volatile
for (entry_ptr entry = m_head; entry; entry = entry->getNext()) {
if (entry->equalsKey(key)) {
return entry;
}
}
}
static entry_ptr EMPTY = NULL;
return EMPTY;
}

当多个线程同时执行插入时，由于next的修改可能会被覆盖，从而造成内存泄漏，因此写需要加锁。（当然这里也可以考虑CAS无锁化，效率方面看应用场景）

写操作代码：

//返回值表示key是否已经存在, 已存在返回true
bool set(const KeyType & key, const ValueType & value) {
entry_ptr entry = get(key);
// 如果key已经存在，直接修改
if (entry) {
entry->setValue(value);
return true;
}
LockType lock(m_lock);
// double check，if之后，加锁之前，entry可能被赋值了
// 因此加完锁要再检查一遍
entry = get(key);
if (entry) {
entry->setValue(value);
return true;
}
m_head = new entry_type(key, value, m_head);
++m_count;
return false;
}

由于我们的实现中，不对桶进行扩容，不支持删除，因此简化很多。对于链表新增的节点，均插入到头部即可。
第二部分，std::unordered_map实现自定义key

1. unordered_map的定义
下面是unordered_map的官方定义。

template<class Key,
class Ty,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, Ty> > >
class unordered_map;
> class unordered_map

第1个参数，存储key值。

第2个参数，存储mapped value。

第3个参数，为哈希函数的函数对象。它将key作为参数，并利用函数对象中的哈希函数返回类型为size_t的唯一哈希值。默认值为std::hash<key>。

第4个参数，为等比函数的函数对象。它内部通过等比操作符’=='来判断两个key是否相等，返回值为bool类型。默认值是std::equal_to<key>。在unordered_map中，任意两个元素之间始终返回false。

2. 问题分析
对于unordered_map而言，当我们插入<key, value>的时候，需要哈希函数的函数对象对key进行hash，又要利用等比函数的函数对象确保插入的键值对没有重复。然而，当我们自定义类型时，c++标准库并没有对应的哈希函数和等比函数的函数对象。因此需要分别对它们进行定义。

因为都是函数对象，它们两个的实际定义方法并没有很大差别。不过后者比前者多了一个方法。因为等比函数的函数对象默认值std::equal_to<key>内部是通过调用操作符"=="进行等值判断，因此我们可以直接在自定义类里面进行operator==()重载（成员和友元都可以）。

因此，如果要将自定义类型作为unordered_map的键值，需如下两个步骤：

定义哈希函数的函数对象；

定义等比函数的函数对象或者在自定义类里重载operator==()。

3. 定义方法
本文所有案例在用g++编译时，需加上-std=c++11或者-std=c++0x；如果用VS编译，请选择2010年及以上版本。

为了避免重复，下文以讨论哈希函数的函数对象为主，参数4则是通过直接在自定义类里面对operator==()进行重载。

我们选一种实现

重载operator()的类

#include <iostream>
#include <string>
#include <unordered_map>
#include <functional>
using namespace std;

class Person{
public:
    string name;
    int age;

    Person(string n, int a){
        name = n;
        age = a;
    }

    bool operator==(const Person & p) const 
    {
        return name == p.name && age == p.age;
    }
};

struct hash_name{
    size_t operator()(const Person & p) const{
        return hash<string>()(p.name) ^ hash<int>()(p.age);// hash<string>()(p.name)就是求这个string对应hash值得方法
    }
};

int main(int argc, char* argv[]){
    unordered_map<Person, int, hash_name> ids; //不需要把哈希函数传入构造器
    ids[Person("Mark", 17)] = 40561;
    ids[Person("Andrew",16)] = 40562;
    for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
        cout << ii->first.name 
        << " " << ii->first.age
        << " : " << ii->second
        << endl;
    return 0;
}