「数据结构与算法」哈希表是什么？应该如何实现

小时候在家附近的小店里买东西的时候，有一类售货员看到商品的一瞬间基本上就能算出我一共要付多少钱，用时间复杂度来说，就是, 还有一类不怎么熟练的售货员，他可能需要翻出一个小本子，查价格表，那么时间复杂度就是。

前一类售货员通过不断的记忆，在脑海里建立了 “商品:价格” 之间的对应关系，看到商品后，条件反射的想到了价格，后一类可能就是拿了一个小本本记着商品和价格的关系，然后每次得遍历（如果按照商品名进行排序，那么查找速度或许会快一点，但是每次新增商品就得扩容小本本进行排序）。从数据结构的角度，前者是一个哈希(hash)表，后者就是一个普通的数组。

哈希表，或者叫做散列表，是一种非常好用的数据结构，在现代的编程语言中，如Java, C++, Python, Perl都提供了内置的方法，例如Python的字典结构。从我的学习经验来看，哈希表是一种用空间换效率的方法，这可以从哈希表的建立来说明。

哈希表的建立分为两个部分，一个哈希函数和冲突解决方案。哈希函数的作用是将一个任意长度的输入映射到一个固定大小的数组中，例如{ 1, 11, 13, 16,98 } 可以通过对7求余数，映射到索引为{1,4,6,2,0}的数组。这里 就是一个哈希函数. 一个好的哈希函数，应该尽量的将原来的数组均匀的散步在哈希表中，当然这就不需要你费尽脑筋想了，已经有很多前人提出了对应公式。

由于表的大小一开始已经固定，那么不可避免会出现新的数字加入哈希表中发生冲突的情况，比如说99对7求模，结果是1，而1的位置已经被占据了。这个时候就需要解决冲突。解决冲突的方法有两种策略比较常用，分离链表法和开放寻址法。 前者是在冲突的位置建立一个链表，后者则是在冲突的位置上向前或向后找空位。

C语言本身没有内置哈希表，所以在「数据结构与算法」如何快速求两数之和，我非常粗糙的写了哈希表结构。后来经过几天的学习，我又在C上写了第一个稍微能看的版本。

版本1： 只能实现对数字求hash，也只能存储数字。分为 "hash_table.h" 和 “hash_table.c” 两个小文件。当然一开始的时候并没有头文件，只是后来突然想明白了，“头文件其实是一种总体规划，而不是一种具体实现”，于是就把 函数定义, 类型定义的部分记录到了头文件中。

头文件命名为"hash_table.h"，代码如下。解释性的中文也在代码的注释部分

#ifndef _HASH_TABLE_H
#define _HASH_TABLE_H

#define is_empty(A) ((A).info == empty ? true : false)
#define is_deleted(A) ((A).info == deleted ? true : false)
#define is_legitimate(A) ((A).info == legitimate ? true : false)

/*  由于数组索引只可能是正整数，因此用typedef 将 无符号的整型定义为index*/
/* 同时为了代码的阅读性，定义了一个position，表示返回的位置*/
typedef unsigned int index;
typedef index position;

/* 用结构体定义了哈希表这种数据结构
 * hash_entry用于记录key, value
 * hash_table 记录表的整体大小，目前使用情况，以及内容的实际存放地址
*/
enum entry { empty, deleted, legitimate} ;

typedef struct _hash_entry hash_entry;
typedef struct _hash_table hash_table;

/* 为定义的哈希表结构，定义了操作函数
 * 包括：根据表大小，初始化一个哈希表 
 * 计算哈希值，寻找表中的空闲位置，
 * 在表中插入数据，搜索数据，以及最后的摧毁表，释放内存
*/
hash_table *initialize(int table_size);
index hash(int value, int table_size);
position find(int key, hash_table *tbl);
void insert(int key, int value, hash_table *tbl);
int search(int key, hash_table *tbl);
void destroy(hash_table *tbl);

#endif

如下就是实际代码: "hash_table.c"， 解释同样在代码中的注释。

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

