Hash Table(哈希表)

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

timg

代码:


#ifndef HASH_TABLE_H
#define HASH_TABLE_H

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

#define hash_table_empty(table) (table->size == 0)
#define hash_table_size(table) (table->size)
#define hash_table_capacity(table) (table->capacity)
#define pair_data(pair) (pair->data)
#define pair_key(pair) (pair->key)

typedef struct pair {

    struct pair *next;

    char *key;

    void *data;
} pair;

typedef struct hash_table {

    size_t size;  // 元素大小
    size_t capacity; // 桶的大小,容量

    pair **key_arr;

} hash_table;

int strtoi(char *str) {
    size_t len = strlen(str);
    int i;
    int sum = 0;
    for(i = 0; i < len; i++) {
        sum += (int)str[i];
    }

    return sum;
}

/**
 * 取余法
 * @param str
 * @param bucket_size
 * @return
 */
int hash_str(char *str, size_t bucket_size) {

    if (bucket_size == 0) {
        bucket_size = 10;
    }
    int number = strtoi(str);
    int index = (number * 33 * 33) % bucket_size;

    return index;
}

/**
 * 乘法
 * @param str
 * @param bucket_size
 * @return
 */
int hash_str_multi(char *str, size_t bucket_size) {

    if (bucket_size == 0) {
        bucket_size = 10;
    }
    int number = strtoi(str);

    double tmp = number * 0.618;

    int index = floor((tmp - floor(tmp)) * bucket_size);

    return index;
}

pair *pair_new(char *key, void *data) {

    pair *p = malloc(sizeof(pair));
    p->next = NULL;
    p->data = data;
    p->key = key;

    return p;
}

pair *pair_lookup(pair *p, char *key) {

    while (p != NULL) {
        if(strcmp(p->key, key) == 0) {
            break;
        } else {
            p = p->next;
        }
    }

    return p;
}

/**
 * 创建
 * @param bucket_size
 * @return
 */
hash_table *hash_table_new(size_t bucket_size) {

    hash_table *table = malloc(sizeof(hash_table));

    table->capacity = bucket_size;
    table->size = 0;
    table->key_arr = malloc(bucket_size * sizeof(pair));

    for (int i = 0; i < bucket_size; i++) {
        table->key_arr[i] = NULL;
    }

    return table;
}

/**
 * 查找
 * @param table
 * @param key
 * @return
 */
pair *hash_table_lookup(hash_table *table, char *key) {
    int index = hash_str(key, hash_table_capacity(table));
    pair *head = table->key_arr[index];

    pair *p = pair_lookup(head, key);

    return p;
}

/**
 * set
 * @param table
 * @param key
 * @param data
 */
void hash_table_set(hash_table *table, char *key, void *data) {

    // key 存在,则覆盖
    int index = hash_str(key, hash_table_capacity(table));

    pair *pair_exist = pair_lookup(table->key_arr[index], key);

    if (pair_exist) {
        pair_exist->data = data;
        return ;
    }

    // key 不存在,则添加
    pair *p = pair_new(key, data);

    p->next = table->key_arr[index];
    table->key_arr[index] = p;
    table->size += 1;
}

/**
 * get
 * @param table
 * @param key
 * @return
 */
void *hash_table_get(hash_table *table, char *key) {

    pair *p = hash_table_lookup(table, key);

    if (p != NULL) {
        return pair_data(p);
    }

    return NULL;
}

/**
 *
 * @param table
 * @param key
 */
void hash_table_remove(hash_table *table, char *key) {

    int index = hash_str(key, hash_table_capacity(table));
    pair *current = table->key_arr[index];
    pair *head = current;
    pair *prev =  current;

    while (current != NULL) {
        if (strcmp(pair_key(current), key) == 0) {
            if (head == current) {
                table->key_arr[index] = current->next;
            } else {
                prev->next = current->next;
            }

            free(current);
            table->size -= 1;
            return ;
        }

        prev = current;
        current = current->next;
    }

}

/**
 * free
 * @param table
 */
void hash_table_free(hash_table *table) {

    size_t len = hash_table_capacity(table);

    for(int i = 0; i < len; i++) {
        if (table->key_arr[i] != NULL) {
            pair *node = table->key_arr[i];
            while (node != NULL) {
                pair *next = node->next;
                free(node);
                node = next;
            }
        }
    }

    free(table);
}

#endif //HASH_TABLE_H