php内核hashtable

玩具代码, 拉链法解决HashTable冲突, 见笑了

hashtable.png

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
#include <stdlib.h>
#include <string.h>
typedef struct _ {
struct _ * next;
char *key;
char *value;
} Node;
#define HASH_TABLE_SIZE 100
Node * initNode(char *key, char *value) {
if (key == NULL || value == NULL) {
Node *node = (Node *)malloc(sizeof(Node));
node->key = NULL;
node->value = NULL;
node->next = NULL;
return node;
} else {
Node *node = (Node *)malloc(sizeof(Node));
node->key = (char *)malloc(strlen(key) + 1);
strcpy(node->key, key);
node->value = (char *)malloc(strlen(value) + 1);
strcpy(node->value, value);
node->next = NULL;
return node;
}
}
int times33(char *key, int key_len) {
int hash = 5381;
for(int i = 0; i < key_len; i++) {
hash = ((hash << 5) + hash) + *key++;
}
return hash;
}
int initHashTable(Node **hashTable, int size) {
for(int i = 0; i < size; i++) {
*(hashTable + i) = initNode(NULL, NULL);
}
return 0;
}
int insertHashTable(Node **hashTable, int size, char *key, char *value) {
int hash_value = times33(key, strlen(key)); // 对key 求hash值
int arr_key = (size - 1) & hash_value; // 把hash值映射到0到(size-1)
Node *node = initNode(key, value); // 堆内存上申请一个Node(X)
node->next = *(hashTable + arr_key); // X的下个元素是链表的头节点
*(hashTable + arr_key) = node; // 把X作为链表的头结点
return 0;
}
char * searchValueByKey(Node **hashTable, int size, char *key) {
int hash_value = times33(key, strlen(key));
int arr_key = (size - 1) & hash_value;
Node *node = *(hashTable + arr_key);
while(node->key != NULL) {
if (strcmp(node->key, key) == 0) {
return node->value;
} else {
node = node->next;
}
}
return NULL;
}
int main(int argc, char** argv) {
Node *hashTable[HASH_TABLE_SIZE];
initHashTable(hashTable, HASH_TABLE_SIZE);
insertHashTable(hashTable, HASH_TABLE_SIZE, "name", "thomas");
insertHashTable(hashTable, HASH_TABLE_SIZE, "age", "19");
char *va = searchValueByKey(hashTable, HASH_TABLE_SIZE, "age");
printf("va = %sn", va);
return 0;
}