哈希表通过一种最有效的检索方法–散列来查找元素, 一个哈希表通过一个哈希函数, 在所有可能的键与槽位之间建立一张映射表. 理想的状态就是把不同键生成的哈希值互不相同, 但这会使得哈希表里的条目变得巨大, 而且条目中可能绝大多数是无用的.

所以, 通常哈希函数把一些不同的键映射到表中相同的槽位上, 这就会产生冲突, 一个好的哈希函数要最大限度的地减少冲突

链式哈希表(Chained Hash Table)

链式哈希表从根本上来说是由一组链表构成, 每个链表可以看成一个"桶(bucket)”

链式哈希表在插入元素时, 将其键传入一个哈希函数h(k), 函数通过散列的方式告知元素属于哪个"桶”,然后在相应的链表头插入元素

在查找或删除元素时, 用同样的方式先找到元素的"桶”, 然后遍历相应的链表

每个链表并不限制包含元素的个数, 但是表如果变得很大, 性能就会变得很低

链式哈希表

冲突的发生

当两个键通过哈希函数到表里相同的位置时, 这两个键就产生的冲突.

链式哈希表当产生冲突时, 它就把元素放到冲突发生的"桶"中. 这就产生一个问题, 如果总是发生这样的冲突, 那么这个桶就会越来越大, 里面的元素越来越多

理想的情况是, 把元素平均和随机的分配到每一个"桶"中, 这种称为均匀散列(uniform hash). 实际情况只能是无限接近平均分配

一个重要的因素–负载因子(load factor)

a = n / m 其中, n是元素个数, m是"桶"的个数

最好的情况是每个链表的中的元素个数接近负载因子的数值

选择哈希函数

哈希函数h(k) = x将键k映射到哈希表中的x位置, 大多数的散列方法假设k设整数, 这样k能够很容易的以数学的方式修改, 使x更加均匀的分布在表中, 当k不是一个整数时, 我们需要将k转换为整数

  • 取余法: h(k) = k mod m

通常选择的m会是一个素数, 且不要太接近于 2 的幂, 同时还要考虑存储的限制和负载因子

  • 乘法: h(k) = m(kA mod 1), A(0<A<1)通常是 0.618 左右

这种方法对m的选择不像取余法中那么慎重

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/* 一个适用于处理字符串的哈希函数 */
/* hashpjw.c */

unsigned int hashpjw(const void *key)
{
    const char *ptr = key;
    unsigned int val = 0;
    unsigned int tmp;

    while (*ptr != '\0') {
        val = (val << 4) + *ptr;

        if (tmp = (val & 0xf0000000)) {
            val = val ^ (tmp >> 24);
            val = val ^ tmp;
        }
        ptr++;
    }
    /* PRIME_TBLSIZ 是实际的表的大小 */
    return val % PRIME_TBLSIZ;
}

链式哈希表头文件

 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
/** chtbl.h */
#ifndef CHTBL_H
#define CHTBL_H

#include <stdlib.h>
#include "list.h"

/* 链式哈希表结构 */
typedef struct CHTbl_ {
    /* "桶的个数" */
    int buckets;
    /* hash_func 是自定义传入的哈希函数 */
    int (*hash_func)(const void *key);
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    /* 元素数量 */
    int size;
    List *table;
}CHTbl;

/* 初始化哈希表 */
int chtbl_init(CHTbl *htbl, int buckets, int (*hash_func)(const void *key),
    int (*match)(const void *key1, const void *key2), void (*destroy)(void *data));
/* 销毁函数 */
void chtbl_destroy(CHTbl *htbl);
/* 插入数据 */
int chtbl_insert(CHTbl *htbl, const void *data);
/* 删除数据 */
int chtbl_remove(CHTbl *htbl, void **data);
/* 查找数据 */
int chtbl_lookup(const CHTbl *htbl, void **data);

#define chtbl_size(htbl) ((htbl)->size)

#endif

链式哈希表的实现

 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdlib.h>
#include <string.h>

#include "list.h"
#include "chtbl.h"

