[数据结构与算法]哈希表（散列表）的伟大之处！

导读：最近在看《redis源码设计和实现》，第二章数据结构里面字典的实现是哈希表（散列表），不由得想起之前在阅读《STL源码剖析》的时候，其hashtable和hashmap实现的底层原理也是哈希表，因此，来一探究竟！

哦对了，来宣传一波之前写的红黑树和哈希表实现的map和set的差异unordered_map和map的差异，希望有助于大家学习和进步。

为什么选哈希表？

为什么要用哈希表？其他查找方法缺点在哪里？

在线性表、树等数据结构中，记录在结构中的相对位置是随机的，和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较（查找的效率依赖于查找过程中所进行的比对次数）

想要不经过任何比较、一次存取就能得到所有记录，就必须在记录的存储位置和她的关键字之间建立一个确定的对应关系，使得每个关键字和结构中一个唯一的存储位置相对应。在哈希表中，这个对应的由来叫做哈希函数。

冲突：k1 ！= k2，f（k1）=f（k2）取余相同

根据设定的哈希函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便叫做哈希表，这一映像过程叫做哈希造表或散列表，所得的的存储位置成为哈希地址或散列地址

哈希表

哈希函数的构造方法

直接定址方法、数字分析法、平方取中法、折叠法、除留取余法、随机数法

处理冲突的方法

冲突不能避免，但是可以优化。

假设哈希表的地址集为0~（n-1），冲突是指由关键字得到的哈希地址为j的位置上已存在记录，则处理冲突的方法就是为该关键字的记录找到另一个“空”的哈希地址。

H = （H（key）+di）MOD（m）

开放定址法（对增量序列进行变化）

• 分为线性探测法：d = 1，2，3，4，…m-1
• 二次探测再散列：d = pow(1,2)，pow(2,2)，…pow(m-1,2)
• 伪随机探测法：d为伪随机数

线性探测法中很容易造成同义词、非同义词的聚集（堆积）现象，严重影响查找效率

再哈希法：H = RH（key）

在同义词冲突的时候计算另一个哈希函数地址，这种方法不易聚集，但是增加了计算的时间

链地址法：将所有关键词的记录存储在同一线性链表中

新建了链表，新的链表的头结点作为哈希桶的一个元素

建立一个公共溢出区（独立区域）

哈希表的查找及分析

在哈希表上进行查找的过程和哈希造表的过程基本一致。

给定key值，根据造表时的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定定值相同，则查找成功， 否则根据造表时候设定的处理冲突的方法找“下一地址”，直到哈希表中某个位置为“空”或者表中所填记录的关键字等于给定值为止

当删除的一个元素的时候，给该位置标记一个标记元素，否则查找遇到空会直接查找结束

平均查找长度（ASL）
一般查找长度和哈希函数、处理冲突的方法和哈希表的装填因子有关。

• 哈希函数的好坏首先影响出现冲突的频繁程度。
• 对设定相同的哈希函数，不同的处理冲突的方法得到的哈希表不同
• 在一般情况下，处理冲突的方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子

哈希表的ASL是哈希表的装填因子的函数，而不是n的函数，因此，不管n多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围内

实际查找效率分析

• 当成功的时候，求找的步数的平均值即可（即成功平均查找长度）
• 当查找失败的时候，计算所有的步数

code

code

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

#define DEFAULTSIZE 16

typedef struct ListNode {
    struct ListNode* next;
    int key;
    void* data;
}*list, *element;
typedef struct HashTable {
    int tableSize;
    list* theLists;
}HashTable;
/*
    @param: tableSize 桶的数量
    @return: 哈希表
*/
HashTable* initHashTable(int tableSize) {   
    int i = 0;
    HashTable* hashTable = NULL;
    if (tableSize <= 0) {
        tableSize = DEFAULTSIZE;
    }
    hashTable = (HashTable*)malloc(sizeof(HashTable));
    if (NULL == hashTable) {
        printf("allocate memory failed!\n");
        return NULL;
    }
    hashTable->tableSize = tableSize;
    hashTable->theLists = (list*)malloc(sizeof(list) * tableSize);
    if (NULL == hashTable->theLists) {
        printf("allocate memory failed!\n");
        free(hashTable);
        return NULL;
    }
    for (int i = 0; i < tableSize; i++) {
        hashTable->theLists[i] = (ListNode*)malloc(sizeof(ListNode));
        if (NULL == hashTable->theLists[i]) {
            printf("allocate memory failed!\n");
            free(hashTable->theLists);
            free(hashTable);
            return NULL;
        }
        else {
            // 初始化所有的结点为0
            memset(hashTable->theLists[i], 0, sizeof(ListNode));
        }
    }
    return hashTable;
}
void* getdata(ListNode* e) {
    return e != NULL ? e->data : NULL;
}
ListNode* find(HashTable* hashTable, int key) {
    int i = 0;
    list l = NULL;
    void* e = NULL;
    i = hash(key, hashTable->tableSize);
    l = hashTable->theLists[i];
    e = l->next;
    while (NULL != e && ((ListNode*)e)->key != key) {
        e = ((ListNode*)e)->next;
    }
    return ((ListNode*)e);
}
void deleteNode(HashTable* hashTable, int key) {
    ListNode* e = NULL, *last = NULL;
    list l = NULL;
    int i = hash(key, hashTable->tableSize);
    l = hashTable->theLists[i];

    last = l;
    e = l->next;
    while (e != NULL && e->key != key) {
        last = e;
        e = e->next;
    }
    if (e) {
        last->next = e->next;
        free(e);
    }
}
void destroy(HashTable* hashTable) {
    int i = 0;
    list l = NULL;
    ListNode* cur = NULL, *next = NULL;
    for (int i = 0; i < hashTable->tableSize; i++) {
        l = hashTable->theLists[i];
        cur = l->next;
        while (cur->next != NULL) {
            next = cur->next;
            free(cur);
            cur = next;
        }
        free(l);
    }
    free(hashTable);
}
void insert(HashTable* hashTable, int key, void* value) {
    ListNode* e = NULL, *tmp = NULL;
    list l = NULL;
    e = find(hashTable, key);
    if (NULL == e) {
        tmp = (ListNode*)malloc(sizeof(ListNode));
        if (NULL == tmp) {
            printf("allocate memory failed!\n");
            return;
        }
        // 前插法，找到头结点
        l = hashTable->theLists[hash(key, hashTable->tableSize)];   
        tmp->data = value;
        tmp->key = key;
        tmp->next = l->next;
        l->next = tmp;
    }
    else {
        printf("the node already exist\n");
    }
}
int main() {
    HashTable* hashTable = NULL;
    hashTable = initHashTable(31);
    return 0;
}

// hash function
int hash(int key, int tableSize) {
    return key % tableSize;
}