hashmap C++实现分析_c++ hashmap

一、简介

Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。

在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。

本文介绍的C++ hashmap，是一个缓存用的hash_map，实现模仿自Java的HashMap，做了一些改造和精简。

特点：无读锁， 低写锁， 不删除只添加/更新， 桶不扩容， 按经验值初始化桶大小， 性能取决于hash算法和桶大小。

二、数据结构

1、哈希

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

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

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

2、哈希表

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

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

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

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

对于某个元素，我们通过哈希算法，根据元素特征计算元素在数组中的下标，从而将元素分配、插入到不同的链表中去。在查找时，我们同样通过元素特征找到正确的链表，再从链表中找出正确的元素。

3、HashMap 的数据结构　　　　　　　　　　　　　

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

三、几个核心问题

1. 找下标：如何高效运算以及减少碰撞

当我们拿到一个hashCode之后，需要将整型的hashCode转换成链表数组中的下标，比如数组大小为n，则下标为：

index = hashCode % n;

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

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

index = hashCode & (n-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)

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

}

#endif /* cache_hash_func_H__ */

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

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

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

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

举个例子，有一个Key值，假设经过简单的hashcode后，得到的值为“01011000110101110011111010011011”，如果当前数组的大小为16，在不进行扰动计算的情况下，他最终得到的index结果值为11。

由于15的二进制扩展到32位为“0000000000000000 0000000000001111”，所以，一个数字在和他进行按位与操作的时候，前28位无论是什么，计算结果都一样：

hashCode	hashCode&00001111
0101100011010111 0011111010011011	11
0010000000000000 0011111010011011	11
0000000000000000 0011111010011011	11

而经过扰动计算之后，之前会产生冲突的两个hashcode，最终得到的index的值不一样了，即使是高位的不同，也会造成最终结果的不同。

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

全网把Map中的hash()分析的最透彻的文章，别无二家。

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

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