浅谈哈希表

前言

最近，在启动一块嵌入式 Linux 开发板时，发现，同一份 uboot，从 SD 卡启动，和从 EMMC 启动，产生的效果不一样。最后发现是这两种存储介质中 uboot 的环境变量不一样。
遂去研究 uboot 环境变量存储机制

• 存储在 flash 中
• 存储在内存中

在 flash 中是以字符串的形式存放的。而在内存中，为了命令检索高效，是存储在哈希表（HashTable）中的。
哈希！了解，但只了解一点点。今天再次碰上了，就进一步了解下。

哈希表的作用

假设有一个长度为 100 的整型数组，数组中的每个元素的值也都是 100 以内，给出一个小于 100 的整数，你能以最快的速度告诉我，这个整数在数组中出现几次吗？
这里使用哈希表就是一个比较好的办法

创建一个长度为 100 的整型数组 h 作为哈希表，遍历待测数组 a，以待测数组中元素的值作为哈希表的下标，如
a[0] = 3，则 h[3]++；
a[1] = 8，则 h[8]++；
…
最后，哈希表中就记录了每个数字出现的次数，这时候有人来问，整数 x 在数组 a 中出现了几次，你就直接返回 h[x] 的值就行了。比你挨个遍历数组 a，比对是否等于 x，最后记录相等的次数，要快的多吧。
这只是一个简单的哈希表例子，实际应用中要比这复杂不少，数据类型也不是简单的整数类型，不过核心思想就是：

通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。

uthash

研究哈希表可以使用 uthash 这个开源项目，据说这份代码已经被集成到最新的 GCC 了，可见其代码之优秀。
uthash 所有的代码都是用宏实现的，总共 6 个 .h 文件，所以你想使用 uthash 时，只要包含这些头文件就可以了。

感受

先直观感受下其查找的速度
（查找 0-99999 这 10 万个整数是否在目标数组中）
test10_2.c（传统双重循环遍历查找法）

#include 
#include 
#include 

