数据结构-哈希

什么是哈希?

哈希是用来查找的一个搜索结构。一般的算法是通过比较来找数据的,但是哈希查找不用比较就可以一次直接从事先建好的哈希表中找到数据。

来看下使用各搜索算法的时间复杂度和空间复杂度:

所以哈希算法就是一种用空间换时间的算法


哈希的实现方式:

通过对要存入的数据进行key-value的映射到数组中的第key个位置。

例子:

        有一个int arr[ 10 ]数组,存入10, 11, 24, 13这些元素,我们可以通过一种映射方式,将要存入的数据和arr数组的下标建立关系以便查找的时候直接通过这种关系找到相应的数据。对于以上数据,就可以使用num(表示要存入的数据) % 5来将这些数存入计算的结果(数组下标)相应位置,比如10就可以存入arr[0],因为10 % 10 = 0, 同样arr[ 1 ] = 11,arr[ 3 ] = 13,arr[ 4 ] = 24; 在以上数组中查找元素的时候,就可以使用刚才的方法,比如我要看12在不在数组中,12 % 5 = 2,但是arr[ 2 ] = 0(一开始都会初始化为一个值,或者使用一个状态来标记数组的相应位置),所以12不在数组中。查找13 % 5 = 3,arr[ 3 ] = 13,所以13在数组中。 

以上Hash(value) = value % m被称为哈希函数。通过哈希函数计算出的数组称为哈希表。


哈希冲突:

对于int arr[ 10 ] = {10, 11, 0, 13, 24, 0, 0, 0, 0, 0},这个哈希表,当我们插入14的时候,放的位置应该是arr[4]

但是arr[ 4 ]已经有元素了,这种情况就叫哈希冲突,解决这个问题我们可以增大数组,使用 int arr[ 50 ];

然后哈希函数为Hash(value)  = value % 50; 这样就不会出现以上的冲突了,当然这只是其中一种方法,而且非常不实用,在插入的元素值相差非常大的时候,这种方法会非常浪费空间。另一种方法是改变哈希函数。


常见哈希函数:

好的哈希函数能将哈希冲突降到最小,但是无法避免哈希冲突。

哈希函数的设计原则:

  1. 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
  2. 哈希函数计算出来的地址能均匀分布在整个空间中
  3. 哈希函数应该比较简单  

常见的哈希函数有以下几个:

直接定值法(线性函数):

取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B  

优点:简单、均匀  

缺点:需要事先知道关键字的分布情况  适合查找比较小且连续的情况

应用:找出字符串中出现次数最多的字符,或者只出现一次的字符(字符ASCII码作为数组下标,遇到一个相应元素个数++,最后再遍历一次数组)

除留余数法 :

设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:

Hash(key) = key% p(p<=m),将关键码转换成哈希地址,例子中用到的就是除留余数法。

平方取中法:
假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址;  
再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址  

平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况

折叠法 :
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表
长,取后几位作为散列地址  

折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况。

随机数法:  
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数  

通常应用于关键字长度不等时采用此法

数学分析法 :
设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均
匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分

布均匀的若干位作为散列地址。例如存储手机号。


处理哈希冲突:

解决哈希冲突的常见方法是:闭散列和开散列。

闭散列:

当放入的地址冲突后,如果哈希表未满,则向后寻找空位置放。

例如对于:int arr[ 10 ] = {10, 11, 0, 13, 24, 0, 0, 0, 0, 0},当要放入14的时候,发现14的位置被24占了,就直接找下一个空位置。也就是arr[ 5 ] = 14,要放入20的时候就要放在arr[ 2 ]的位置上了。但是这种方法的一旦很多数据连在一起,比如连续放入,14 25 26 27 28 29的时候,很多元素都不在正确的位置。大大降低了哈希表的效率。

解决这个问题的方法是使用二次探测( i * i),i 从 1 开始,开始那个方法可以称为一次探测(线性探测),每次找空位置的时候都是使用 i++

二次探测:

二次探测是先 i++, 然后 i * i, 看结果是否为空,不为空继续向后。

研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只

要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5(元素个数 / 空间总大小 <= 0.5);如果超出必须考虑增容

