哈希存储(散列存储)

为了快速定位数据

哈希表

哈希冲突 / 哈希矛盾

关键字不一样，但是映射之后结果一样

如何避免 哈希矛盾？

1、重新设计哈希函数，尽可能均匀散列分布在哈希表

2、开放定址法：向下寻找未存储的位置进行存放数据

3、链地址法： 将数据链表的首地址存入哈希表，只需将数据结点往链表后链接即可

哈希表创建

HSNode_t *hashtable[HASH_SIZE] = {NULL};

1、设计哈希函数

int hash_function(char key)
{if (key >= 'a' && key <= 'z'){return key-'a';}else if (key >= 'A' && key <= 'Z'){return key-'A';}else{return HASH_SIZE-1;}
}

2、插入哈希表

int insert_hashtable(HSDataTYpe data)
{int addr = hash_function(data.name[0]);HSNode_t *pnode = malloc(sizeof(HSNode_t));if (NULL == pnode){perror("fail malloc");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = hashtable[addr];hashtable[addr] = pnode;return 0;
}

3、插入数据

void print_hash()
{for(int i = 0;i < HASH_SIZE ;++i){HSNode_t *p = hashtable[i];while(p != NULL){printf("name : %s  tel : %s",p->data.name,p->data.tel);p = p->pnext;}}printf("\n");
}

4、遍历哈希表

HSNode_t *search_hash(char *name)
{HSNode_t *p = NULL;int addr = hash_function(name[0]);p = hashtable[addr];while(p != NULL){if(!(strcmp(p->data.name,name))){//return p;printf("name : %s  tel : %s",p->data.name,p->data.tel);return p;}else{p = p->pnext;}}return NULL;}

5、数据查找

void destroy_hash()
{HSNode_t *p;for(int i = 0; i < HASH_SIZE;++i){while(hashtable[i] != NULL){p = hashtable[i];hashtable[i] = p->pnext;free(p);}}
}

二、算法