//实际哈希表表单元结构，记录着键值对，以及当前单元状态，是空闲，还是已经占用，还是标记删除
typedef struct _hash_entry{
    enum entry info;
    int key;
    int value;
} hash_entry ;

// 记录表的元信息
typedef struct _hash_table{
    int size;
    int table_size;
    hash_entry *entrys;
} hash_table ;

// 初始化表，返回一个指向表的指针
hash_table *initialize(int table_size)
{
    hash_table * hash_tbl;
    hash_tbl = malloc(sizeof(hash_table)); //动态申请内存
    hash_tbl->size = 0;  //初始化表的大小为0
    int new_table_size; 
    new_table_size = table_size *  10 + 3;
    hash_tbl->table_size = new_table_size; // 理论上是找一个质数用作表的大小，但是我偷懒了，直接申请一个更大的空间
    hash_tbl->entrys = malloc(sizeof(hash_entry) * new_table_size); // 申请实际存放元素的连续空间
    int i;
    for (i = 0; i < new_table_size; i++){
        hash_tbl->entrys[i].info = empty;   
    } // 初始化里面的记录
    printf("initialize ok \n"); //当时为了调试写的，可以注释掉
    return hash_tbl;    
}

index hash(int value, int table_size){
    index hash_value ;
    hash_value = (value << 5) % table_size;  //一个简单的哈希函数，通过位移的方式，整体乘以5，然后求表格大小求模
    //printf("hash value is %d \n", hash_value);
    return hash_value ;
}

// 以开放寻址解决冲突
position find(int key, hash_table *tbl)
{
    position pos;
    int collision = 0;
    int table_size = tbl->table_size;
    pos = hash(key, table_size); //find the position
    while (tbl->entrys[pos].info != empty &&  //判断当前记录是否为空，如果不为空，同时
            tbl->entrys[pos].key != key){    //里面记录key和要查找的key还不一样，就说明有冲突
        pos += 2 * ++collision - 1;                
        if ( pos > table_size)
            pos -= table_size;
    }
    return pos;
}

//插入元素
void insert(int key, int value, hash_table *tbl)
{
    position pos = find(key, tbl);
    float load;
    load = (float)tbl->size / (float)tbl->table_size;
    printf("Load is %f \n", load);
    if ( load > 0.5 )
        return;
    if ( ! is_legitimate(tbl->entrys[pos]) ){
        tbl->entrys[pos].info  = legitimate;
        tbl->entrys[pos].key   = key;
        tbl->entrys[pos].value = value;
        tbl->size ++;
        printf("Insert %d at position %d \n", 
                tbl->entrys[pos].value,
                 pos);
    }

}
//根据key搜索元素，返回value
int search(int key, hash_table *tbl)
{
    position pos;
    pos = find(key, tbl);
    printf("Find %d at position %d\n", key, pos);
    //printf("%d is %d\n", 10, tbl->entrys[8].value);
    if ( ! is_legitimate(tbl->entrys[pos])){
        printf("unused key\n");
        return -1;
    }
    int res = tbl->entrys[pos].value;
    return res;

}
//摧毁表格，释放内存
void destroy(hash_table * tbl)
{
    free(tbl->entrys);
    free(tbl);
}
//一些测试性操作
int main()
{
    hash_table * hash_tbl;
    hash_tbl = initialize(13);
    // INSERT TEST
    printf("INSERT TEST\n");
    insert(10, 100, hash_tbl);
    insert(11, 110, hash_tbl);
    insert(12, 123, hash_tbl);
    //printf("%d is %d\n", 10, hash_tbl->entrys[8].value);
    printf("-------------------------------------\n");
    // SEARCH TEST
    printf("%d is %d\n", 10, search(10, hash_tbl));
    printf("%d is %d\n", 11, search(11, hash_tbl));
    printf("%d is %d\n", 12, search(12, hash_tbl));
    destroy(hash_tbl);
    return 0;
}

后续计划: 写一个能够存储字符串的哈希表。