开散列:

开散列法又叫链地址法(开链法)。  

开散列法:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。



开散列的具体实现:

下面是开散列的实现方法:

设置的装载因子(插入的元素和空间大小之比)为0.7,大于此值就自动扩容,扩容是按照素数表中的数据来扩容的。

操作:

  1. 初始化哈希表(申请空间,初始化空间);
  2. 哈希函数(用来计算插入的位置)
  3. 向哈希表插入元素(根据哈希函数计算的结果)
  4. 判断元素是否在哈希表中
  5. 删除哈希表中的某个元素
  6. 打印哈希表
  7. 销毁哈希表

Hashtable.h头文件:

#pragma once
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
typedef unsigned int size_t;
// 哈希表节点中的数据项
typedef int HashDataType;

// 哈希表的节点
typedef struct HashNode {
	HashDataType data;
	struct HashNode* next;
}HashNode, *PHashNode;

// 哈希表
typedef struct Hashtable {
	// 哈希表,是一个节点数组
	PHashNode* elements;
	// 哈希表的最大容量
	size_t capacity;
	// 哈希表当前元素个数
	size_t size;
}Hashtable;

// 使用素数表对齐做哈希表的容量,降低哈希冲突
#define  _PrimeSize 11
static const unsigned long _PrimeList[_PrimeSize] = {
	 11ul, 23ul, 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul
};

// 初始化哈希表
void initHashtable(Hashtable** table, size_t capacity);
// 向哈希表插入元素
void putElemIntoHashtable(Hashtable** table, HashDataType data);
void putElemIntoHashtableNew(Hashtable* table, PHashNode node);
// 取得哈希表中的元素
HashDataType getElemFromHashtable(Hashtable* table, HashDataType data);
// 用来计算哈希码的函数
size_t intHashFunc(size_t capacity, HashDataType data);
// 删除哈希表中的某个元素
void deleteElemFromHashtable(Hashtable* table, HashDataType data);
// 打印哈希表中的元素
void printHashtable(Hashtable* table);
// 获取下一个容量
size_t getPrimeCapacity(Hashtable* table);
// 获取节点
PHashNode buyNode(data);
// 检测哈希表的元素是否满了(插入元素个数 / 总空间大小 > 0.7)
int isFull(Hashtable* table);
// 销毁哈希表
void destroyHashtable(Hashtable** table);

初始化哈希表(申请空间,初始化空间);

// 初始化哈希表
void initHashtable(Hashtable** table, size_t capacity) {
	*table = (Hashtable*)malloc(sizeof(Hashtable));
	if (*table == NULL) {
		assert(0);
		exit(0);
	}
	(*table)->capacity = capacity;
	(*table)->size = 0;
	(*table)->elements = (PHashNode*)malloc(sizeof(PHashNode*)*(*table)->capacity);
	// 节点置空
	for (int i = 0; i < (*table)->capacity; ++i) {
		(*table)->elements[i] = NULL;
	}
}

哈希函数(用来计算插入的位置),使用了除留余数法,模空间的容量(数组大小)

// 用来计算哈希码的函数
size_t intHashFunc(size_t capacity, HashDataType data) {
	return data % capacity;
}

向哈希表插入元素(根据哈希函数计算的结果进行头插,头插效率高),以及扩容

// 向哈希表插入元素
void putElemIntoHashtable(Hashtable** table, HashDataType data) {
	if (table == NULL)
		return;
	size_t len = (*table)->capacity;
	PHashNode insertNode = buyNode(data);

	// 元素插满了,扩容
	if (isFull((*table))) {
		// 先将当前元素插入
		size_t newCapacity = getPrimeCapacity((*table));
		Hashtable* newTable = (Hashtable*)malloc(sizeof(Hashtable));
		initHashtable(&newTable, newCapacity);
		putElemIntoHashtableNew(newTable, insertNode);

		// 找到每一个非空元素,直接赋值给新哈希表
		for (int i = 0; i < len; ++i) {
			PHashNode Cur = (*table)->elements[i];
			while (Cur) {
				PHashNode tmp = Cur->next;
				putElemIntoHashtableNew(newTable, Cur);
				Cur = tmp;
			}
		}

		// 将旧哈希表的指针指向新哈希表
		(*table) = newTable;
		(*table)->size = newTable->size;
		(*table)->capacity = newTable->capacity;
		return;
	}
	else{
		size_t pos = intHashFunc((*table)->capacity, data);
		insertNode->next = (*table)->elements[pos];
		(*table)->elements[pos] = insertNode;
	}
	(*table)->size++;
}

