散列表

散列表：散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)，使用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。

Tips

• 散列技术既是一种存储方式，也是一种查找方法。
• 散列技术最适合的求解问题是查找和给定值相等的记录。

散列函数的构造方法

1.直接定址法
f(key) = a * key + b （a、b为常数）

2.数字分析法
比如电话号码199xxxx1234，其后四位分布较均匀，则可以取后四位1234作为关键字。还可以对抽取出来的数字做反转（1234改成4321）、右环位移（1234改成4123）、左环位移（1234改成2341）、前两位和后两位数叠加（12+34=46）等方法。

3.平方取中法
对数进行平方之后，取中间的几位数。如1234，平方之后的值为1522756，则取中间的三位227。

4.折叠法
比方说关键字是1234567890，散列表表长为3，将其分成四组，987|654|321|0，将其叠加123+456+789+0=1962，取后三位962即为散列地址。适合关键字数位较多的情况，事先不需要知道关键字的分布。

5.除留余数法
f(key) = key mod p （p<=m），即用关键字key对p求余，获取散列地址。通常p为小于或等于表长m的最小质数或不包含小于20质因子的合数。

6.随机数法
f(key) = random(key)，使用随机函数random对key产生散列地址。比较适合关键字长度不等的时候使用。

处理散列冲突的方法

1.开放定址法：

开发定址法有三种方式

线性探测法：一旦发生了冲突，就去寻找下一个空的散列地址，并将记录存入。
公式：fi(key) = (f(key) + di) MOD m（di = 1, 2, 3, .......,m-1）

因为线性探测法如果多次碰到不是同义词但需要抢夺同一个地址的情况，会产生堆积，所以为了减少产生堆积，还有二次探测法和随机探测法。

二次探测法：改进线性探测法的d，使di = 1^2, -1^2, 2^2, -2^2, ..., q^2, -q^2, q<=m/2，这样可以双向找到可能的空位置，减少堆积。
公式：fi(key) = (f(key) + di) MOD m（di = 1^2, -1^2, 2^2, -2^2, ..., q^2, -q^2, q<=m/2）

随机探测法：在冲突时，位移量di采用随机函数计算得到。
公式：fi(key) = (f(key) + di) MOD m（di是一个随机数）

2.再散列函数法

公式：fi(key) = RHi(key) （i = 1, 2, ..., k）
即使用多个函数求散列地址，这里的RH就是不同的散列函数，每当发生冲突时，就换一个散列函数求散列地址。

3.链地址法

使用邻接表结构，对关键字使用除留余数法后，如果余数相等，将其放在同一余数的链表上。

4.公共溢出法

将所有溢出的元素都存到溢出表中。查找时，先查找基本表的对应位置，如果没有的时候再到溢出表中寻找。

// 散列表
#include <stdio.h>
#include <malloc.h>

#define OK 1 // 执行成功

#define SUCCESS 1 // 查找成功
#define UNSUCCESS 0 // 查找失败

#define HASHSIZE 12 // 散列表表长
#define NULLKEY -32768 // 表示该位置无元素

typedef int Status; // 函数返回结果类型

int m = 0; // 散列表表长，全局变量

// 散列表结构
typedef struct {
    int *elem; // 存储数据远元素的数组
    int count; // 当前数据元素个数
} HashTable;

/**
 * 初始化散列表
 * @param H 散列表
 * @return 执行状态
 */
Status InitHashTable(HashTable *H) {
    int i; // 用来遍历元素
    m = HASHSIZE; // 设置全局散列表表长
    H->count = m; // 设置当前数据元素个数
    H->elem = (int *) malloc(m * sizeof(int)); // 初始化存储元素的数组

    // 设置散列表中所有元素为空
    for (i = 0; i < m; i++) {
        H->elem[i] = NULLKEY;
    }
    return OK;
}

/**
 * 散列函数
 * @param key 关键字
 * @return 对关键字求值后的散列地址
 */
int Hash(int key) {
    return key % m; // 除留余数法
}

/**
 * 插入关键字到散列表中
 * @param H 散列表
 * @param key 关键字
 */
void InsertHash(HashTable *H, int key) {
    int addr = Hash(key); // 求散列地址

    // 如果该位置的值不为空，则冲突，并向下一个位置移动
    while (H->elem[addr] != NULLKEY) {
        addr = (addr + 1) % m; // 开发定址法的线性探测
    }
    H->elem[addr] = key; // 直到有空位后插入关键字
}

/**
 * 在散列表中查找关键字
 * @param H 散列表
 * @param key 关键字
 * @param addr 散列地址
 * @return 查找成功或失败
 */
Status SearchHash(HashTable H, int key, int *addr) {
    *addr = Hash(key); // 求散列地址

    // 当散列表中该地址的元素不等于关键字
    while (H.elem[*addr] != key) {
        *addr = (*addr + 1) % m; // 开发定址法的线性探测

        // 当该位置的元素为空，或者重新回到回到初始散列地址
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) {
            return UNSUCCESS; // 查找失败
        }
    }
    return SUCCESS; // 查找成功
}

int main() {
    int arr[HASHSIZE] = {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34};
    int i, p; // i用来遍历元素，p用来存储元素地址
    int key; // key存储关键字
    Status status; // status存储执行状态
    HashTable H; // 哈希表



    InitHashTable(&H); // 初始化散列表
    for (i = 0; i < m; i++) {
        InsertHash(&H, arr[i]); // 将arr数组的元素插入散列表中
    }

    /************ 查找一个散列表中不存在的元素 ************/
    key = 39; // 设置查找关键字

    status = SearchHash(H, key, &p); // 在散列表中重找key所在位置

    if (status) {
        printf("查找元素%d的地址为：%d\n", key, p);
    } else {
        printf("查找元素%d失败", key);
    }

    /************ 查找散列表中存在的元素 ************/
    for (i = 0; i < m; i++) {
        key = arr[i]; // 设置查找关键字
        SearchHash(H, key, &p); // 在散列表中重找key所在位置
        printf("查找元素%d的位置为：%d\n", key, p);
    }

    return 0;
}

运行结果