数据结构与算法-哈希表篇（C语言版）

实现一个简单的哈希表

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

#define SIZE 9

// 将数组元素封装成 key
typedef struct Element{
    int key;
}* Element;

// 利用数组实现哈希表
typedef struct HashTable{
    Element* table;
}* HashTable;

/**
 * 哈希函数，计算对应的哈希值
 */
int hash(int key) {
    return key % SIZE;
}

// 初始化哈希表
void init(HashTable hashTable) {
    hashTable->table = malloc(sizeof (struct Element) * SIZE);
    for(int i = 0; i < SIZE; i++) {
        hashTable->table[i] = NULL;
    }
}

// 往哈希表中插入元素（此处暂未考虑装满的情况）
void put(HashTable hashTable, Element element) {
    // 计算哈希值
    int hashCode = hash(element->key);
    // 对号入座
    hashTable->table[hashCode] = element;
}

// 查找
int get(HashTable hashTable, int key) {
    int hashCode = hash(key);
    if(hashTable->table[hashCode]->key == key) {
        return 1;
    }
    return 0;
}

// 创建一个新元素
struct Element* createElement(int key) {
    struct Element* element = malloc(sizeof(struct Element));
    element->key = key;
    return element;
}

冲突处理

线性探测法

当前有冲突就往后查找空闲位置

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

#define SIZE 9

// 将数组元素封装成 key
typedef struct Element{
    int key;
}* Element;

// 利用数组实现哈希表
typedef struct HashTable{
    // 此处是指针的指针，数组中存放的是地址
    Element* table;
}* HashTable;

/**
 * 哈希函数，计算对应的哈希值
 */
int hash(int key) {
    return key % SIZE;
}

// 初始化哈希表
void init(HashTable hashTable) {
    hashTable->table = malloc(sizeof (struct Element) * SIZE);
    for(int i = 0; i < SIZE; i++) {
        hashTable->table[i] = NULL;
    }
}

// 往哈希表中插入元素（此处暂未考虑装满的情况）
void put(HashTable hashTable, Element element) {
    // 计算哈希值
    int hashCode = hash(element->key);
    int count = 0;
    // 若当前哈希值对应位置已有元素则向后寻找
    while(hashTable->table[hashCode]) {
        // 重新计算哈希值，不能单纯 hashCode++，这样很可能会数组下标越界
        hashCode = hash(element->key + ++count);
    }
    // 对号入座
    hashTable->table[hashCode] = element;
}

// 查找
int get(HashTable hashTable, int key) {
    int hashCode = hash(key);
    int count = 0;
    // 记录最初的位置，目的是方便后面判断 hashcode 是否已经走了一圈回来
    int startIndex = hashCode;
    do{
        int cur = hashTable->table[hashCode]->key;
        if(cur == key) {
            return 1;
        }
        // 没找到则重新计算哈希值
        hashCode = hash(key + ++count);
    } while (startIndex != hashCode && hashTable->table[hashCode]);
    return 0;
}

// 创建一个新元素
struct Element* createElement(int key) {
    struct Element* element = malloc(sizeof(struct Element));
    element->key = key;
    return element;
}

int main() {
    struct HashTable hashTable;
    init(&hashTable);
    for (int i = 0; i < 9; ++i) {
        put(&hashTable, createElement(i * 9));
    }

    for (int i = 0; i < 9; ++i) {
        printf("%d ", hashTable.table[i]->key);
    }

}

链地址法

当前有冲突则将其变成链表连接起来

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

#define SIZE 9

// 链表结构
typedef struct LinkNode {
    int key;
    struct LinkNode* next;
}* LinkNode;

// 数组模拟哈希表
typedef struct HashTable {
    // 此处数组存放的是struct LinkNode类型节点
    struct LinkNode* node;
}* HashTable;

int hash(int key) {
    return key % SIZE;
}

void init(HashTable hashTable) {
    hashTable->node = malloc(sizeof(struct LinkNode) * SIZE);
    // 将哈希表中的所有头节点初始化
    for (int i = 0; i < SIZE; ++i) {
        // hashtable->node[i] 指的是数组中第 i 个的 struct LinkNode 节点，而不是指针（地址），故后面是用 . 来引出其结构体变量
        hashTable->node[i].key = -1;
        hashTable->node[i].next = NULL;
    }
}

LinkNode createNode(int key) {
    LinkNode node = malloc(sizeof(struct LinkNode));
    node->key = key;
    node->next = NULL;
    return node;
}

void put(HashTable hashTable, int key) {
    int hashCode = hash(key);
    LinkNode head = &hashTable->node[hashCode];
    // 若已有元素占领该位置，则继续直至链表尾，然后插入
    while(head->next) {
        head = head->next;
    }
    head->next = createNode(key);
}

int get(HashTable hashTable, int key) {
    int hashCode = hash(key);
    LinkNode head = &hashTable->node[hashCode];
    // 此处设计的哈希表中的链表头节点默认全为 -1（类似于虚拟头节点），故真正的节点在head->next上
    while(head->next) {
        if(head->next->key == key) {
            return 1;
        }
        head = head->next;
    }
    return 0;
}

int main() {
    struct HashTable table;
    init(&table);

    put(&table, 10);
    put(&table, 19);
    put(&table, 20);

    printf("%d\n", get(&table, 20));
    printf("%d\n", get(&table, 17));
    printf("%d\n", get(&table, 19));
}