判断元素是否在哈希表中

// 取得哈希表中的元素
HashDataType getElemFromHashtable(Hashtable* table, HashDataType data) {
	if (table == NULL)
		return NULL;
	size_t len = table->capacity;
	size_t pos = intHashFunc(table->capacity,  data);
	PHashNode Cur = table->elements[pos];
	while (Cur) {
		if (Cur->data == data)
			return data;
		Cur = Cur->next;
	}
	return NULL;
}

删除哈希表中的某个元素

// 删除哈希表中的某个元素
void deleteElemFromHashtable(Hashtable* table, HashDataType data) {
	if (table == NULL)
		return;
	size_t len = table->capacity;
	size_t pos = intHashFunc(table->capacity,  data);
	PHashNode Cur = table->elements[pos];
	PHashNode preCur = NULL;
	while (Cur) {
		if (Cur->data == data) {
			if (preCur == NULL) {
				table->elements[pos] = Cur->next;
				free(Cur);
				Cur = NULL;
				table->size--;
				return;
			}
			preCur->next = Cur->next;
			free(Cur);
			Cur = NULL;
		}
		preCur = Cur;
		Cur = Cur->next;
	}
}

打印哈希表

// 打印哈希表中的元素
void printHashtable(Hashtable* table) {
	printf("哈希表元素如下:\n");
	if (table == NULL)
		return;
	size_t len = table->capacity;
	for (int i = 0; i < len; ++i) {
		PHashNode Cur = table->elements[i];
		printf("[%d]:", i);
		while (Cur) {
			printf("%d--->", Cur->data);
			Cur = Cur->next;
		}
		printf("NULL\n");
	}
	printf("\n");
}

销毁哈希表

//销毁哈希表
void destroyHashtable(Hashtable** table) {
	size_t len = (*table)->capacity;
	for (int i = 0; i < len; ++i) {
		PHashNode Cur = (*table)->elements[i];
		while (Cur) {
			PHashNode tmp = Cur->next;
			free(Cur);
			Cur = NULL;
			Cur = tmp;
		}
	}
	(*table)->capacity = 0;
	(*table)->size = 0;

	free((*table)->elements);
	(*table)->elements = NULL;

	free(*table);
	*table = NULL;
}

测试用例:

#include "Hashtable.h"

int main() {
	Hashtable* ht = NULL;
	initHashtable(&ht, 5);
	printf("初始容量5\n");
	putElemIntoHashtable(&ht, 1);
	putElemIntoHashtable(&ht, 5);
	putElemIntoHashtable(&ht, 1);
	putElemIntoHashtable(&ht, 3);

	printHashtable(ht);

	putElemIntoHashtable(&ht, 8);
	putElemIntoHashtable(&ht, 23);
	putElemIntoHashtable(&ht, 9);
	putElemIntoHashtable(&ht, 12);

	printf("新4增个元素扩容扩容:size = %d capacity = %d\n", ht->size, ht->capacity);
	printHashtable(ht);

	putElemIntoHashtable(&ht, 13);
	putElemIntoHashtable(&ht, 22);
	putElemIntoHashtable(&ht, 20);

	printHashtable(ht);

	printf("销毁哈希表\n");
	destroyHashtable(&ht);
	printHashtable(ht);
	return 0;
}
1 5 1 3 8 23 9 12 13 22 20

运行结果:


哈希表的应用:

给40亿个不重复的无符号整数,没排过序。
给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 
思路:
1. 先将这40亿个数存入到位图数组中
40亿个int型的数占16G内存,由于一个字节可以表示8个无符号数,而一个整形空间由4个字节组成,所以一个int可以表示32个数,16G / 32 = 512M内存,所以需要512M个整形空间,来存表示这40亿个数(可能会有重复得)。

