数据结构---哈希表

2024-01-14 18:36:22

前言

在总结了链表和集合这两种抽象的数据结构后，接下总结的一种数据结构是哈希表。哈希表支持一种高效的检索方式：散列。从根本上来说，一个哈希表包含一个数组，可以通过特殊的索引值来访问数组中的值。哈希表的主要思想是利用哈希函数，在所有键值和槽之间建立一个映射表，哈希表每次都接受一个键然后返回一个相对应的哈希编码。键的值可以多种多样，但是哈希值只能是整型（java的存储方式就是哈希表存储以提高查找速度）

为什么使用哈希表

由于计算哈希值和数组中进行索引都只消耗固定的时间，换句话说就是时间复杂度为 \(O(1)\) 所以哈希表的最大的优点他是一种运行时间为常数的检索方法，当哈希函数可以保证输入不同的键值和得到哈希值都不同时，那么哈希表就可以直接寻址得到结果。但是在实际上输入不同的键值的可能得到相同的槽位，这就是哈希冲突的发生，而且从信息的存储的角度，我们也不希望每个键值都有不同的哈希值，例如名字键值是一个长度为8的字符，每个字符可以取26个可能字符A,B,C...，那么这个哈希表将会有\(26^8 = 2.09*10^{11}\)的条目，但是这个当中许多名字是无用的。这样尽管提高了速度，但是造成空间的大大浪费。通常情况下，哈希表的条目比他的键值少，即大多数的哈希函数会将一些不同的键映射到相同的哈希值上，一个好的哈希函数会尽量的减低这种冲突的发生，但是冲突是不可避免的 。所以我们采用一些结构在解决这种冲突的影响，本文就简单的介绍几种哈希表结构，它们以不同的方式来解决哈希冲突。

  • 链式哈希表

    • 将数据存储在一个个桶中的哈希表。每个桶都是一个链表，而链表的长度随着这个桶对应的哈希值发生冲突而增加。

  • 开地址哈希表

    • 将数据存储在表本身，通过探查方法来避免冲突问题。

链式哈希表的描述

链式哈希表的本质可以理解为一组链表组成的桶，我们把每个元素通过散列的方式 放在不同的木桶当中。在插入新元素的时候，先把键值转入一个哈希函数得到一个哈希值，这个哈希值决定这个元素到最后进到那个元素中（桶中），然后在相应的链表头当中插入元素。当然遍历和查找，删除元素的时候也通过相同的方式查找元素进行操作。每一个桶都是一个链表，这就是表示了链式哈希表并没有限制包含元素的个数。但是如果一个桶的元素长度太多，就会使得哈希表的性能下降，下图是链式哈希表的结构模型图。
数据结构---哈希表

解决冲突

链式哈希表解决冲突的方式很简单，当发生冲突的时候，就把元素放在相对应的桶上的链表上，当这个桶发生一个冲突就把这个桶的链表加长。那有没有一种可能就是一个桶的深度远远大于其他桶，那让访问这个桶的时候造成时间十分长。比如我们设置一个查询失败时间，那这个失败时间肯定是查询这个哈希表最深的桶决定的（有点类似木桶原理）。在实际中我们希望每一个桶都是均匀增长的，这种在理论上我们称为均匀散列。而且必须注意的一点的是，如果数据类很大的时候，即使我们的哈希表是均匀增长的，但是随着木桶的深度的增大，这个哈希表的性能也会快速降低。为了定量的计算这个哈希表可能支持的数量量数，可以定义一个参考值负载因子其计算公式为：

\[\alpha = \frac{n}{m} \n:定义为元素的数量 \m:定义为桶的数量 \]

但是必须注意的这个是理论中达到均匀散列下的理想负载因子，在实际中要小于这个负载因子。如何可以使得哈希表更好的接近均匀散列重点就是在于如何的选择哈希函数？

哈希函数的选择

线性函数

一个很正常的方法就是定义线性函数\(h(k)\):

\[h(k) = x \]

一般的情况下，\(h(k)\)的\(k\)的取值都是正整数，当\(k\)不是正整数的时候也可以使用强制转换将\(k\)变成正整数。但是如何取键的特性作为转换为\(k\)值就是一个值得考虑的问题，比如有一组电话号码。13开头和15开头17开头的如果利用前两个数字作为键值，这样就会导致有很多的号码对应一个键值，显然这个是不符合我们期望的。

取余法

另一个常用的方法是取余法

\[h(k) = k \ mod \ m \]

有一个整数型的k值，对哈希表的长度m取余得到哈希表的哈希值。这里值的注意一点的是这个m的取值。 取余运算的本质无非是个减去种子n倍的减法。那么做减法的时候，种子中间大段的0或1就会让哈希原值的中间一段，有非常大的可能性仍然保持原样，对于hash函数在进行运算后，哈希值还保留着原键值的特征这明显是不好了。因为哈希函数就是让键映射到哈希值，这个哈希值最好是无规律的无序，均匀的，不可逆推的。 如果做完哈希运算之后，哈希值和原值中间居然有一大段二进制位保持不变，那么这个哈希函数就可以说是失败到不能再失败了。 而且还有一点就是如果输入的数据只有高位的信息发生变化的话，那么我利用\(2^m\)为取余数活会大大提高发生哈希冲突的可能，比如取余数为256，键值只有高位发生变化的可能性比较高，那么$\frac{257}{256}=1, \frac{513}{256}=1，\frac{769}{256}=1 $。那为什么要取质数了？这些我还没有找出准确的数学证明，不过貌似取质数可以使得分布更为均匀。

