【数据结构】哈希表

散列表（也叫哈希表），是根据关键码值而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
哈希表的核心是合适的hash函数，数据范围，解决冲突的办法

这里通过数字分析法设计哈希函数， 链地址法解决从冲突。

冲突

对于不同的关键字可能得到相同的散列地址的现象称为冲突
比如哈希函数为Hash(key)=key%HashSize时就有可能出现冲突的情况。

假设哈希表的大小是4个bit
1001和10001所对应的哈希地址是相同的
解决冲突的办法是建立一个链表存储这两个数据
1
2
3

数字分析法

struct student
{
	int birthday;
	char name[10];
}
1
2
3
4
5

对于一个班的学生，出生年月日的前几位的数据相差不大，如果用这几位数据做哈希表的地址那么出现冲突的概率很大，但是表示月份和日期的数字相差较大，用这几位数据做哈希表的地址出现冲突的概率就不是很大。或者将将年月日都作为哈希地址（年是一级地址，月是二级地址，日是三级地址）

哈希结构

这里没有用学生信息的那个例子，用的是数据的存储和查找，HashTable中的三级指针是因为哈希表地址按照数据的个位、十位、百位分成了三层。哈希表中存的是节点的指针。

struct Node
{
	int data;
	struct Node* next;	
};
Node* CreateNode(int data);
struct HashTable
{
	struct Node*** pArray[10];
	void initHash(HashTable**p);
	void insertData(HashTable* pTable,int data);
	Node* findDada(HashTable* p, int data);
};
1
2
3
4
5
6
7
8
9
10
11
12
13

初始化哈希表

void HashTable::initHash(HashTable** p)
{
	*p = new HashTable;
	
	for (int i = 0; i < 10; i++)
	{
		(*p)->pArray[i] = new Node * *[10];
		for (int j = 0; j < 10; j++)
		{
			(*p)->pArray[i][j] = new Node * [10];
			memset((*p)->pArray[i][j], 0, 10 * sizeof(Node*));
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

插入

void HashTable::insertData(HashTable* pTable, int data)
{
	//创建节点
	Node* node = CreateNode(data);
	//找位置
	int bai = data / 100 % 10;
	int shi = data / 10 % 10;
	int ge = data % 10;
	//插入
	Node* temp = NULL;
	if (pTable->pArray[bai][shi][ge] == NULL)
		pTable->pArray[bai][shi][ge] = node;
	else//冲突，链表尾插法解绝
	{
		temp = pTable->pArray[bai][shi][ge];
		while (temp->next)
			temp = temp->next;
		temp->next = node;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

查找

Node* HashTable::findDada(HashTable* p, int data)
{
	//数据按层拆分
	int bai = data / 100 % 10;
	int shi = data / 10 % 10;
	int ge = data % 10;
	//链表查找
	Node*temp = p->pArray[bai][shi][ge];
	while (temp)
	{
		if (data == temp->data)
			return temp;
		temp = temp->next;
	}
	return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16