C语言数据结构 - 哈希表

叁歲伎倆 2024-03-22 21:47 66阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    /************** 哈希表结构实现 **************/
    typedef int bool;
    
    typedef struct ListNode {
        void *key;
        void *val;
        struct ListNode *next;
    } Node;
    
    typedef struct {
        int size; // 哈希表存入数据的个数
        int length; // 哈希表底层数组容器的长度
        Node **buckets; // 哈希表底层数组容器，数组元素是Node*
        unsigned int (*hashCode)(void *); // 外部指定的hashCode方法，用于求解key的hash值
        bool (*equals)(void *, void *); // 外部指定的equals方法，用于比较两个key是否相同
    } HashTable;
    
    /*!
     * 创建哈希表
     * @param length 指定的哈希表底层数组的长度
     * @param hashCode 指定的求解key的hash值的方法
     * @param equals 指定的比较两个key是否相同的方法
     * @return 哈希表
     */
    HashTable *new_HashTable(int length, unsigned int (*hashCode)(void *), bool (*equals)(void *, void *)) {
        HashTable *ht = (HashTable *) malloc(sizeof(HashTable));
    
        ht->size = 0;
        ht->length = length;
        ht->buckets = (Node **) calloc(length, sizeof(Node *));
        ht->hashCode = hashCode;
        ht->equals = equals;
    
        return ht;
    }
    
    /*!
     * 除留余数法 获取 key 在 哈希表中的插入位置
     * @param ht 哈希表
     * @param key key
     * @return 插入位置
     */
    unsigned int hash(HashTable *ht, void *key) {
        return ht->hashCode(key) % ht->length;
    }
    
    /*!
     * put方法有两个作用，如果key在哈希表中不存在，则插入key-val键值对，否则更新key的val值
     * @param ht 哈希表
     * @param key 键
     * @param val 值
     */
    void put_HashTable(HashTable *ht, void *key, void *val) {
        // 获取 key 在哈希表中的插入位置 i
        unsigned int i = hash(ht, key);
    
        // 检查哈希表 桶i 位置 链上的键值对中是否有为key的键
        Node *cur = ht->buckets[i];
        while (cur != NULL) {
            // 如果有的话，则更新对应key对应的val
            if (ht->equals(cur->key, key)) {
                cur->val = val;
                return;
            }
            cur = cur->next;
        }
    
        // 如果链上都没有对应key，则创建key-val键值对节点，加入到 桶i 位置的头部
        Node* node = (Node*) malloc(sizeof(Node));
        node->key = key;
        node->val = val;
        node->next = ht->buckets[i];
    
        ht->buckets[i] = node;
    
        // 哈希表存入数据的个数+1
        ht->size++;
    }
    
    /*!
     * 判断哈希表中是否含有key
     * @param ht 哈希表
     * @param key 键
     * @return 哈希表中是否有 key
     */
    bool has_HashTable(HashTable* ht, void* key) {
        // 获取 key 在哈希表中的插入位置 i
        unsigned int i = hash(ht, key);
    
        // 检查哈希表 桶i 位置 链上的键值对中是否有为key的键
        Node* cur = ht->buckets[i];
        while(cur != NULL) {
            // 如果有的话，则返回true
            if(ht->equals(cur->key, key)) {
                return 1;
            }
            cur = cur->next;
        }
    
        // 如果没有的话，则返回false
        return 0;
    }
    
    /*!
     * 获取哈希表 键key 对应的 值val，如果不存在对应key，则返回NULL
     * @param ht 哈希表
     * @param key 键
     * @return 返回键对应的值
     */
    void* get_HashTable(HashTable* ht, void* key) {
        // 获取 key 在哈希表中的插入位置 i
        unsigned int i = hash(ht, key);
    
        // 检查哈希表 桶i 位置 链上的键值对中是否有为key的键
        Node* cur = ht->buckets[i];
        while(cur != NULL) {
            // 如果有的话，则返回对应val
            if(ht->equals(cur->key, key)) {
                return cur->val;
            }
            cur = cur->next;
        }
    
        // 如果没有的话，则返回NULL
        return NULL;
    }
    
    /*!
     * 删除哈希表中key对应键值对
     * @param ht 哈希表
     * @param key 键
     */
    void del_HashTable(HashTable* ht, void* key) {
        // 获取 key 在哈希表中的插入位置 i
        unsigned int i = hash(ht, key);
    
        // 当前节点的前一个节点
        Node* prev = NULL;
        // 当前节点
        Node* cur = ht->buckets[i];
    
        // 如果当前节点不为NULL
        while(cur != NULL) {
            // 如果当前节点的key和要删除的key相同
            if(ht->equals(cur->key, key)) {
                // 记录当前节点为要被删除的节点
                Node* removed = cur;
    
                if(prev != NULL) {
                    // 如果当前节点前一个节点不为NULL
                    // prev 是要被删除节点的前一个节点
                    // removed->next 是要被删除节点的下一个节点
                    prev->next = removed->next;
                } else {
                    // 如果当前节点前一个节点为NULL，则要被删除的节点就是头节点
                    // ht->buckets[i] 指向该桶位置的头节点
                    // removed->next 是该桶位置第二个节点
                    ht->buckets[i] = removed->next;
                }
    
                // 释放被删除节点的内存
                free(removed);
    
                // 哈希表存入数据的个数-1
                ht->size--;
    
                return;
            }
    
            prev = cur;
            cur = cur->next;
        }
    }
    
    /*!
     * 打印哈希表
     * @param ht 哈希表
     */
    void print_HashTable(HashTable* ht) {
        for(int i=0; i<ht->length; i++) {
            Node* cur = ht->buckets[i];
    
            // 桶位置 i
            printf("[%d]", i);
    
            // 打印该桶位置 链上节点的key
            while(cur != NULL) {
                printf(" -> %d", *((int*) cur->key));
                cur = cur->next;
            }
    
            printf("\n");
        }
    }
    
    
    /************** 测试代码 **************/
    unsigned int hashCode(void* key) {
        return abs(* ((int*) key));
    }
    
    int equals(void* key1, void* key2) {
        return (*(int*) key1) - (*(int*) key2) == 0;
    }
    
    int main() {
        HashTable* ht = new_HashTable(10, hashCode, equals);
    
        int nums[] = {1, 2, 2, 3, 3, 4, 10, 12, 22, 103, 100};
        int nums_size = 11;
    
        for(int i=0; i<nums_size; i++) {
            put_HashTable(ht, &nums[i], NULL);
        }
    
        printf("%d\n", ht->size);
    
        print_HashTable(ht);
    
        int key = 3;
        printf("ht has key=%d ? %d\n", key, has_HashTable(ht, &key));
    
        del_HashTable(ht, &key);
        print_HashTable(ht);
        printf("ht has key=%d ? %d\n", key, has_HashTable(ht, &key));
    
        return 0;
    }