哈希表示例

哈希表的意义在于高效查找。对于查找来说，如果数据量特别大，二分查找和哈希表算法十分有用了。二分查找前面已经讲过，现来讲讲哈希表算法。
就像输入数据数组下标返回数组元素一样，这样的查找方式是最高效的了，哈希表就是这样一种数据结构。
假设现在有10个元素的数组，通过每一个元素可以确定它存在在哈希表中的哪一个位置(哈希表可以理解为一个特殊数组，它的数据成员也有下标)，当下次要查找该元素时候，就可以通过该位置拿到该数值元素，这便是哈希表的核心思想。
如何通过一个数据元素确定其在哈希表中的位置，一般我们可以通过该元素取模于元素个数，这样一来我们只要分配一个跟元素个数一样大的哈希表就可以来存放这些数组元素了。但是，这样会数据重叠的情况发生。例如下面例子，
数组a的数据成员为:

int a[3] = {2, 3, 6};

对于2来说，它放在hash[2 % 3]，即hash[2]处，但是对于3和6来讲，它们放在哈希表的hash[3 % 3] 和hash[6 % 3]，即hash[0]处，那么就会出现后存到hash[0]的’6’覆盖掉先存到hash[0]的3了。因此哈希表的数据成员不能这样单纯的存放，解决办法是采用链表。
哈希表的数据成员是链表头，即是链表变量(注意，不是链表指针)，每次数据都是追加到对应的哈希表位置的链表头指向的链表中。这样，一来不会产生数据覆盖，二来对于查找操作效率也大大提高。
示例代码如下:
为了方便测试，先定义并实现两个函数，分别是用于产生随机数存放到数组、遍历数数所在数组:

void rand_array(void)
{
    for (i = 0; i < MAX; i++)
        a[i] = rand() % 100;
}

void show_array(const char *str)
{
    printf("%s", str);
    for (i = 0; i < MAX; i++)
        printf("%d ", a[i]);
    printf("\n");
}

定义链表节点，这里采用双向链表，方便操作

typedef struct _Node NODE;  //前向typedef
struct _Node{
    int data;
    NODE* pre;
    NODE* next;
};

创建哈希表，并将数组成员放到哈希表对应的位置

//返回哈希表的地址。哈希表的数据成员是链表，所以返回类型是链表类型的地址
NODE* hash_create(int max)
{
    NODE *list = NULL, *new = NULL;
    int index;
    list = (NODE* )malloc(max * sizeof(NODE));  //动态分配空间，该空间的数据成员是链表变量

    //对哈希表中的数据元素初始化
    for (i = 0; i < max; i++)
    {
        list[i].pre = &list[i];
        list[i].next = &list[i];
    }

    //将数组元素挂到对应哈希表位置中
    for (i = 0; i < max; i++)
    {
        //推算该数据应在哈希表的哪一个位置存放
        index = create_hash_index(a[i]);        

        new = (NODE* )malloc(sizeof(NODE));
        new->data = a[i];

        //将数据挂到双向链表中
        new->next = &list[index];
        new->pre = list[index].pre;
        list[index].pre->next = new;
        list[index].pre = new;
    }

    return list;
}

上面根据数据元素推算出应在哈希表哪一个位置函数create_hash_index的实现体为:

int create_hash_index(int dat)
{
    return dat % MAX;
}

遍历哈希表的数据成员

//遍历哈希表中的所有数据
void travel_hash(NODE* list)
{
    NODE* tmp = NULL;
    for (i = 0; i < MAX; i++)
    {
        tmp = list[i].next;
        printf("list[%d]: ", i);
        while (tmp != &list[i])
        {
            printf("%d ", tmp->data);
            tmp = tmp->next;
        }
        printf("\n");
    }
}

查找哈希表中的数据，查找成功返回该元素在该哈希表中的下标，找不到则返回-1

//查找哈希表中的数据
int find_hash(NODE* list, int key)
{
    NODE* tmp = NULL;

    for (i = 0; i < MAX; i++)
    {
        tmp = list[i].next;
        while (tmp != &list[i])
        {
            if (tmp->data == key)
                return i; //tmp->data;
            tmp = tmp->next;
        }       
    }
    return -1;
}

销毁哈希表及哈希表中链表数据成员

//销毁哈希表及哈希表中链表数据成员
void destory_hash(NODE* list)
{
    NODE* tmp = NULL, *save = NULL;

    for (i = 0; i < MAX; i++)
    {
        tmp = list[i].next;
        while (tmp != &list[i])
        {
            save = tmp->next;
            free(tmp);          
            tmp = save;

            //save = tmp;
            //free(tmp);
            //tmp = save->next;
        }
    }
    free(list);
}

main函数的调用

int main(void)
{
    NODE* hash_list = NULL;
    int dat;

    //产生随机数并存放到数组中
    rand_array();

    //显示数组中的随机数
    show_array("rand: ");

    //创建哈希表并将数组元素放到哈希表中
    hash_list = hash_create(MAX);

    //遍历哈希表
    travel_hash(hash_list);

     while (1)
    {
        printf("please input dat:");
        scanf("%d", &dat);

        if (dat == -1)
            break;

        printf("find: %d\n", find_hash(hash_list, dat));
    }
    //销毁哈希表及哈希表中的链表数据成员
    destory_hash(hash_list);    
    return 0;
}

运行结果：