(60)王道数据结构-散列查找

原文地址:散列查找

基本概念

散列（Hashing）通过散列函数（哈希函数）将要参与检索的数据与散列值（哈希值）关联起来，生成一种便于搜索的数据结构，我们称其为散列表（哈希表），也就是说，现在我们需要将一堆数据保存起来，这些数据会通过哈希函数进行计算，得到与其对应的哈希值，当我们下次需要查找这些数据时，只需要再次计算哈希值就能快速找到对应的元素了

散列函数

散列函数也叫哈希函数，哈希函数可以对一个目标计算出其对应的哈希值，并且，只要是同一个目标，无论计算多少次，得到的哈希值都是一样的结果，不同的目标计算出的结果介乎都不同。哈希函数在现实生活中应用十分广泛，比如很多下载网站都提供下载文件的MD5码校验，可以用来判别文件是否完整，哈希函数多种多样，目前应用最为广泛的是SHA-1和MD5，比如我们在下载IDEA之后，会看到有一个验证文件SHA-256校验和的选项，我们可以点进去看看

散列表

可以利用哈希值的特性，设计一张全新的表结构，这种表结构是专为哈希设立的，我们称其为哈希表（散列表）

我们可以将这些元素保存到哈希表中，而保存的位置则与其对应的哈希值有关，哈希值是通过哈希函数计算得到的，我们只需要将对应元素的关键字（一般是整数）提供给哈希函数就可以进行计算了，一般比较简单的哈希函数就是取模操作，哈希表长度是多少（长度最好是一个素数），模就是多少

哈希值是通过哈希函数计算得到的，我们只需要将对应元素的关键字（一般是整数）提供给哈希函数就可以进行计算了，一般比较简单的哈希函数就是取模操作，哈希表长度是多少（长度最好是一个素数），模就是多少

实现代码

#define SIZE 9

typedef struct Element {   //这里用一个Element将值包装一下
    int key;    //这里元素设定为int
} * E;

typedef struct HashTable{   //这里把数组封装为一个哈希表
    E * table;
} * HashTable;

int hash(int key){   //哈希函数
    return key % SIZE;
}

void init(HashTable hashTable){   //初始化函数
    hashTable->table = malloc(sizeof(struct Element) * SIZE);
    for (int i = 0; i < SIZE; ++i)
        hashTable->table[i] = NULL;
}

void insert(HashTable hashTable, E element){   //插入操作，为了方便就不考虑装满的情况了
    int hashCode = hash(element->key);   //首先计算元素的哈希值
    hashTable->table[hashCode] = element;   //对号入座
}

_Bool find(HashTable hashTable, int key){
    int hashCode = hash(key);   //首先计算元素的哈希值
    if(!hashTable->table[hashCode]) return 0;   //如果为NULL那就说明没有
    return hashTable->table[hashCode]->key == key;  //如果有，直接看是不是就完事
}

E create(int key){    //创建一个新的元素
    E e = malloc(sizeof(struct Element));
    e->key = key;
    return e;
}

int main() {
    struct HashTable hashTable;
    init(&hashTable);
    insert(&hashTable, create(10));
    insert(&hashTable, create(7));
    insert(&hashTable, create(13));
    insert(&hashTable, create(29));

    printf("%d\n", find(&hashTable, 1));
    printf("%d\n", find(&hashTable, 13));
}

哈希冲突

通过哈希函数计算得到一个目标的哈希值，但是在某些情况下，哈希值可能会出现相同的情况。

这种问题是很严重的，因为哈希函数的设计不同，难免会出现这种情况，这种情况是不可避免的，我们只能通过使用更加高级的哈希函数来尽可能避免这种情况，但是无法完全避免。当然，如果要完全解决这种问题，我们还需要去寻找更好的方法。

线性探针法

