C语言实现哈希表 - 二次探测再散列解决冲突

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

#define HASH_SIZE 10 //哈希表大小 #define EMPTY_ELEMENT -1 //表示该位置没有元素

int hash_table[HASH_SIZE]; //哈希表

//哈希函数 int hash(int key) { return key % HASH_SIZE; }

//插入元素 void insert(int key) { int index = hash(key); //计算哈希值

//如果该位置已经有元素了，就进行二次探测
int i = 1;
while (hash_table[index] != EMPTY_ELEMENT)
{
    index = (index + i * i) % HASH_SIZE;
    i++;
}

hash_table[index] = key; //插入元素

}

//查找元素 bool search(int key) { int index = hash(key); //计算哈希值

//如果该位置不是要找的元素，就进行二次探测
int i = 1;
while (hash_table[index] != key)
{
    if (hash_table[index] == EMPTY_ELEMENT) //如果该位置为空，说明没有找到
        return false;

    index = (index + i * i) % HASH_SIZE;
    i++;
}

return true; //找到了

}

int main() { //初始化哈希表 for (int i = 0; i < HASH_SIZE; i++) hash_table[i] = EMPTY_ELEMENT;

//插入元素
insert(5);
insert(15);
insert(25);
insert(35);

//查找元素
printf('%d\n', search(5)); //输出1
printf('%d\n', search(10)); //输出0

return 0;

}