2. 输入一个数,算出相应的位位置,和位图中的位比较。结果不为0则这个数在这40亿个数中。

代码如下:


#include <stdio.h>
#include <malloc.h>
#define MAX_SIZE 400000 // 可表示 400000 * 8 * 4个数(最多可表示12800000个数)
typedef unsigned int size_t;
typedef struct BitMap {
	size_t capacity;
	size_t bit[MAX_SIZE];
}BitMap;

// 初始化位图,将每一位都初始化为
void initBitMap(BitMap* bmp);

// 将数组中的数用位图表示
void saveNumList(BitMap* bmp, int arr[], int len);

// 用于计算Num在位图中的位置的函数,返回值有两个参数arr[0]表示在位图的哪一块,arr[1]表示在这块位图中的哪一个地方。
int* getPos(BitMap* bmp, int Num);

// 判断一个数是否在位图中
int isInNumList(BitMap* bmp, int Num);

// 设置某一位为1
void set(BitMap* bmp, int block, int pos);

// 设置某一位为0
void reset(BitMap* bmp, int block, int pos);

// 打印位图数组
void printBitMap(BitMap* bmp);

void printArray(int* arr, int len);

int main() {
	size_t arr[10000000]; // 1000万个数,需要39M的内存
	int len = 10000000;
	
	for (int i = 0; i < len; ++i) {
		arr[i] = i;
	}

	BitMap* bmp = (BitMap*)malloc(sizeof(BitMap));
	initBitMap(bmp);
	saveNumList(bmp, arr, len);
	int num = 9999999;
	int ret = isInNumList(bmp, num);
	if (0 != ret)
		printf("%d在数组中\n", num);
	else {
		printf("%d不在数组中\n", num);
	}

	ret = isInNumList(bmp, num + 1);
	if (0 != ret)
		printf("%d在数组中\n", num + 1);
	else {
		printf("%d不在数组中\n", num + 1);
	}
	return 0;
}

// 初始化位图
void initBitMap(BitMap* bmp) {
	bmp->capacity = MAX_SIZE;
	int len = bmp->capacity;
	for (int i = 0; i < len; ++i) {
		bmp->bit[i] = 0;
	}
}

// 将数组中的数用位图表示
void saveNumList(BitMap* bmp, int arr[], int len) {
	for (int i = 0; i < len; ++i) {
		int* pos = getPos(bmp, arr[i]);
		set(bmp, pos[0], pos[1]);
	}
}
	

// 用于计算Num在位图中的位置的函数,返回值有两个参数arr[0]表示在位图的哪一块,arr[1]表示在这块位图中的哪一个地方。
int* getPos(BitMap* bmp, int Num) {
	int arr[2];
	int block = Num / 32;
	int pos = Num % 32;
	arr[0] = block;
	arr[1] = pos;
	return arr;
}

// 判断一个数是否在数组中
int isInNumList(BitMap* bmp, int Num) {
	int* arr = getPos(bmp, Num);
	return (bmp->bit[arr[0]] & (1 << arr[1]));
}

// 设置某一位为1
void set(BitMap* bmp, int block, int pos) {
	bmp->bit[block] = bmp->bit[block] | (1 << pos);
}

// 设置某一位为0
void reset(BitMap* bmp, int block, int pos) {
	bmp->bit[block] &= (~(1 << pos));
}

// 打印位图
void printBitMap(BitMap* bmp) {
	printf("打印位图:\n");
	int len = bmp->capacity;
	for (int i = 0; i < len; ++i) {
		printf("%u ", bmp->bit[i]);
	}
}

void printArray(int* arr, int len) {
	printf("打印数组:\n");
	for (int i = 0; i < len; ++i) {
		printf("%d ", arr[i]);
	}
}

运行结果:


由于VS的栈空间大小默认为1M,所以需要修改默认的值,不然会出现栈溢出。


堆栈保留大小和堆栈提交大小随便改一个。然后应用退出。





版权声明:本文为Bugggget原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Bugggget/article/details/80355394

