引言： 实现链式哈希的代码
/*
质数： 对于大于1的正自然数， 处理1和它本身别的数都无法整除它， 这个数就是质数
hash函数的确定：
α(质量因子) = 0.7-0.8比较合适
m：存储数据的真实个数
n：存储空间的大小α = m / n, 这样就能将n的值确定下来
给定一个数， 需要判断这个数存储再哈希表的哪一个位置， 这个时候需要引出hash函数
p:该质数一般取比存储空间小的最大质数，保证hash表的散列度好
H(key) = key % p(质数)
链式哈希和顺序哈希以上的算法， 肯定有数据元素对应的hash的索引值是一致的， 这个叫做冲突，解决冲突的方法有两种：
1.对于顺序存储的哈希表， 再冲突的位置的基础上加上步长
2.对于链式存储的hash表， 将经过hash函数处理之后索引值一样的数据元素使用一条链表串起来， 这样查找的时候， 最多也是对这条链表查找。*/
#ifndef _HASH_H
#define _HASH_H
/****************************************************
*
*
*Author:hewei
*Date:2024-3-9
*File:hash.h
*Note: value = hash(key) = key % MOD;
*
*
*
*************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 15
#define MOD 15
typedef int datatype;
typedef struct node {
datatype key;
int value;
struct node *next;
}list_node, *link_list;
typedef struct {
list_node data[N];
}hash_t;
hash_t *hash_create();
int hash_free(hash_t *h);
int hash_insert(hash_t *h, datatype value);
link_list hash_search(hash_t *h, datatype key);
/***********************************
*
*Base search, squence search and binary search, assess ASL平均查找长度
*
*********************************/
int squence_search(int *arr, int arr_len, int obj_value);
int binary_search(int *arr, int arr_len, int obj_value);
#endif
#include "hash.h"
/*brife: create a link hash table
*
* */
hash_t *hash_create()
{
hash_t *h;
if((h = (hash_t *)malloc(sizeof(hash_t))) == NULL) {
printf("malloc hash heap space failed\n");
return NULL;
}
memset(h, 0, sizeof(hash_t));
return h;
}
/*brife: release a hash table
*
* */
int hash_free(hash_t *h)
{
if(h == NULL) {
printf("param is invalid\n");
return -1;
}
free(h);
return 0;
}
/*brife: need search element insert to hash table
*
* */
int hash_insert(hash_t *h, datatype key)
{
if(h == NULL) {
printf("param is invalid\n");
return -1;
}
link_list p, q;
if((q = (link_list)malloc(sizeof(list_node))) == NULL) {
printf("%s, alloc new node memery failed\n", __func__);
return -1;
}
q->key = key;
q->value = key % MOD;
q->next = NULL;
p = &(h->data[key % MOD]);
while(p->next && p->next->key < q->key) {
p = p->next;
}
q->next = p->next;
p->next = q;
return 0;
}
/*brife: specify data search
*param:hash_t handle, search key
*
* */
link_list hash_search(hash_t *h, datatype key)
{
if(h == NULL) {
printf("param is invalid\n");
return NULL;
}
link_list p = &(h->data[key % MOD]);
while(p->next != NULL && p->next->key != key) {
p = p->next;
}
if(p->next == NULL) {
return NULL;
}
return p->next;
}
int squence_search(int *arr, int arr_len, int obj_value)
{
if(arr == NULL) {
printf("param is invalid\n");
return -1;
}
int i = 0;
for(;i < arr_len; i++) {
if(arr[i] == obj_value) {
return i;
}
}
return -1;
}
int binary_search(int *arr, int arr_len, int obj_value)
{
if(arr == NULL) {
printf("param is invalid\n");
return -1;
}
int low = 0, high = arr_len - 1, mid = (high + low) / 2;
while(arr[mid] != obj_value) {
if(arr[mid] < obj_value) {
low = mid + 1;
mid = (low + high) / 2;
} else {
high = mid - 1;
mid = (low + high) / 2;
}
}
return mid;
}#include "hash.h"
int main(int argc, const char *argv[])
{
datatype arr[] = {67, 7, 89, 6, 1, 198, 201};
int sort_arr[] = {1, 4, 6, 8, 9, 88};
int i, arr_len = sizeof(arr) / sizeof(datatype);
link_list ret = NULL;
hash_t *h;
if((h = hash_create()) == NULL) {
printf("hash table create failed\n");
return -1;
}
for(i = 0; i < arr_len; i++) {
hash_insert(h, arr[i]);
}
printf("Please input a hope search data:");
scanf("%d", &i);
if((ret = hash_search(h, i)) == NULL) {
printf("Not found\n");
} else {
printf("Found: key: %d, value: %d\n", ret->key, ret->value);
}
int r = squence_search(sort_arr, sizeof(sort_arr) / sizeof(int), 8);
printf("squence_search: %d\n", r);
r = binary_search(sort_arr, sizeof(sort_arr) / sizeof(int), 9);
printf("squence_search: %d\n", r);
return 0;
}
