散列表(C语言，又称哈希表(hash)，除留余数法+线性探测)

概念相关参考《大话数据结构》，下面贴上可运行的代码

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define HASHSIZE 12 // hash表的长度,这个长度应该足够长
#define NULLKEY -32768 // 一个不可能的值初始化hash表

// 表结构
typedef struct {
    int *elem;
    int count;
}HashTable;

bool init(HashTable *);
int hash(int);
bool insert(HashTable *, int);
bool search(HashTable *, int, int *);

bool search(HashTable *H, int key, int *pAddr)
{
    *pAddr = hash(key); // 先计算key应该存在的位置
    //开始查找
    while (H->elem[*pAddr] != key) { // 不相等则说明冲突
        // 线性探测更新地址
        *pAddr = (*pAddr + 1) % HASHSIZE;
        // 冲突情况下按照我们的算法，值应该存放到其后紧跟的空闲位置，也就是肯定在NULLKEY前，中间不会出现NULLKEY
        if (H->elem[*pAddr] == NULLKEY || *pAddr == hash(key)) {
            // 到了NULLKEY还未找到或者回到源点则说明要查找的key不存在
            printf("search %d failed, not exist.\n", key);
            return false;
        }
    }

    printf("search %d success(at %d).\n", key, *pAddr);
    return true;
}

bool insert(HashTable *H, int key)
{
    int addr;
    addr = hash(key); // 先计算得到hash表应该存放的地址
    while (H->elem[addr] != NULLKEY) { // 如果成立则说明冲突
        /* 如果冲突则进行线性探测寻找下一个
         * 因为我们的表长度是根据已知要操作的数列长度申请了足够长的空间，所以肯定会找到一个空闲位置
         */
        printf("found conflict at %d when insert %d\n", addr, key);
        addr = (addr + 1) % HASHSIZE; 
    }
    // 循环结束肯定会找到一个空闲的addr
    H->elem[addr] = key;
    printf("insert %d success(at %d).\n", key, addr);
    return true;
}

// **除留余数法**
int hash(int key)
{
    return key % HASHSIZE;
}

bool init(HashTable *H)
{
    H->count = HASHSIZE;
    H->elem = (int *)malloc(sizeof(int)*HASHSIZE);
    for (int i=0; i < H->count; i++) {
        H->elem[i] = NULLKEY;
    } 
    printf("init success.\n");
    return true;
}

int main(void)
{
    int addr;
    int arr[HASHSIZE] = {12,67,56,16,25,37,22,29,15,47,48,34};
    HashTable h1;
    init(&h1);
    printf("-------insert--------\n");
    // 填充
    for (int i=0; i<HASHSIZE; i++) {
        insert(&h1, arr[i]);
    }
    printf("-------search--------\n");
    search(&h1, 12, &addr);
    search(&h1, 67, &addr);
    search(&h1, 16, &addr);
    search(&h1, 34, &addr);
    search(&h1, 999, &addr);

    return 0;
}

output

root@8be225462e66 c]# gcc hash.c && ./a.out
init success.
-------insert--------
insert 12 success(at 0).
insert 67 success(at 7).
insert 56 success(at 8).
insert 16 success(at 4).
insert 25 success(at 1).
found conflict at 1 when insert 37
insert 37 success(at 2).
insert 22 success(at 10).
insert 29 success(at 5).
insert 15 success(at 3).
insert 47 success(at 11).
found conflict at 0 when insert 48
found conflict at 1 when insert 48
found conflict at 2 when insert 48
found conflict at 3 when insert 48
found conflict at 4 when insert 48
found conflict at 5 when insert 48
insert 48 success(at 6).
found conflict at 10 when insert 34
found conflict at 11 when insert 34
found conflict at 0 when insert 34
found conflict at 1 when insert 34
found conflict at 2 when insert 34
found conflict at 3 when insert 34
found conflict at 4 when insert 34
found conflict at 5 when insert 34
found conflict at 6 when insert 34
found conflict at 7 when insert 34
found conflict at 8 when insert 34
insert 34 success(at 9).
-------search--------
search 12 success(at 0).
search 67 success(at 7).
search 16 success(at 4).
search 34 success(at 9).
search 999 failed, not exist.
[root@8be225462e66 c]#

散列表(C语言，又称哈希表(hash)，除留余数法+线性探测)

原文：https://blog.51cto.com/sndapk/2819885