哈希map详解（附代码）
1.问题场景
我们的某个系统目前是在一个老旧的平台上运行的，最近处理的数据量有点大，导致数据查找性能大幅下降。
由于平台比较老旧，编译器版本很低，使用标准库中的hash_map也就别想了。因此我们想着自己实现一个简易的，专用的hash_map，来达到优化查找性能的目的。
文章的后面附的有代码，核心代码只有不到100行，供您参考。
2.哈希容器的两个要点
a) 散列函数
散列函数的作用是，将key映射为一个value的存储地址。
最简单的映射方法是，将key直接映射为一个数组下标。
这种映射方法速度极快，但是并不适用于所有场景。比如key的取值范围特别大，要覆盖这个范围的话就需要一个特别大的数组，内存浪费很严重。
因此，需要一个散列函数，将key映射成一个存储地址，降低所需的存储空间。
散列函数通常有这样几种类型：
- 除余法：即将key与存储地址范围（比如数组的长度）取模，简单有效
- 乘余取整法：让key乘以一个小数D（0<D<1）后，取小数部分，然后在用整数N乘以这个值，取整数部分
- 平方取中法：先求key的平方（目的是扩大相近的数值的差别），然后根据存储地址范围，取中间的几位数作为存储地址（因为一个乘积的中间几位数与乘数的每一数位都相关，所以由此产生的散列地址较为均匀）
- 数值分析法：根据数值的特征（比如分布概率）设定存储地址
- 基数转换法：将key看成某一进制的数，转换成另外一个进制的数，取中间几位作为散列地址
- 折叠法：对于位数很多的key，可以将其分割成位数相同的几个部分，将他们叠加后作为散列地址
散列函数选择的原则是，让散列地址的分布，尽量均匀，从而降低冲突概率。
b)冲突处理
冲突是指，两个key映射到同一个存储地址。
我们不喜欢冲突，因为冲突会后要再次进行查找，直到找到真正的元素。这会降低查找效率。
然而冲突又是常见的，工作良好的散列函数，能尽量降低冲突概率，但很难消除冲突。只有在某些很特殊的场景下， 才能实现无冲突。
常见的冲突处理方法有如下几种：
1.分离链表法
即从冲突的位置拉出一个链表，存放冲突的元素（如下图）
2.开放定址法
即用表本身的空闲空间来存放冲突元素。
常见的做法有四种：
- 线性探查法：从冲突位置，每次+1寻找下一个元素，该方法容易产生聚集
- 二次探查法：从冲突位置，每次+1^2、2^2、3^2…寻找下一个元素，该方法比线性探查法要好很多，但是还是有可能产生聚集。
- 随机探查法：冲突后随机寻找地址空间，该方法不可控
- 双散列探查法：冲突后使用第二个散列函数做跳步，寻找下一个位置，该方法对第二个散列函数要求很高，否则会引起灾难性的后果
3.参考实现方案
我们这里仅讨论冲突处理方法。
方案1：改进后的二次探查法
二次探查法如果能保证hash桶的个数为质数，且容器负载系数在0.5以下（即保证容器实际容纳的元素个数不到容器容量的一半，超过后扩大容器容量重新整理），则可保证新插入元素所需的探查次数不超过2（据说数学上是可以证明的）。
GCC的STL使用的就是这种方法。
方案2：分离链表法
只要散列够平均，链表就能足够短，性能就能足够高。
SGI的STL就是采用的分离链表法。
4.我们的方案
a) 方案选择
我们的应用场景有如下特点：
- key的范围足够大，而且足够随机
- 能够保证容器负载系数很低，因此不涉及整理问题
- 要求代码必须简单易懂
- 要求尽量不使用动态内存
关于散列函数，根据第一条就可确定，除余法就能满足要求。
关于冲突处理，二次探查和分离链表感觉差不多，但我们最终我们选择的是分离链表法。原因有二：
- 简单的二次探查法实测效果并不好，要想让二次探查法发挥出威力，还得对跳步算法做优化，实现起来比较复杂
- 分离链表法简单易懂，实测效果好（桶深度，即链表长度不超过5）
b) 参考代码
x_hash_map.h
#ifndef X_HASH_MAP_H_
#define X_HASH_MAP_H_
//hash_map中的元素
typedef struct x_hmap_elem_t_tag
{
long key;
long val;
long next; // 指向下一个元素
} x_hmap_elem_t;
typedef struct x_hash_map_t_tag
{
int bkt_size; //桶元素，也是元素集合的容量
x_hmap_elem_t *p_elems; //所有元素集合（数组，顺序使用）
int cur_pos; //上述集合中，下一个可用元素的下标
long *p_bkts; //各个桶的首元素（数组）
} x_hash_map_t;
//新建一个hash_map（需指定最大容量）
x_hash_map_t* alloc_hash_map(long max_elems);
//寻找key对应的value，失败返回-1，否则返回value
long find_hmap_elem(x_hash_map_t *p_map, long key);
//插入一个元素（调用时保证元素不存在）
int insert_hmap_elem(x_hash_map_t *p_map, long key, long value);
#endifx_hash_map.c
#include "x_hash_map.h"
#include <memory.h> // for memset()
#include <stdlib.h> // for NULL
//预定义的素数表，定义来自：gcc-4.8.5-libstdc++-v3/src/shared/hashtable-aux.cc
const unsigned long k_prime_list[] =
{ 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, 37ul, 41ul,
43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, 83ul, 89ul, 97ul,
103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, 157ul, 167ul, 179ul,
193ul, 199ul, 211ul, 227ul, 241ul, 257ul, 277ul, 293ul, 313ul, 337ul,
359ul, 383ul, 409ul, 439ul, 467ul, 503ul, 541ul, 577ul, 619ul, 661ul,
709ul, 761ul, 823ul, 887ul, 953ul, 1031ul, 1109ul, 1193ul, 1289ul,
1381ul, 1493ul, 1613ul, 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul,
2753ul, 2971ul, 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul,
5503ul, 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, 19183ul,
20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, 33223ul, 35933ul,
38873ul, 42043ul, 45481ul, 49201ul, 53201ul, 57557ul, 62233ul, 67307ul,
72817ul, 78779ul, 85229ul, 92203ul, 99733ul, 107897ul, 116731ul,
126271ul, 136607ul, 147793ul, 159871ul, 172933ul, 187091ul, 202409ul,
218971ul, 236897ul, 256279ul, 277261ul, 299951ul, 324503ul, 351061ul,
379787ul, 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, 1056323ul,
1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, 1693859ul,
1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, 2716249ul,
2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, 4355707ul,
4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, 6984629ul,
7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, 11200489ul,
12117689ul, 13109983ul, 14183539ul, 15345007ul, 16601593ul, 17961079ul,
19431899ul, 21023161ul, 22744717ul, 24607243ul, 26622317ul, 28802401ul,
31160981ul, 33712729ul, 36473443ul, 39460231ul, 42691603ul, 46187573ul,
49969847ul, 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, 1725587117ul,
1866894511ul, 2019773507ul, 2185171673ul, 2364114217ul, 2557710269ul,
2767159799ul, 2993761039ul, 3238918481ul, 3504151727ul, 3791104843ul,
4101556399ul, 4294967291ul, 6442450933ul, 8589934583ul, 12884901857ul,
17179869143ul, 25769803693ul, 34359738337ul, 51539607367ul,
68719476731ul, 103079215087ul, 137438953447ul, 206158430123ul,
274877906899ul, 412316860387ul, 549755813881ul, 824633720731ul,
1099511627689ul, 1649267441579ul, 2199023255531ul, 3298534883309ul,
4398046511093ul, 6597069766607ul, 8796093022151ul, 13194139533241ul,
17592186044399ul, 26388279066581ul, 35184372088777ul, 52776558133177ul,
70368744177643ul, 105553116266399ul, 140737488355213ul,
211106232532861ul, 281474976710597ul, 562949953421231ul,
1125899906842597ul, 2251799813685119ul, 4503599627370449ul,
9007199254740881ul, 18014398509481951ul, 36028797018963913ul,
72057594037927931ul, 144115188075855859ul, 288230376151711717ul,
576460752303423433ul, 1152921504606846883ul, 2305843009213693951ul,
4611686018427387847ul, 9223372036854775783ul, 18446744073709551557ul,
18446744073709551557ul };
x_hash_map_t* alloc_hash_map(long max_elems)
{
//找一个【大于等于元素个数】的【最小素数】作为桶的个数
int prim_idx = 0;
while (k_prime_list[prim_idx] < max_elems)
++prim_idx;
//新建一个map
x_hash_map_t *p_map = (x_hash_map_t*) malloc(sizeof(x_hash_map_t));
p_map->bkt_size = k_prime_list[prim_idx];
p_map->cur_pos = 0;
p_map->p_elems = (x_hmap_elem_t*) malloc(
sizeof(x_hmap_elem_t) * p_map->bkt_size);
p_map->p_bkts = (long*) malloc(sizeof(long) * p_map->bkt_size);
for (long i = 0; i < p_map->bkt_size; ++i)
p_map->p_bkts[i] = -1; //-1表示桶是空的
return p_map;
}
long find_hmap_elem(x_hash_map_t *p_map, long key)
{
//确定一个桶，取出首元素指针
long cur_idx = p_map->p_bkts[key % p_map->bkt_size];
while (cur_idx >= 0) //遍历查找桶中元素
{
if (p_map->p_elems[cur_idx].key == key) //找到
return p_map->p_elems[cur_idx].val;
cur_idx = p_map->p_elems[cur_idx].next;
}
return -1;
}
int insert_hmap_elem(x_hash_map_t *p_map, long key, long value)
{
//新建元素
long new_idx = p_map->cur_pos;
p_map->p_elems[new_idx].key = key;
p_map->p_elems[new_idx].val = value;
//插入桶元素链表的头部
p_map->p_elems[new_idx].next = p_map->p_bkts[key % p_map->bkt_size];
p_map->p_bkts[key % p_map->bkt_size] = new_idx;
++p_map->cur_pos;
return 0;
}test.c
#include "x_hash_map.h"
#include <assert.h>
#include <stdio.h>
/*
gcc -o x_hash_map.o -c x_hash_map.c -Wall -m64 -g -O3
gcc -o test.o -c test.c -Wall -m64 -g -O3
gcc -o test test.o x_hash_map.o -Wall -m64 -g -O3
*/
#define TEST_MAX 30000000
int main()
{
x_hash_map_t *p_map = alloc_hash_map(TEST_MAX);
for(long i=0;i<TEST_MAX;++i)
{
if(i % 10000000 == 0)
printf("insert %ld\n", i);
insert_hmap_elem(p_map, i, i+1);
}
for(long i=0;i<TEST_MAX;++i)
{
if(i % 10000000 == 0)
printf("find %ld\n", i);
long val = find_hmap_elem(p_map, i);
assert(val == i+1);
}
return 0;
}5.参考资料
- 《STL源码剖析》-侯捷
- 《初等数论及其应用》-Rosen