int chtbl_init(CHTbl *htbl, int buckets, int (*hash_func)(const void *key),
    int (*match)(const void *key1, const void *key2), void (*destroy)(void *data))
{
    /* 初始化所需要多少个链表, 即多少个"桶"的内存 */
    if ((htbl->table = (List *)malloc(sizeof(List) * buckets)) == NULL) {
        return -1;
    }

    htbl->buckets = buckets;
    /* 为每个链表设置销毁函数 */
    for (int i = 0; i < htbl->buckets; i++) {
        /* list_init(&htbl->table[i], destroy); */
        list_init(htbl->table + i, destroy);
    }

    htbl->hash_func = hash_func;
    htbl->match = match;
    htbl->destroy = destroy;
    /* 初始表长度 */
    htbl->size = 0;

    return 0;
}

void chtbl_destroy(CHTbl *htbl)
{
    for (int i = 0; i < htbl->buckets; i++) {
        list_destroy(htbl->table + i);
    }
    free(htbl->table);
    memset(htbl, 0, sizeof(CHTbl));
}

int chtbl_insert(CHTbl *htbl, const void *data)
{
    void *temp;
    int bucket, retval;

    temp = (void *)data;
    /* 不插入重复的数据 */
    if (chtbl_lookup(htbl, &temp) == 0) {
        return 1;
    }
    /* hash the key */
    bucket = htbl->hash_func(data) % htbl->buckets;
    if ((retval = list_ins_next(htbl->table + bucket, NULL, data)) == 0) {
        htbl->size++;
    }
    return retval;
}

int chtbl_remove(CHTbl *htbl, void **data)
{
    ListElmt *element, *prev;
    int bucket;
    /* 使用 hash 函数确认数据属于哪个"桶" */
    bucket = htbl->hash_func(*data) % htbl->buckets;
    prev = NULL;
    /* 在"桶"中查找, 即是查找链表 */
    for (element = list_head(htbl->table + bucket); element != NULL;
        element = list_next(element)) {
        if (htbl->match(*data, list_data(element))) {
            /* 如果查找到相同数据, 删除这个元素 */
            if (list_rem_next(htbl->table + bucket, prev, data) == 0) {
                htbl->size--;
                return 0;
            } else {
                return -1;
            }
        }
        prev = element;
    }
    return -1;
}

int chtbl_lookup(const CHTbl *htbl, void **data)
{
    ListElmt *element;
    int bucket;
    /* Hash the key. */
    bucket = htbl->(*data) % htbl->buckets;

    for (element = lsit_head(htbl->table + buckets); element != NULL;
        element = list_next(element)) {
        if (hb->match(*data, list_data(element))) {
            *data = list_data(element);
            return 0;
        }
    }
    return -1;
}

链式哈希表的应用: 符号表

在使用程序解析某种语法时, 为了能够更有效的管理程序中的符号信息, 通学使用一种叫做符号表的数据结构, 一般使用哈希表来实现. 对符号表进行插入数据时, 也即是向哈希表插入数据, 称为词法分析.

下面的例子是一个非常简单的词法分析器, 分析传入的字符串, next_token从输入istream中取得下一个字符串, 如果没有了, 就返回退出

假设输入的字符只有两种: 一种是数字, 另一种是数字之外的字符. 字符之间以空格隔开

 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
46
47
48
49
50
51
52
53
54
55
56
/* lex.c */
#include <stdlib.h>
#include <string.h>
#include "chtbl.h"

typedef enum Token_ {lexit, error, digit, other} Token;

Token lex(const char *istream, CHTbl *symtbl);

static char *next_token(const char *istream) {
    /* check next there is a token */
    /* return NULL; */
}

typedef struct Symbol_ {
    char *lexeme;
    Token token;
}Symbol;

Token lex(const char *istream, CHTbl *symtbl)
{
    Token token;
    Symbol *symbol;
    int length, retval, i;

    if ((symbol = (Symbol *)malloc(sizeof(Symbol))) == NULL) {
        return error;
    }
    /* next_token 返回下一个字符或者 NULL */
    if ((symbol->lexeme = next_token(istream)) == NULL) {
        /* 如果没有下一个词 */
        free(symbol);
        return lexit;
    }else {
        symbol->token = digit;
        length = strlen(symbol->lexeme);

        for (i = 0; i < length; i++) {
            /* -> 和 [] 同一运算级, 从左到右 */
            if (!isdigit(symbol->lexeme[i])) {
                /* 检查是否是数字 */
                symbol->token = other;
            }
        }
        memcpy(&token, &symbol->token, sizeof(Token));
        /* 将符号插入哈希表中 */
        if ((retval = chtbl_insert(symtbl, symbol)) < 0) {
            free(symbol);
            return error;
        } else if (retval == 1) {
            /* 符号已经存在于哈希表中 */
            free(symbol);
        }
    }
    return token;
}

