C语言：Hash表查找字符串内容

目标：通过特定的一个哈希函数，将任意类性值映射成为一个整数值，（例如index = value % size）并将整数值作为索引，去一个顺序表中查找这个索引的value。

这种数据结构可以减少查找的时间复杂度，使之接近O（1），达不到顺序表的查找速度是因为可能会出现一个索引对应多个value，这时就要参考冲突处理机制。

常见的冲突处理机制有：

现在已经存在很多优秀的针对整形、字符型、浮点型等的哈希函数，可以直接使用。

Code

#include 
#include 
#include //拉链法
//链表节点，数据域存字符串
typedef struct Node{char *str;struct Node *next;
}Node;//顺序表（表头，大小）
typedef struct HashTable{//链表首地址,是链表头结点的顺序表，由于头结点是Node *,顺序表示Node **Node **data;int size;
}HashTable;//初始化链表,头插法，产生的新节点的next = 传入节点
Node *init_node(char *str, Node *head){Node *p = (Node *)malloc(sizeof(Node));p->str = strdup(str);//创建一片空间，需要free，万一*str内容变了也没关系p->next = head;return p;//虚拟头结点
}HashTable *init_hashtable(int n){HashTable *h = (HashTable *)malloc(sizeof(HashTable));h->size = n << 1;//若要使哈希表存储效率变高，存储空间扩大一倍？？h->data = (Node **)calloc(h->size, sizeof(Node *));return h;
}void clear_node(Node *node){if (node == NULL) return;Node *p = node, *q;while(p){q = p->next;free(p->str);free(p);p = q;}free(q);//?return;
}void clear_hashtable(HashTable *h){if (h == NULL) return;for (int i = 0; i < h->size; i++){clear_node(h->data[i]);}free(h->data);free(h);return;
}int BKDRHash(char *str){int seed = 31, hash = 0;for (int i = 0; str[i]; i++) hash = hash * seed + str[i];//保证正数return hash & 0x7fffffff;
}int insert(HashTable *h, char *str){int hash = BKDRHash(str);int ind = hash % h->size;h->data[ind] = init_node(str, h->data[ind]);return 1;
}int search(HashTable *h, char *str){int hash = BKDRHash(str);int ind = hash % h->size;Node *p = h->data[ind];while (p && strcmp(str, p->str)) p = p->next;return p != NULL;
}int main(){setvbuf(stdout, NULL, _IONBF, 0);
#define max_n 100int op;char str[max_n + 5] = {0};HashTable *h = init_hashtable(max_n + 5);while(~scanf("%d%s", &op, str)){switch (op){case 0:printf("insert %s to hashtable\n", str);insert(h, str);break;case 1:printf("search %s from hashtable, result = %d\n", str, search(h, str));}}
#undef max_nreturn 0;
}