可以去找找哈希表中相邻的位置上有没有为空的，只要哈希表没装满，那么我们肯定是可以找到位置装下这个元素的，这种类型的解决方案我们统称为线性探测法，开放定址法包含，线性探测法、平方探测法、双散列法等，这里我们以线性探测法为例。

既然第一次发生了哈希冲突，那么我们就继续去找下一个空位：

$$
h_i(key) = (h(key) + d_i) % TableSize
$$
其中di是随着哈希冲突次数随之增加的量，比如上面出现了一次哈希冲突，那么就将其变成1表示发生了一次哈希冲突，然后可以继续寻找下一个位置

实现代码

void insert(HashTable hashTable, E element){   //插入操作，注意没考虑满的情况，各位小伙伴可以自己实现一下
    int hashCode = hash(element->key), count = 0;
    while (hashTable->table[hashCode]) {   //如果发现哈希冲突，那么需要继续寻找
        hashCode = hash(element->key + ++count);
    }
    hashTable->table[hashCode] = element;   //对号入座
}

_Bool find(HashTable hashTable, int key){
    int hashCode = hash(key), count = 0;   //首先计算元素的哈希值
    const int startIndex = hashCode;   //记录一下起始位置，要是转一圈回来了得停
    do {
        if(hashTable->table[hashCode]->key == key) return 1;  //如果找到就返回1
        hashCode = hash(key + ++count);
    } while (startIndex != hashCode && hashTable->table[hashCode]);  //没找到继续找
    return 0;
}

int main() {
    struct HashTable hashTable;
    init(&hashTable);
    for (int i = 0; i < 9; ++i) {
        insert(&hashTable, create(i * 9));
    }

    for (int i = 0; i < 9; ++i) {
        printf("%d ", hashTable.table[i]->key);
    }
}

链地址法

常见的哈希冲突解决方案是链地址法，当出现哈希冲突时，我们依然将其保存在对应的位置上，我们可以将其连接为一个链表的形式

1.通过结合链表的形式，哈希冲突问题就可以得到解决了，但是同时也会出现一定的查找开销

2.因为现在有了链表，我们得挨个往后看才能找到，当链表变得很长时，查找效率也会变低

3.可以考虑结合其他的数据结构来提升效率。

4.当链表长度达到8时，自动转换为一棵平衡二叉树或是红黑树，这样就可以在一定程度上缓解查找的压力了

实现代码

#define SIZE 9

typedef struct ListNode {   //结点定义
    int key;
    struct ListNode * next;
} * Node;

typedef struct HashTable{   //哈希表
    struct ListNode * table;   //这个数组专门保存头结点
} * HashTable;

void init(HashTable hashTable){
    hashTable->table = malloc(sizeof(struct ListNode) * SIZE);
    for (int i = 0; i < SIZE; ++i) {
        hashTable->table[i].key = -1;   //将头结点key置为-1，next指向NULL
        hashTable->table[i].next = NULL;
    }
}

int hash(int key){   //哈希函数
    return key % SIZE;
}

Node createNode(int key){   //创建结点专用函数
    Node node = malloc(sizeof(struct ListNode));
    node->key = key;
    node->next = NULL;
    return node;
}

void insert(HashTable hashTable, int key){
    int hashCode = hash(key);
    Node head = hashTable->table + hashCode;   //先计算哈希值，找到位置后直接往链表后面插入结点就完事了
    while (head->next) head = head->next;
    head->next = createNode(key);   //插入新的结点
}

_Bool find(HashTable hashTable, int key){
    int hashCode = hash(key);
    Node head = hashTable->table + hashCode;
    while (head->next && head->key != key)   //直到最后或是找到为止
        head = head->next;
    return head->key == key;   //直接返回是否找到
}

int main(){
    struct HashTable table;
    init(&table);

    insert(&table, 10);
    insert(&table, 19);
    insert(&table, 20);

    printf("%d\n", find(&table, 20));
    printf("%d\n", find(&table, 17));
    printf("%d\n", find(&table, 19));
}