链式哈希表的接口函数

  • int chtbl_init(CHTbl* htbl, int buckets, int (*h)(const void* key), int (*match)(const void* key, const void* key2), void (*destory)(void* data));

    • 返回值：初始化成功，返回0，不成功返回-1。
    • 描述：初始化htbl指定的哈希表，对哈希表进行操作之前必须先初始化哈希表，表中的buckets决定了桶数。函数h指向一个哈希函数以便对键值进行散列。match函数对两个数据进行匹配，destroy对表的bucket中的数据进行释放。
    • 时间复杂度：\(O(m)\) \(m\)为哈希表中bucket的数目

  • void chtbl_destory(CHTbl* htbl);

    • 描述：对哈希表进行销毁
    • 时间复杂度：\(O(m)\) \(m\)为哈希表中bucket的数目

  • int chtbl_insert(CHTbl* htbl,const void *data);

    • 返回值：插入成功返回0，失败返回-1
    • 描述：对哈希表插入元素，由于理想的哈希表不允许又相同的哈希值，所以在插入元素前先对表进行look_up判断。
    • 时间复杂度：\(O(1)\)

  • int chtbl_remove(CHTbl* htbl, const void** data)

    • 返回值：移除成功返回0，失败返回-1
    • 描述对哈希表进行移除
    • 时间复杂度：\(O(1)\)

  • int chtbl_look_up(CHTbl* htbl, const void** data)

    • 返回值：成功返回0，失败返回-1
    • 描述对哈希表进行查找
    • 时间复杂度：\(O(1)\) 固定时间

实现代码

#pragma once
#ifndef CHTBL_H
#define CHTBL_H
#include <stdlib.h>
#include "list.h"

// 定义一个哈希表的结构
typedef struct CHTbl_ 
{
	int buckets;
	int (*h)(const void* key);
	int (*match)(const void* key, const void* key2);
	void (*destory)(void* data);
	int size;
	List* table;
}CHTbl;

// 公共接口
int chtbl_init(CHTbl* htbl, int buckets, int (*h)(const void* key), int (*match)(const void* key, const void* key2), void (*destory)(void* data));
void chtbl_destory(CHTbl* htbl);
int chtbl_insert(CHTbl* htbl,const void *data);
int chtbl_remove(CHTbl* htbl, const void** data);
int chtbl_look_up(CHTbl* htbl, const void** data);

#define chtbl_size(htbl) ((htbl)->size)
#endif // !chtbl_h



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

#include "list.h"
#include "chtbl.h"


// 公共接口的实现

/*chtbl_init 哈希表初始化*/
int chtbl_init(CHTbl* htbl, int buckets, int (*h)(const void* key), int (*match)(const void* key, const void* key2), void (*destory)(void* data))
{
	// 为哈希表分配内存
	if ((htbl->table = (List*)malloc(sizeof(List) * buckets)) == NULL)
	{
		return -1;
	}
	// 初始化成功
	htbl->buckets = buckets;
	for (int i = 0; i < htbl->buckets; i++)
	{
		list_init(&htbl->table[i], destory);
	}
	htbl->h = h;
	htbl->match = match;
	htbl->destory = destory;
	htbl->size = 0;
}


/*chtbl_destory 摧毁*/
void chtbl_destory(CHTbl* htbl) 
{
	for (int i = 0; i < htbl->buckets; i++) 
	{
		list_destroy(&htbl->table[i]);
	}
	free(htbl->table);
	memset(htbl, 0, sizeof(CHTbl));
	return ;
}

/*chtbl_insert 哈希表插入*/
int chtbl_insert(CHTbl* htbl, const void* data)
{
	void* temp;
	int bucket;
	int retval;

	temp = (void*)data;

	if (chtbl_look_up(htbl, &temp) == 0)
	{
		return -1;
	}
	bucket = htbl->h(data) % htbl->buckets;
	if (retval = (list_ins_next(&htbl->table[bucket], NULL, data)) == 0)
	{
		htbl->size++;
	}
	return retval;
}


int chtbl_remove(CHTbl* htbl, const void** data)
{
	ListElement* element;
	ListElement* prev;
	int bucket;

	bucket = htbl->h(*data) % htbl->buckets;
	//查找元素
	prev = NULL;

	for (element = list_head(&(htbl->table[bucket])); element != NULL; element=list_next(element))
	{
		if (htbl->match(*data, list_data(element))) 
		{
			if ((list_rem_next(&(htbl->table[bucket]), prev, data) == 0))
			{
				htbl->size--;
				return 0;
			}
			else 
			{
				return -1;
			}
		}
		prev = element;
	}
	return -1;
}

/*查找哈希表的元素*/
int chtbl_look_up(CHTbl* htbl, const void** data) 
{
	ListElement* element;
	int bucket;

	bucket = htbl->h(*data) % htbl->buckets;
	for (element = list_head(&(htbl->table[bucket])); element != NULL; element = list_next(element)) 
	{
		if (htbl->match(*data, list_data(element)))
		{
			*data = list_data(element);
			return 0;
		}
	}
	return -1;
}

数据结构---哈希表

上一篇：[LeetCode] 1257. Smallest Common Region


下一篇：并发编程-FutureTask&CompletableFuture