欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

散列表是什么,你真的懂了吗?

程序员文章站 2022-06-03 09:14:50
...

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。
实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：
· 计算哈希函数所需时间
· 关键字的长度
· 哈希表的大小
· 关键字的分布情况
· 记录的查找频率
1.直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。
2. 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
3. 平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，如下图所示
散列表是什么,你真的懂了吗?
4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
5. 随机数法：选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。
6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

对于散列表的性能分析有以下判断：
首先有个指标即平均查找长度ASL用来度量散列表查找效率：成功查找、不成功查找。
而且我们要对关键词的查找的同时，这还要取决于产生冲突的多少。
而影响产生冲突的多少的因素有:
(1)散列函数是够均匀:你构造的散列表不均匀，那么冲突就会变多，然后性能就会变差
(2)处理冲突的方法
(3)散列表的装填因子α

因此我们需要分析不同的冲突处理方法和装填因子对效率的影响。
1.线性探测法的查找性能
有证明可得，线性探测法的期望探测发满足下列公式：
散列表是什么,你真的懂了吗?散列表是什么,你真的懂了吗?
线性探测法的实现代码如下:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef enum
{
    Legitimate, // 合法
    Empty,      // 空
    Deleted     // 已经删除
} EntryType;
#define MAXN 100000
typedef struct HashTbl Cell;
struct HashTbl
{
	int data;
	int lnfo;//单元状态
};
typedef struct TblNode *HashTable;
struct TblNode
{
	int TableSize;//哈希表的大小
	Cell *Cells;//存放数据的数组
};
HashTable CreateHashTable(int Tablesize);
int NextPrime(int N);
void Insert(HashTable H,int x);
int Find(HashTable H,int key);
void PrintHashTable(HashTable H);
int main()
{
	HashTable  H;
	int N;
	printf("请输入给定哈希表的大小:\n");
	scanf("%d",&N);
	H=CreateHashTable(N);
	int x;
	for(int i=0;i<5;i++)
	{
		printf("请输入元素:\n");
		scanf("%d",&x);
		Insert(H,x);//往哈希表中放入元素
	}
	PrintHashTable(H);//打印哈希表中的元素
	return 0;
}
HashTable CreateHashTable(int Tablesize)
{
	HashTable H;
	H=(HashTable)malloc(sizeof(struct TblNode));
	H->TableSize=NextPrime(Tablesize);
	H->Cells=(Cell *)malloc(sizeof(Cell)*H->TableSize);
	for(int i=0;i<H->TableSize;i++)
		H->Cells[i].lnfo=Empty;
	return H;
}
int NextPrime(int N)//返回素数
{
	int p=(N%2)?N+2:N+1;
	while(p<=MAXN)
	{
		int i;
		for((int)sqrt(p);i>2;i--)
		{
			if(p%i)
				break;
		}
		if(i==2)
			break;
		else
			p+=2;

	}
	return p;
}
void Insert(HashTable H,int x)
{
	int pos=Find(H,x);
	if(H->Cells[pos].lnfo!=Legitimate)
	{
		H->Cells[pos].lnfo=Legitimate;
		H->Cells[pos].data=x;
		printf("插入成功\n");
	}
	else
	{
		printf("键值已存在");
	}
}
int Find(HashTable H,int key)
{
	int CurPos=key%H->TableSize;
	int CollisionNum=0;
	while (H->Cells[CurPos].lnfo != Empty&&
		H->Cells[CurPos].data != key)
	{
		CurPos += 2 * (++CollisionNum) - 1;
		//如果新的定位越过数组，那么可以通过减去TableSize把它拉回数组范围内
		if (CurPos >= H->TableSize)
			CurPos -= H->TableSize;
	}
	return CurPos;
}
void PrintHashTable(HashTable H)
{
    for (int i = 0; i < H->TableSize; i++)
    {
		if (H->Cells[i].lnfo == Legitimate)
			printf("%3d",H->Cells[i].data);
    }
   printf("\n");
}

2.平方探测法和双散列探测法的查找性能
有证明可得，平方探测法和双散列探测法的查找性能满足下列公式
散列表是什么,你真的懂了吗?
散列表是什么,你真的懂了吗?
我们可以发现
理论值和具体值会存在一些差异，理论值是根据一般情况下的散列表，而具体值根据具体的散列表，可能这个表的元素分布比较不一样。

然后我们可以得出相应的图，看一下装填因子和ASL的关系
散列表是什么,你真的懂了吗?
合理的装填因子应该不超过0.85