开地址哈希表(Open-Addressed Hash Tables)

在链式哈希表中, 元素存放在每个地址的"桶"中, 而在开地址哈希表中, 元素存放在表本身

冲突解决

在开地址哈希表中, 探查这个表, 直到找到一个可以旋转元素的槽. 例如, 如果要插入一个元素, 我们探查槽位直到找一个空槽, 然后将元素插入些槽中. 如果要删除一个元素, 我们探查槽位直到定位到该元素或直到找一个空槽. 如果在找到元素之前找到一个空槽或遍历完所有槽位, 那么说明元素不在表中

需要进行过多少次探查后就停止探查取决于: 哈希表的负载因子和元素均匀分布程度

在开地址哈希表中a=n/m, 因为每个槽位至多能够容纳一个元素, 所以a总是小于等于 1, 假设进行均匀散列, 探查的槽位个数是1/(1-a), 明显的当表中负载因子越大, 所探查次就越多

线性探查

开地址哈希表中的一种简单的探查方法就是探查表中连续的槽位.

h(k, i) = (h<sup>'</sup>(k)+i) mod m 0 < i < m-1(m 是表中槽位个数), h'是一个辅助函数, 比如取余法函数

线性探查

双散列

最有效地探查开地址哈希表的方法之一, 就是通过求两个辅助哈希函数的哈希编码之和, 来得到最终的哈希编码值

h(h, i) = (h<sub>1</sub>(k) + i * h<sub>2</sub>(k)) mod m
h1和 h2分别是两个不两同的哈希辅助函数, 为了保证第二次访问任何一个槽之前, 其他所有槽都访问过了, 方法一是: m 必须是 2 次幂, 让 h2 返回一个奇数值; 另一种方法是选择 m 为一个素数, h2 返回值在 1 <= h2(k) <= m-1 之间

通常情况下, 令 h1(k) = k mod m, h2(k) = 1 + (k mod m'), 其中 m' 略小于 m, 类似 m-1, m-2. 双散列的优点是能够探查并产生较好的颁布, 缺点是必须限制 m 的值, 也是表的大小不变, 这样才能保证在一系列探查中访问表中所有槽之后才会再次探查任何槽

双散列

开地址哈希表头文件

 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
#ifndef OHTBL_H
#define OHTBL_H

#include <stdlib.h>

/* 开地址哈希表表结构, 使用双散列方法 */
typedef struct OHTbl_ {
    /* 表中槽位个数 */
    int positions;
    /* 一个哈希表初始化时, 空槽通常包含一个指向 NULL 的空指针
     * 当删除一个元素时, 不能将删除元素的数据指向 NULL, 这是由于当查找
     * 接下来的元素时, NULL 表明些槽位是空的, 随之探查过程将停止
     * 这样一个或多个元素可能被插入之前删除过元素的槽位中, 但实际指向数据还存在
     *
     * 所以当删除一个元素, 把该槽们标记为一个特殊的值, 来指明这个地址曾经删除一个元素
     *
     */
    void *vacated;
    /* 散列方法一 */
    int (*hash_f1)(const void *key);
    /* 散列方法二 */
    int (*hash_f2)(const void *key);
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    /* 表中元素数量 */
    int size;
    /* 槽位指针, 初始为 NULL, 插入数据后其指向数据 */
    void **table;
}OHTbl;
/* 初始化哈希表 */
int ohtbl_init(OHTbl *htbl, int positions, int (*hash_f1)(const void *key),
    int (*hash_f2)(const void *key2), int (*match)(const void *key1, const void *key2),
    void (*destroy)(void *data));
/* 销毁表 */
void ohtbl_destroy(OHTbl *htbl);
/* 插入数据 */
void ohtbl_insert(OHTbl *htbl, const void *data);
/* 删除数据 */
int ohtbl_remove(OHTbl *htbl, void **data);
/* 查找数据 */
int ohtbl_lookup(const OHTbl *htbl, void **data);
/* 哈希表大小 */
#define ohtbl_size(htbl) ((htbl)->size)

#endif

开地址哈希表的实现

  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
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* ohtbl.c */
#include <stdlib.h>
#include <string.h>
#include "ohtbl.h"

/* 元素辅助 */
static char vacated;
/* 初始化哈希表 */
int ohtbl_init(OHTbl *htbl, int positions, int(*hash_f1)(const void *key),
    int (*hash_f2)(const void *key), int (*match)(const void *key1, const void *key2),
    void (*destory)(void *data))
{
    int i;
    /* 为哈希表槽们指针申请内存 */
    if ((htbl->table = (void **)malloc(positions * sizeof(void *))) == NULL) {
        return -1;
    }
    /* 初始槽位大小 */
    htbl->positions = positions;
    /* 将每个槽位都初始为 NULL */
    for (i = 0; i < htbl->positions; i++) {
        htbl->table[i] = NULL;
    }
    /* 初始辅助指针 */
    htbl->vacated = &vacated;

    htbl->hash_f1 = hash_f1;
    htbl->hash_f2 = hash_f2;
    htbl->match = match;
    htbl->destroy = destroy;
    htbl->size = 0;
    return 0;
}
/* 销毁 */
void ohtbl_destroy(OHTbl *htbl)
{
    int i;
    if (htbl->destroy != NULL) {
        /* 遍历每个槽位, 如果槽为空, 并且槽位没有被标注过有元素插入, 销毁这个槽位 */
        for (i = 0; i < htbl->positions; i++) {
            if (htbl->table[i] != NULL && htbl->table[i] != htbl->vacated) {
                htbl->destroy(htbl->table[i]);
            }
        }
    }

    free(htbl->table);
    memset(htbl, 0, sizeof(OHTbl));
}
/* 插入元素 */
int ohtbl_insert(OHTbl *htbl, const void *data)
{
    void *temp;
    int position, i;
    /* 如果表的大小达到最大槽位数, 即哈希表已满, 无法再插入元素 */
    if (htbl->size == htbl->positions) {
        return -1;
    }
    /* 不插入相同的数据到表中 */
    temp = (void *)data;
    if (ohtbl_lookup(htbl, &temp) == 0) {
        return 1;
    }

    /* use double hashing to hash the key */
    for (i = 0; i < htbl->positions; i++) {
        /* 双散列方法查找槽位 */
        position = (htbl->hash_f1(data) + (i * htbl->hash_f2(data))) % htbl->positions;
        /* 如果槽位为 NULL 或者该槽位没有指向标记值则可以将数据插入到这个槽位中 */
        if (htbl->table[position] == NULL || htbl->table[position] == htbl->vacated) {
            /* 将槽位指向数据 */
            htbl->table[position] = (void *)data;
            htbl->size++;
            return 0;
        }
    }
    return -1;
}

int ohtbl_remove(OHTbl *htbl, void **data)
{
    int position, i;

    for (i = 0; i < htbl->position; i++) {
        position = (htbl->hash_f1(*data) + (i *htbl->hash_f2(*data))) % htbl->positions;

        if (htbl->table[position] == NULL) {
            /* 没有查找到数据 */
            return -1;
        } else if (htbl->table[position] == htbl->vacated) {
            /* 元素被标注为删除过, 继续查找是否有冲突产生过 */
            continue;
        } else if (htbl->match(htbl->table[position], *data)) {
            /* 查找到元素, 对比其中数据 */
            *data = htbl->table[position];
            htbl->table[position] = htbl->vacated;
            htbl->size--;
            return 0;
        }
    }
    return -1;
}

int ohtbl_lookup(const OHTbl *htbl, void **data)
{
    int position, i;

    for (i = 0; i < htbl->positions; i++) {
        position = (htbl->hash_f1(*data) + (i * htbl->hash_f2(*data))) % htbl->positions;
        if (htbl->table[position] == NULL) {
            return -1;
        } else if (htbl->match(htbl->table[position], *data)) {
            *data = htbl->table[position];
            return 0;
        }
    }
    return -1;
}