智能推荐

使用欧几里得算法解决问题——求字符串的最大公因子(力扣第1071题)(JavaScript解法)

1、欧几里得算法的思想 基于辗转相除法的原理,具体做法:用较大数除以较小数,再用出现的余数(第一个余数)去除除数,,再用出现的余数(第二个余数)去除第一个余数,如此仿佛,直到最后一个余数为0 2、算法流程 3、JavaScript实现欧几里得算法 4、使用欧几里得算法解决问题 力扣1071字符串的最大公因子 题目描述: 对于字符串 S 和 T,只有在 S = T + … + T(T ...

spring与redis整合和序列化问题

spring与redis整合 首先用docker下载redis 下载:docker pull redis 运行:docker run -d -p 6379:6379 --name myredis docker.io/redis 连接redis Desktop Manager 然后开始在springboot上开始配置 application.yml: 自动配置好StringRedisTemplate...

CentOS 7配置南大docker镜像

文章目录 CentOS 7配置南大docker镜像 0.帮助页面 1.系统要求 2.卸载旧版本(没有旧版本可跳过) 3.安装方式 4.准备工作 5.可选操作 Stable Test Nightly 6.安装docker引擎 7. (可选)修改配置文件防止与xshell连接冲突 8.启动docker CentOS 7配置南大docker镜像 0.帮助页面 南大docker源:https://mirr...

Qcon演讲纪实:详解如何在实时视频通话中实现AR功能

2018年4月20日-22日,由 infoQ 主办的 Qcon 2018全球软件开发大会在北京如期举行。声网首席 iOS 研发工程师,iOS 端移动应用产品设计和技术架构负责人龚宇华,受邀分享了《基于 ARkit 和 ARcore,在实时视频通话中实现 AR 功能》,在演讲中剖析了 AR 与 VR 差异,ARKit 的工作原理,以及逐步讲解如何基于 ARKit 与声网Agora SDK 创建 AR...

POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4106    Accepted Submission(s): 1947 Probl...

猜你喜欢

使用Breeze.js编写更好的查询

这篇文章是由同行评审Agbonghama柯林斯 。 感谢所有SitePoint的审稿作出SitePoint内容也可以是最好的! 数据量正在迅速发展,他们正在变得越来越复杂,维护。 许多开发人员希望避免由数据问题他们的工作过程中造成的问题和头痛。 一个使我们的工作更轻松的图书馆是Breeze.js 。 在这篇文章中,我们将讨论我们如何能够写出更好的查询与Breeze.js。 但是首先,我们应该知道什...

Netty框架构建Nio编程

~~~ 随手点赞,养成习惯 ~~~ 为什么选择Netty框架 Netty是业界最流行的NIO框架之一,它的健壮性、功能、性能、可定制性和可扩展性在同类框架中都是首屈一指的。 优点: ① API使用简单,开发门槛低 ②功能强大,预置了多种编解码功能,支持多种主流协议 ③ 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展; ④性能高,通过与其他业界主流的NIO框架对比,Nett...

【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description Solution 首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],...

【String-easy】541. Reverse String II 反转的元素,有反转个数和间隔

1. 题目原址 https://leetcode.com/problems/reverse-string-ii/ 2. 题目描述 3. 题目大意 给定一个字符串,和字符串的间隔k, 这个k表示每k个数反转一次,然后再间隔k个元素再反转k个元素。 4. 解题思路 只要按照间隔去反转就可以了。然后间隔k个元素不反转是通过让i每次递增 2*k完成的。 5. AC代码 6. 相似题型 【1】344. Re...

【C语言笔记结构体】

我们都知道C语言中变量的类型决定了变量存储占用的空间。当我们要使用一个变量保存年龄时可以将其声明为int类型,当我们要使用一个变量保存某一科目的考试成绩时可以将其声明为float。 那么,当我们要做一个学生信息管理系统时,需要保存学生的姓名、学号、年龄等信息,该怎么做呢? 如当要保存三个学生的信息时, 方法一是: 方法二是: 显然,方法二跟更清晰,因为它把name、num、age都集成在一个模板,...