代码实现如下:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef enum
{
    Legitimate, // 合法
    Empty,      // 空
    Deleted     // 已经删除
} EntryType;
#define MAXN 100000
typedef struct HashTbl Cell;
struct HashTbl
{
	int data;
	int lnfo;//单元状态
};
typedef struct TblNode *HashTable;
struct TblNode
{
	int TableSize;//哈希表的大小
	Cell *Cells;//存放数据的数组
};
HashTable CreateHashTable(int Tablesize);
int NextPrime(int N);
void Insert(HashTable H,int x);
int Find(HashTable H,int key);
void PrintHashTable(HashTable H);
int main()
{
	HashTable  H;
	int N;
	printf("请输入给定哈希表的大小:\n");
	scanf("%d",&N);
	H=CreateHashTable(N);
	int x;
	for(int i=0;i<5;i++)
	{
		printf("请输入插入的元素:\n");
		scanf("%d",&x);
		Insert(H,x);//往哈希表中放入元素
	}
	PrintHashTable(H);//打印哈希表中的元素
	return 0;
}
HashTable CreateHashTable(int Tablesize)
{
	HashTable H;
	H=(HashTable)malloc(sizeof(struct TblNode));
	H->TableSize=NextPrime(Tablesize);
	H->Cells=(Cell *)malloc(sizeof(Cell)*H->TableSize);
	for(int i=0;i<H->TableSize;i++)
		H->Cells[i].lnfo=Empty;
	return H;
}
int NextPrime(int N)//返回素数
{
	int p=(N%2)?N+2:N+1;
	while(p<=MAXN)
	{
		int i;
		for((int)sqrt(p);i>2;i--)
		{
			if(p%i)
				break;
		}
		if(i==2)
			break;
		else
			p+=2;

	}
	return p;
}
void Insert(HashTable H,int x)
{
	int pos=Find(H,x);
	if(H->Cells[pos].lnfo!=Legitimate)
	{
		H->Cells[pos].lnfo=Legitimate;
		H->Cells[pos].data=x;
		printf("插入成功\n");
	}
	else
	{
		printf("键值已存在");
	}
}
int Find(HashTable H,int key)
{
	int Currentpos, NewPos;
    int CNum = 0; // 记录冲突次数
    // NewPos = Currentpos = Hash(Key, H->TableSize); // 初始散列的位置
    int p = H->TableSize;         
    NewPos = Currentpos = key % p; // 除留余数法

    // 为空的话就是找不到
	while (H->Cells[NewPos].lnfo != Empty && H->Cells[NewPos].data != key)
    {
        // 奇数次冲突 加i的平方
        if (++CNum % 2)
        {
            // CNum相当于i的映射
            // NewPos是增加后的位置
            NewPos = Currentpos + ((CNum + 1) / 2) * ((CNum + 1) / 2);
            // 如果加超了
            // 调增成合法的地址
            if (NewPos >= H->TableSize)
                NewPos = NewPos % H->TableSize;
        }
        else
        {
            NewPos = Currentpos - (CNum / 2) * (CNum / 2);
            while (NewPos < 0)
                NewPos += H->TableSize;
        }
    }
	return NewPos;
}
void PrintHashTable(HashTable H)
{
    for (int i = 0; i < H->TableSize; i++)
    {
		if (H->Cells[i].lnfo == Legitimate)
			printf("%3d",H->Cells[i].data);
    }
   printf("\n");
}

3.分离链接法的查找性能
所有地址链表的平均查找长度定义成装填因子α
α可能超过1
有证明可得，期望探测次数为
散列表是什么,你真的懂了吗?
散列表是什么,你真的懂了吗?
分离链表的实现过程为:
利用除数留余法来获得相关的数组下标，如果产生冲突，则放到这个数组指向的链表之后。
散列表是什么,你真的懂了吗?
分离链表的实现代码如下；

#include<stdio.h>
#include<stdlib.h>
#define MIN 2
typedef struct ListNode *position;
typedef position List;
struct ListNode
{
	int element;
	position next;
};

struct HashTbl
{
	int TableSize;
	List *ThisList;
};
typedef struct HashTbl *HashTable;

HashTable CreateHashTable(int N);
int NextPrime(int N);
int IsPrime(int N);
void Insert(HashTable H,int x);
position find(HashTable H,int x);

int main()
{
	HashTable H;
	int N,i,x;
	printf("请输入你要构造的散列表的大小:\n");
	scanf("%d",&N);
	H=CreateHashTable(N);
	for(i=0;i<N;i++)
	{
		printf("请输入要插入的元素:\n");
		scanf("%d",&x);
		Insert(H,x);
	}
	position p;
	printf("请输入你要查找的元素:\n");
	scanf("%d",&x);
	p=find(H,x);
	if(p)
	{
		printf("查找成功:\n");
		printf("%d",p->element);
	}
	else
	{
		printf("查找失败!");
	}
	return 0;

}
HashTable CreateHashTable(int N)
{
	HashTable H;
	int i;
	if(N<MIN)
	{
		printf("散列表太小！,无法构成散列表");
		return NULL;
	}
	H=(HashTable)malloc(sizeof(struct HashTbl));
	if(H==NULL)
	{
		printf("空间溢出！");
		return NULL;
	}
	H->TableSize=NextPrime(N);//得到大小为素数的散列表
	H->ThisList=(List *)malloc(sizeof(List)*H->TableSize);

	if(H->ThisList==NULL)
	{	
		printf("空间溢出");
	return NULL;
	}
	for(i=0;i<H->TableSize;i++)
	{
		H->ThisList[i]=(List)malloc(sizeof(struct ListNode));
		if(H->ThisList[i]==NULL)
		{
			printf("空间溢出");
			return NULL;
		}
		else
			H->ThisList[i]->next=NULL;
	}
	return H;
}
int NextPrime(int N)//判断是够是素数
{
	while(1)
	{
		if(IsPrime(N))
			return N;
		else
			N++;
	}
}
int IsPrime(int N)
{
	int i;
	for(i=2;i*i<=N;i++)
	{
		if(N%i==0)
			return 0;
	}
	return 1;
}
void Insert(HashTable H,int x)
{
	position pos,Newcell;
	List L;
	pos=find(H,x);
	if(pos==NULL)//判断条件
	{
		Newcell=(List)malloc(sizeof(struct ListNode));
		if(Newcell==NULL)
		{
			printf("溢出空间");
			return ;
		}
		else
		{
			L=H->ThisList[x%H->TableSize];//找到相应的位置并放入那个链表之后
			Newcell->next=L->next;
			Newcell->element=x;
			L->next=Newcell;
		}
	}
}
position find(HashTable H,int x)/*查找函数,作用是查找位置是否为空，为空返回NULL,方便我们进行插入结点。
								不为空就是我们要查找的那个数*/
{
	position p;
	List L;
	L=H->ThisList[x%H->TableSize];
	p=L->next;
	while(p)
	{
		if(p->element==x)
			return p;
		p=p->next;
	}
	return NULL;
}

