哈希表(又称散列表)的基础知识【定义、映射和构建】_s4 内表定义 哈希

哈希表

定义

哈希表(Hash table，也叫散列表)，是根据关键字值(key)直接进行访问的数据结构，它通过把关键字值映射到表中一个位置(数组下标)来直接访问，以加快查找关键字值的速度。这个映射函数叫做哈希(散列)函数，存放记录的数组叫做哈希(散列)表。

如果给定一个表M，存在某个函数f(key)，对任意的关键字值key，代入函数后能得到包含该关键字的表中地址，称表M为哈希表，函数f(key)为哈希函数。
如图所示：

不同的哈希运用：
①最简单的哈希-字符哈希

int main(){
	int char_map[128] = {0};
	string str = "abcdasdfolkljosiifyg";
	for(int i = 0; i < str.length(); i++){
		char_map[str[i]]++;
	} 
	for(int i = 0; i < 128; i++){
		if(char_map[i] > 0){
			printf("[%c][%d] : %d", i, i, char_map[i]);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

②哈希表排序整数

int main(){
	int random[10] = {999, 1, 444, 65, 89, 601, 654, 9, 7, 7};
	int hash_map[1000] = {0};
	for(int i = 0; i < 10; i++){
		hash_map[random[i]]++;
	}
	for(int i = 0; i < 1000; i++){
		for(int j = 0; j < hash_map[i]; j++){
			printf("%d\n", i);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

问题提出

1.对于负数或非常大的整数，如何哈希(映射)？
比如：-30，856245674，…
2.对于字符串，又如何哈希？
比如：afasdfkjo 、XYF、…
3.对于一些无法直接映射的数据类型，如浮点数、数组、对像等，如何进行哈希？
比如：1.5484、[1, 5, 6]、…

解决方案

利用哈希函数，将关键字值(key)(大整数、字符串、浮点数等)转换为整数再对表长取余，从而关键字值被转换为哈希表的表长范围内的整数。
代码示例如下：

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

int int_func(int key, int table_len){
	return key % table_len;
}
int string_func(string key, int table_len){
	int sum = 0;
	for(int i = 0; i < key.length(); i++){
		sum += key[i];
	}
	return sum % table_len;
}

int main(){
	const int TABLE_LEN = 10;
	int hash_map[TABLE_LEN] = {0};
	hash_map[int_func(9999995, TABLE_LEN)]++;
	hash_map[int_func(5, TABLE_LEN)]++;
	hash_map[string_func("abc", TABLE_LEN)]++;
	hash_map[string_func("bac", TABLE_LEN)]++;
	for(int i = 0; i < TABLE_LEN; i++){
		printf("hash_map[%d] = %d\n", i, hash_map[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

利用拉链法，解决不同值之间的冲突问题；

自主选择哈希表的长度m，可定义为一个长度为m的指针数组，依照上述的方法计算出哈希函数的value值，将其以头插法插入到相对应的value值的单链表中。

如果需要 查询 value：
若元素value的哈希函数值为hash_key，遍历时以t[hash_key]为头指针的单链表，查找该链表的各节点值是否为value。

如下图所示：

实现代码如下：

struct ListNode{
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL) {}
};
int hash_func(int key, int table_len){
	return key % table_len;
}
void insert(ListNode* hash_table[], ListNode* node, int table_len){
	int hash_key = hash_func(node->val, table_len);
	node->next = hash_table[hash_key];
	hash_table[hash_key] = node;
}
bool search(ListNode* hash_table[], int value, int table_len){
	int hash_key = hash_func(value, table_len);
	ListNode* head = hash_table[hash_key];
	while(head){
		if(head->val == value){
			return true;
		}
		head = head->next;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

致谢

本章知识点和思路由小象学院相关视频提供，由本人学习并梳理得出，希望自己加深记忆的同时，也能给大家提供更多有关于一些算法的知识点。
你的点赞、评论、收藏就是对我最大的支持与鼓励，谢谢！