int main()
{
	int i;
	int j;
	clock_t start, stop;
	double duration;
	int *a = malloc(sizeof(int) * 100000);

	for (i = 0; i < 100000; i++) {
		a[i] = i;
	}

	start = clock();
	/*--------------------------------*/
	for (i = 0; i < 100000; i++) {
		for (j = 0; j < 100000; j++) {
			if (i == a[j]) {
				break;
			}
		}
	}
	/*--------------------------------*/

	stop = clock();
	duration = (double)(stop - start) / 1000000;
	printf("%lf s\n", duration);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

test10_1.c（哈希表查找法）

#include 	/* printf */
#include  /* malloc */
#include 
#include "uthash.h"

typedef struct example_user_t {
	int id;
	UT_hash_handle hh;
} example_user_t;

int main()
{
	int i;
	example_user_t *user, *tmp, *users = NULL;
	clock_t start, stop;
	double duration;

	/* create elements */
	for (i = 0; i < 100000; i++) {
		user = (example_user_t *)malloc(sizeof(example_user_t));
		if (user == NULL)
			exit(-1);

		user->id = i;
		HASH_ADD_INT(users, id, user);
	}

	start = clock();
	/*--------------------------------*/
	for (i = 0; i < 100000; i++) {
		HASH_FIND_INT(users, &i, tmp);
	}
	/*--------------------------------*/

	stop = clock();
	duration = (double)(stop - start) / 1000000;
	printf("%lf s\n", duration);

	HASH_CLEAR(hh, users);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

运行

$ ./test10_2
9.571326 s
$
./test10_1
0.022954 s
1
2
3
4
5

传统查找法耗时 9.5s，哈希查找法耗时 0.02s，可见哈希在查找方面的优越性。

分析源码

test10.c

#include 	/* printf */
#include  /* malloc */
#include "uthash.h"

typedef struct example_user_t {
	int id;
	UT_hash_handle hh;
} example_user_t;

int main()
{
	int i;
	example_user_t *user, *tmp, *users = NULL;

	/* create elements */
	for (i = 0; i < 30; i++) {
		user = (example_user_t *)malloc(sizeof(example_user_t));
		if (user == NULL) {
			exit(-1);
		}
		user->id = i;
		HASH_ADD_INT(users, id, user);
	}

	i = 3;
	HASH_FIND_INT(users, &i, tmp);
	printf("%d %s in hh\n\n", i, (tmp != NULL) ? "found" : "not found");

	i = 5;
	HASH_FIND_INT(users, &i, tmp);
	printf("%d %s in hh\n\n", i, (tmp != NULL) ? "found" : "not found");

	i = 7;
	HASH_FIND_INT(users, &i, tmp);
	printf("%d %s in hh\n\n", i, (tmp != NULL) ? "found" : "not found");

	i = 1007;
	HASH_FIND_INT(users, &i, tmp);
	printf("%d %s in hh\n", i, (tmp != NULL) ? "found" : "not found");

	HASH_CLEAR(hh, users);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

将 1 - 30 这 30 个整数添加到哈希表，然后查询 3、5、7、1007 是否在哈希表中
运行

$ ./test10
3 found in hh
5 found in hh
7 found in hh
1007 not found in hh
1
2
3
4
5

加点打印，窥探其实现机理。

_ha_hashv = 0x2a333225
_ha_hashv = 0x6217f7a5
_ha_hashv = 0x6392f77c
_ha_hashv = 0xb68ef0e4
_ha_hashv = 0xdb3b8e5
_ha_hashv = 0x46fd8a31
_ha_hashv = 0x45f2400e
_ha_hashv = 0xb33656fa
_ha_hashv = 0x9d13c292
_ha_hashv = 0x74401341
_ha_hashv = 0x72f8f9ee
_ha_hashv = 0x36b478b8
_ha_hashv = 0xcc635388
_ha_hashv = 0x3fe7d7fc
_ha_hashv = 0x4042a413
_ha_hashv = 0x5615360e
_ha_hashv = 0x1006120
_ha_hashv = 0x48b34b17
_ha_hashv = 0x49fbfa2e
_ha_hashv = 0xd5e8b63d
_ha_hashv = 0xb0aec8fc
_ha_hashv = 0xcf292f65
_ha_hashv = 0xc8cee813
_ha_hashv = 0x8436b233
_ha_hashv = 0xd6af3c42
_ha_hashv = 0x6a16ee6b
_ha_hashv = 0x7288f523
_ha_hashv = 0x848fa6f1
_ha_hashv = 0x29f27f7f
_ha_hashv = 0x8168fce7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

在将 1-30 这 30 个数字添加到哈希表时，分别对这 30 个数做了哈希 HASH_VALUE()，得到上面这 30 个哈希值。
将这 30 个值放入 32 个容器中，注意不是随便放置，是按照哈希值放置的，比如 3 对应的哈希值为 _ha_hashv = 0xb68ef0e4，将其和 0x1F 按位与，得到 4，就把 3 存入第 4 个容器中。
在查找 3 是，再次对 3 这个值做哈希，同样会得到 0xb68ef0e4 这个哈希值，和 1F 按位与，得到 4，就去第四个容器中寻找，由于在这 30 个值中，只有 3 会存放在第 4 个容器中，所以一下子就找到了。
如果有两个值存放于同一个容器中怎么办呢？比方说 5 和 27，两者的哈希值分别为 0x46fd8a31 和 0x848fa6f1，和 1F 按位与，都等于 0x11，则这两个值都要存入 0x11 也就是第 17 个容器（这就是哈希表冲突问题）。没关系，在 17 这个容器中再放置两个小容器，分别存放 5 和 27。这样，在查找时，先通过哈希值确定大容器的位置 17，再去 17 这个容器中遍历 2 个小容器，这样查找 2 次也就得到结果了，总比查找 30 次快得多吧。uthash 实现小容器的方式是链表。
上面是存放 30 个值的情况，出现了两个值存入一个容器的冲突情况，出现冲突就会降低查找效率。可想而知，如果存放 300 个值，容器就 32 个，会有更多冲突，查找效率就会下降，那要怎么解决这个问题呢？uthash 采用的办法就是扩充容器数量，当样本数量达到某个阈值时，就会触发容器数量扩充，比方说样本数量为 300 时，容器数量就由 32 扩充到了 64，这样就可以一直保证哈希表的查找效率不降低。

源码地址

https://github.com/troydhanson/uthash.git