散列表概念

基本思想是通过由散列函数决定的键值与散列地址之间的对应关系来实现存储组织和查找运算。既是一种存储方式，又是一种查找方法。
散列技术时需要考虑的两个主要问题是：①如何构造（选择）"均匀的"散列函数？②用什么方法解决冲突？

如何构造散列函数

直接地址法
直接地址法是以关键字key本身或关键字加上某个常量C作为散列地址的方法。对应的散列函数H(key)为：H(key)=key+C
特点：方法计算简单，并且没有冲突。它适合于关键字的分布基本连续的情况，若关键字分布不连续，空号较多，将会造成较大的空间浪费。
数字分析法
数字分析法是假设有一组关键字，每个关键字由n位数字组成，数字分析法是从中提取数字分布比较均匀的若干位作为散列地址。
除余数法
除余数法是一种最简单也最常用的一种散列函数构造方法。散列函数：H(k)=k％p
其中，p最好选取小于或等于表长m的最大素数。
平方取中法
取关键字平方的中间几位作为散列地址的方法
折叠法
折叠法是首先把关键字分割成位数相同的几段(最后一段的位数可少一些)，段的位数取决于散列地址的位数，由实际情况而定，然后将它们的叠加和(舍去最高进位)作为散列地址的方法。
关键字k=98 123 658，散列地址为3位，则将关键字从左到右每三位一段进行划分，得到的三个段为981、236和58，叠加后值为1275，取低3位275作为关键字98 123 658的元素的散列地址

处理冲突的方法

开放定址法

开放定址法的思想：使用某种方法在散列表中形成一个探查序列，沿着此序列逐个单元进行查找，直到找到一个空闲的单元时将新结点存入其中。

线性探插法

探查序列可以由下述公式得到：di=(d+i) % m
其中：di表示第i次探查的地址，m表示散列表的长度。

二次探查法

二次探查法的探查序列为：
d0=H（K），
d1=（d0+1^2）% m
d2=（d0 -1^2）% m，
d3=（d0+2^2）% m，
d4=（d0 -2^2）% m，
……

双重散列法

双重散列法是几种方法中最好的方法，它的探查序列为：hi=（H（key）+iH1（key））％m （0≤i≤m-1）
即探查序列为：d=H（key），（d+lH1（key））％m，（d+2*H1（key））％m，…等。

拉链法(链地址法)

把具有相同散列地址的关键字（同义词）值放在同一个单链表中，称为同义词链表。

例子

设散列函数为h（key）=key％1l；，对关键字序列{27，13，55，32，18，49，24，38，43），用拉链法构造散列表，并计算查找成功时的平均查找长度。在这里插入图片描述

散列表查找

开放定址法数据结构

# define M 997 //M定义为表长，一般M为一个素数
typedef struct { //定义散列表结点类型
    KeyType key;
    DataType data;
} NodeType;
typedef NodeType HashTable[M]; //散列表类型

线性探查法查找算法

int HashSearchl(HashTable HT, KeyType K, int m)
{
    //在长度为m的散列表HT中查找关键字值为K的元素位置
    int d, temp;
    d = K % m; //计算散列地址
    temp = d; //temp作为哨卡,防止进入重复循环
    while (HT[d].key != -32768) { //当散列地址中的key域不为空,则循环
        if (HT[d].key == K)
            return d; //查找成功返回其下标d
        else
            d = (d + 1) % m; //计算下一个地址
        if (d == temp)
            return -1; //查找一周仍无空位置,返回-1表示失败
    }
    return d; //遇到空单元,查找失败
}

插入算法

int HashInsertl(HashTable HT, NodeType s, int m)
{
    //在HT表上插入一个新结点s
    int d;
    d = HashSearchl(HT, s.key, m); //查找插入位置
    if (d == -1) return -1; //表满,不能插入
    else {
        if (HT[d].key == s.key)
            return 0; //表中已有该结点!
        else { //找到一个开放的地址
            HT[d] = s; //插入新结点S
            return 1; //插入成功
        }
    }

}

拉链法数据结构定义

typedef struct node { //定义结点类型
    KeyType key;
    DataType data;
    struct node *next;
} HTNode;

typedef HTNode *HT[M];  //定义散列表类型

查找算法

HTNode *HashSearch2(HT T, KeyType K, int m)
{
    //在长度为m的散列表T中查找关键字值为K的元素位置
    HTNode *p = T[K%m]; //取K所在链表的头指针
    while (p != NULL && p->key != K)
        p = p->next; //顺链查找
    return p; //查找成功p指向K结点的位置,不成功返回NULL
}

插入算法

int HashInsert2(HT T, HTNode *s, int m)
{
    //采用头插法在T表上插入一个新结点
    int d;
    HTNode *p = HashSearch2(T, s->key, m); //查找表中有无待插结点
    if (P != NULL) return 0; //说明表中已有该结点
    else { //将*s插入在相应链表的表头上
        d = s->key % m;
        s->next = T[d];
        T[d] = s;
        return 1; //说明插入成功
    }
}