🚀一、哈希表的原理精讲

🚢（一）概念

哈希表：也叫做散列表。是根据关键字和值（Key-Value）直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的一个存储位置，然后把键值对映射到哈希表上的对应位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（散列函数），用于存放记录的数组叫做 哈希表（散列表）。

哈希表是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法，本质上是由数组衍生而来，其核心就是哈希函数

几个核心概念：

• 键(key)： 组员的编号 如， 1 、 5 、 19 。 。 。
• 值(value)： 组员的其它信息（包含 性别、年龄和战斗力等）
• 索引：数组的下标(0,1,2,3,4) ，用以快速定位和检索数据，同时可以把该数组称为索引数组
• 哈希函数：将组员编号映射到索引上，一般采用求余法

图中，Key为28，通过哈希函数计算存放在哈希表中的位置，得到索引为：28 % 5 = 3，但是如此的话就会造成一个问题：如果还有个学生的学号为33，通过哈希函数计算后得到的数组存放位置下标也为3，这种情况就是待会要讲的哈希冲突

🚢（二）常见哈希函数的构造方法

1.直接定址法

如果我们现在要对0～100岁的人口数字统计表，如表8-10-1所示，那么我们对年龄这个关键字就可以直接用年龄的数字作为地址。此时f (key) =key。

如果我们现在要统计的是80后出生年份的人口数，如表8-10-2所示，那么我们对出生年份这个关键字可以用年份减去1980来作为地址。此时f (key)=key-1980。

也就是说，我们可以取关键字的某个线性函数值为散列地址，即f (key) =axkey+b (a、b为常数)
这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

2.数字分析法

例如当手机号码为关键字时，其11位数字是有规则的，此时是无需把11位数值全部当做散列地址，这时我们给关键词抽取， 抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

3.平方取中法

这个方法计算很简单，假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用做散列地址。再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671，也可以是710，用做散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

4.除留余数法

这是一种最简单、最常用的方法，假定散列表表长为m mm，取一个不大于m mm但最接近或等于m mm的质数p pp，利用以下公式把关键字转换成散列地址。散列函数为H ( k e y ) = k e y % p ( p < = m ) 事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。
除留余数法的关键是选好p pp，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

5.随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是H ( k e y ) = r a n d o m ( k e y ) 这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
 

🚢（三）哈希冲突与处理方法

哈希函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计的好的哈希函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

1.开放地址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

它的公式是:
$f_i(key)=(f(key)+d_i)MODm(d_i=1,2,3,......,m-1)$

2.链地址法

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

例如，关键字序列为{ 12 , 67 , 56 , 16 , 25 , 37 , 22 , 29 , 15 , 47 , 48 , 34 } {12, 67, 56, 16, 25, 37, 22, 29,15, 47,48, 34}{12,67,56,16,25,37,22,29,15,47,48,34}，我们用除留余数法构造散列函数H ( k e y ) = k e y % 12 ，用拉链法处理冲突，建立的表如下图所示。

我们将每一条链表称为哈希桶，数组成员为每一个索引值相同的多个元素

3.公共溢出区法

这个方法其实就更加好理解，就是把凡是冲突的家伙额外找个公共场所待着。我们为所有冲突的关键字建立了一个公共的溢出区来存放。

就前面的例子而言，我们共有三个关键字37 , 48 , 34 {37,48,34}37,48,34与之前的关键字位置有冲突，那么就将它们存储到溢出表中，如下图所示。

如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

🚀二、哈希表的算法实现

为了减少哈希冲突的现象出现，这里我们就讲解一下链地址这种处理方法的实现，一般我们称为哈希链表

1.哈希链表的结构体定义

#define DEFAULT_SIZE 16 //哈希桶的数量

//结点结构
typedef struct _ListNode {
    struct _ListNode *next;
    int key;
    void *data;
}ListNode;

typedef ListNode *List;
typedef ListNode *Element;

//哈希链表结构
typedef struct _HashTable {
    int TableSize;
    List *Thelists;
}HashTable;

2.哈希函数

/*根据 key 计算索引，定位 Hash 桶的位置*/
int Hash(int key, int TableSize)
{
	return (key%TableSize);
}

3.初始化哈希表

/*初始化哈希表*/
HashTable *InitHash(int TableSize)
{
    int i = 0;
    HashTable *hTable = NULL;
    
    if (TableSize <= 0) {
    	TableSize = DEFAULT_SIZE;
    }
    
    hTable = (HashTable *)malloc(sizeof(HashTable));
    if (NULL == hTable)
    {
        printf("HashTable malloc error.\n");
        return NULL;
    }
    hTable->TableSize = TableSize;
    
    //为 Hash 桶分配内存空间，其为一个指针数组
    hTable->Thelists = (List *)malloc(sizeof(List)*TableSize);
    if (NULL == hTable->Thelists)
    {
        printf("HashTable malloc error\n");
        free(hTable);
        return NULL;
    }
    
    //为 Hash 桶对应的指针数组初始化链表节点
    for (i = 0; i < TableSize; i++)
    {
        hTable->Thelists[i] = (ListNode *)malloc(sizeof(ListNode));
        if (NULL == hTable->Thelists[i])
        {
        printf("HashTable malloc error\n");
        free(hTable->Thelists);
        free(hTable);
        return NULL;
        }
    	else
        {
        	memset(hTable->Thelists[i], 0, sizeof(ListNode));
        }
    }
    
    return hTable;
}

4.哈希表插入元素

/*哈希表插入元素，元素为键值对*/
void Insert(HashTable *HashTable, int key, void *value )
{
    Element e=NULL, tmp=NULL;
    List L=NULL;
    e = Find(HashTable, key);
    
    if (NULL == e)
    {
        tmp = (Element)malloc(sizeof(ListNode));
        if (NULL == tmp)
        {
            printf("malloc error\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 key already exist\n");
}

5.哈希表查找元素

/*从哈希表中根据键值查找元素*/
Element Find(HashTable *HashTable, int key)
{
    int i = 0;
    List L = NULL;
    Element e = NULL;
    i = Hash(key, HashTable->TableSize);
    L = HashTable->Thelists[i];
    e = L->next;
    while (e != NULL && e->key != key)
    	e = e->next;
   
    return e;
}

6.哈希表删除元素

/*哈希表删除元素，元素为键值对*/
void Delete(HashTable *HashTable, int key )
{
    Element 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;
        delete(e);
    }
}