哈希表

哈希表

2019 年 03 月 04 日

1143 次浏览

3110字数

1. 什么是哈希表

哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的索引index。

使用散列的查找算法分两步。第一步是用散列函数将被查找的键转换为数组的一个索引。理想情况下不同的键都能被转化为不同的索引，但现实是我们必须考虑不同的键对应到同一个索引上的情况。因此，散列查找的第二步就是一个处理碰撞冲突（collison-resolution）的过程。在之后我们会学到两种处理冲突的方法：拉链法和线性探测法。

2. 散列函数

如果我们有一个能保存M个键值对的数组，那么我们就需要一个能将任意键转换为该数组范围内的索引（[0, M-1]范围内的整数）的散列函数。我们要找的散列函数应该易于计算并且能够均匀分布所有键。

散列函数和键的类型有关。

2.1. 正整数

将整数散列最常用的方法是除数留余法。我们选择大小为素数M的数组，对于任意正整数k，计算k除以M的余数。这个函数非常容易计算（对于编程语言来说），并且能够有效地将键散布到0到M-1的范围内。为什么M一般要取素数呢？因为如果键取了非素数，那么可能无法利用键中所包含的所有信息。举个例子，M取非素数100，那么可以想到对于任意键被散列后的值其实只取决于键的后两位，而跟前面所有位没有任何关系，这时如果你的键的所有可能取值的后两位都比较接近，那么就势必会造成大量的碰撞冲突，而M取素数则分布会显得更好。

2.2. 浮点数

一个比较好的方法是将键转化为二进制然后再使用除数留余法。

2.3. 字符串

除数留余法也可以运用在字符串上。

int hash = 0;
for(int i=0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;

3. 解决碰撞冲突

3.1. 线性探测法

建立两个数组keys和values。keys[]用于存储键值，而values[index]值为1时表示对应的keys[index]里存在数据，而为0时表示keys[index]里没有数据。

#include <stdio.h>
#define HTCAPACITY 50000

int hash(int key) {
        int ret = key % HTCAPACITY;
    return (ret < 0)?(ret + HTCAPACITY):(ret);
}

void htInsert(int *keys, int *values, int key) {
    int index = hash(key);

    while(values[index])
        index = (index + 1) % HTCAPACITY;
    keys[index] = key;
    values[index] = 1;
}

int htSearch(int *keys, int *values, int key) {
    int index = hash(key);

    while(values[index]) {
        if(keys[index] == key)
            return index;
        index = (index + 1) % HTCAPACITY;
    }
    return -1;
}

void print(int *keys, int *values) {
    int i = 0;

    for(; i<HTCAPACITY; i++) {
        printf("[%d] %d\n", i, (values[i])?(keys[i]):(-1));
    }
}

3.2. 拉链法

#include <stdio.h>
#include <stdlib.h>
#define HTCAPACITY 23

typedef struct _htItem
{
    struct _htItem *nextItem;  // NULL if no next
    int key;
}htItem;

// initialize hash table
// 将每个头节点初始化为NULL指针
void htInit(htItem **ht) {
    int i = 0;
    for(; i<HTCAPACITY; i++) {
        ht[i] = NULL;
    }
}

// caculate the key of giving number
int hash(int key) {
    int ret = key % HTCAPACITY;
    return (ret < 0)?(ret + HTCAPACITY):(ret);
}


// insert a key to hash table
void htInsert(htItem **ht, int key) {
    int index = hash(key);
    htItem *tmp = ht[index];

    if(tmp == NULL) {  // 如果指针为NULL，则哈希表中该索引下还没有任何key
        ht[index] = (htItem *)malloc(sizeof(htItem));
        ht[index]->nextItem = NULL;
        ht[index]->key = key;
    } else {
        while(tmp->nextItem)
            tmp = tmp->nextItem;
        tmp->nextItem = (htItem *)malloc(sizeof(htItem));
        tmp->nextItem->nextItem = NULL;
        tmp->nextItem->key = key;
    }
}


// search in hash table
// return NULL if dont exist
htItem* htSearch(htItem **ht, int key) {
    int index = hash(key);
    htItem *tmp = ht[index];
    while(tmp) {
        if(tmp->key == key)
            return tmp;
        tmp = tmp->nextItem;
    }
    return NULL;
}


// delete a key in hash table
void htDelete(htItem **ht, int key) {
    int index = hash(key);
    htItem *tmp = ht[index];

    if(tmp) {
        if(tmp->key == key) {  // head node is the target
            ht[index] = tmp->nextItem;
        } else {
            while((tmp->nextItem) && (tmp->nextItem->key != key))
                tmp = tmp->nextItem;
            if(tmp->nextItem) {
                tmp->nextItem = tmp->nextItem->nextItem;
            } else {
                printf("key dont exist!\n");
            }
        }
    } else {
        printf("Key dont exist!\n");
    }    
}


void print_hashTable(htItem **ht) {
    int index = 0;
    htItem *tmp = NULL;
    for(; index < HTCAPACITY; index++) {
        tmp = ht[index];
        printf("[%d] ", index);
        while(tmp) {
            printf("-> %d ", tmp->key);
            tmp = tmp->nextItem;
        }
        printf("\n");
    }
    printf("-----------------------------\n");
}


int main(int argc, char const *argv[])
{
    htItem **ht = (htItem **)malloc(sizeof(htItem*) * HTCAPACITY);
    htInit(ht);
    htInsert(ht, 10);
    htInsert(ht, 33);
    print_hashTable(ht);
    htDelete(ht, 33);
    print_hashTable(ht);

    return 0;
}

哈希表