散列表不像搜索树那样，在散列表中查找，我们只需要相应的对应，就可以实现查找效率为常数级别的。
散列表是什么,你真的懂了吗?
而且对于字符串这样比较难比较的东西，散列表中就可以定义关键字来进行相应的查找。
散列表是什么,你真的懂了吗?分离链接法的相应代码如下:

4.开放地址法
散列表是什么,你真的懂了吗?
开放地址法的代码如下:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef enum
{
    Legitimate, // 合法
    Empty,      // 空
    Deleted     // 已经删除
} EntryType;
#define MAXN 100000
typedef struct HashTbl Cell;
struct HashTbl
{
	int data;
	int lnfo;//单元状态
};
typedef struct TblNode *HashTable;
struct TblNode
{
	int TableSize;//哈希表的大小
	Cell *Cells;//存放数据的数组
};
HashTable CreateHashTable(int Tablesize);
int NextPrime(int N);
void Insert(HashTable H,int x);
int Find(HashTable H,int key);
void PrintHashTable(HashTable H);
int main()
{
	HashTable  H;
	int N;
	printf("请输入给定哈希表的大小:\n");
	scanf("%d",&N);
	H=CreateHashTable(N);
	int x;
	for(int i=0;i<5;i++)
	{
		printf("请输入插入的元素:\n");
		scanf("%d",&x);
		Insert(H,x);//往哈希表中放入元素
	}
	PrintHashTable(H);//打印哈希表中的元素
	return 0;
}
HashTable CreateHashTable(int Tablesize)
{
	HashTable H;
	H=(HashTable)malloc(sizeof(struct TblNode));
	H->TableSize=NextPrime(Tablesize);
	H->Cells=(Cell *)malloc(sizeof(Cell)*H->TableSize);
	for(int i=0;i<H->TableSize;i++)
		H->Cells[i].lnfo=Empty;
	return H;
}
int NextPrime(int N)//返回素数
{
	int p=(N%2)?N+2:N+1;
	while(p<=MAXN)
	{
		int i;
		for((int)sqrt(p);i>2;i--)
		{
			if(p%i)
				break;
		}
		if(i==2)
			break;
		else
			p+=2;

	}
	return p;
}
void Insert(HashTable H,int x)
{
	int pos=Find(H,x);
	if(H->Cells[pos].lnfo!=Legitimate)
	{
		H->Cells[pos].lnfo=Legitimate;
		H->Cells[pos].data=x;
		printf("插入成功\n");
	}
	else
	{
		printf("键值已存在");
	}
}
int Find(HashTable H,int key)
{
	int Currentpos, NewPos;
    int CNum = 0; // 记录冲突次数
    // NewPos = Currentpos = Hash(Key, H->TableSize); // 初始散列的位置
    int p = H->TableSize;          
    NewPos = Currentpos = key % p; // 除留余数法

    // 为空的话就是找不到
 while (H->Cells[NewPos].lnfo != Empty && H->Cells[NewPos].data != key)
    {
        NewPos = (Currentpos + (++CNum)) % H->TableSize;
    }
	return NewPos;
}
void PrintHashTable(HashTable H)
{
    for (int i = 0; i < H->TableSize; i++)
    {
		if (H->Cells[i].lnfo == Legitimate)
			printf("%3d",H->Cells[i].data);
    }
   printf("\n");
}

一般建议不使用开放地址法。
而对于分离链接法的效率来说。散列表是什么,你真的懂了吗?

希望大家能够好好了解相关的思想和代码实现，成功get散列表。
一定要多思考，尝试自己手动敲写代码，这样才能获得收获！

相关标签： 数据结构 算法

上一篇： MySQL(基础篇)之索引

下一篇： PHP 5.3 new feature

推荐阅读