数据结构：哈希表

m为哈希表长度,di为增量序列1,2,……m-1,且di=i;

代码实现:

//这是配置好的模板文件
#include 
#include 
using namespace std; 
#define m 16 //哈希表长度
#define NONE -1//初始化哈希表为空
#define p 13 //p<=m,p为质数
//哈希表：除留余数、开地址法（线性探测）
 
typedef struct Hash
{
	int key;//关键字
	//其他项
}Hash ,HashTable[m];
 
//初始化
void init_HashTable(HashTable ht)
{
	for (int i = 0; i < m; i++)
	{
		ht[i].key = NONE;
	}
}
static int H(int key)
{
	return key % p;
}
bool Insert(int k, HashTable ht)
{
	int n1 = H(k);
	for (int i = 0; i < m; i++)
	{
		int n = (n1 + i)% m;
		if (ht[n].key == k)
		{
			return true;//此值已经在哈希表中存在，不允许重复
		}
		else if (ht[n].key == NONE)
		{
			ht[n ].key = k;
			return true;
		}
	}
	//满，失败
	return false;
}
void Show(HashTable ht)
{
	for (int i = 0; i < m; i++)
	{
		printf("%d   ", ht[i].key);
	}
}
int main()
{
	HashTable ht;
	init_HashTable(ht);
	int arr[16] = { 3,5,7,1,2,9,28,25,6,11,10,15,17,23,34,19 };
	for (int i = 0; i < m; i++)
	{
		Insert(arr[i], ht);
	}
 
	Show(ht);
	return 0;
}

二.拉链法

(第二种解决哈希冲突的方法,也更重要)

基本思想:相同散列地址的记录链成一单链表,m个散列地址就设m个单链表,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构.

例如:一组关键字为{19,14,23,1,68,20,84,27,55,11,10,79},散列函数为:Hash(key)=key%13,

就会发现有些元素是同义词,比如14%131,1%131,27%13==1,14,1,27是同义词

上图不好,我们最好能用头插法建立哈希表,头插法速度快，O(1)

最多有m个单链表,编号为0-m-1,用一个数组将m个单链表的表头指针存起来.

代码实现：

//这是配置好的模板文件
#include 
#include 
#include
using namespace std; 
#define m 13//哈希表长度
#define None -1
//哈希表：除留余数法+链地址法
typedef struct DateType
{
	int key;//关键字
	
}DateType;
typedef struct Node
{
	DateType date;
	struct Node* next;
}Node;
typedef struct
{
	Node* next;
}Hashtable[m];
//计算key 的哈希值，哈希函数为H(key)=key%m
static int H(int key)
{
	return key % m;
}
//初始化哈希表
void InitHashtable(Hashtable ht)
{
	assert(ht != NULL);
	if (!ht)
	return;
 
	for (int i = 0; i < m; i++)//将链表制空
	{
		ht[i].next = NULL;
	}
}
//查找关键key,返回节点地址
Node* Search(const Hashtable ht, int key)
{
	int n = H(key);
	for (Node* p = ht[n].next; p != NULL; p = p->next)
	{
		if (p->date.key == key)
			return p;
	}
	return NULL;
}
 
//插入
bool Insert(Hashtable ht,int key)//不存重复的值
{
	int n = H(key);
	if (Search(ht, key))//找到了相同的哈希值，则不允许存储重复数据，算法可用哈希表去重
	{
		return false;
	}
	Node* node = (Node*)malloc(sizeof(Node));
	assert( node!= NULL);
	
	//头插//时间复杂度O(1);尾插O(n)
	node->date.key = key;
	node->next = ht[n].next;
	ht[n].next = node;
	return true;
 
}
void Show(Hashtable ht)
{
	for (int i = 0; i < m; i++)
	{
		printf("哈希值为%d有：", i);
		for (Node* p = ht[i].next; p != NULL; p = p->next)
		{
			printf("%d ", p->date.key);
		}
		printf("\n");
	}
}
int main()
{
	Hashtable ht;
	InitHashtable(ht);
	int arr[16] = { 3,5,7,1,2,9,28,25,6,11,10,15,17,23,34,19 };
	//int arr[16] = { 15,19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79 };
	for (int i = 0; i < m; i++)
	{
		Insert(ht,arr[i] );
	}
	Show(ht);
	return 0;
}

总结

1.链地址法的优点:

• 非同义词不会冲突,无”聚集”现象;
• 链表上节点空间动态申请,更适合于表长不确定的情况.

开地址法非同义词也会产生冲突（比如原来需要存储的地址有元素,我们放入下一个地址,那么下一个地址需要存储的元素本来和这个不是同义词,但是也产生冲突了,这种就叫做聚集现象.）

而链地址法不会有这种问题,因为它的同义词都挂在各自的链表上,非同义词之间没有冲突,没有聚集现象;

2.思考:哈希表查找的时间复杂度?

不是O(1),如果完全没有冲突,是O(1),但是一般都会有冲突;

结论:哈希表的查找的时间复杂度不是O(1),但是逼近O(1);

3.影响时间复杂度的因素有散列函数和解决冲突的方法;

散列函数是不是能够让元素比较均匀的分布在散列表中.

解决冲突的方法是看看解决的冲突解决的是不是比较好,如果解决冲突解决的比较好,那么它的时间复杂度就会比较小.

4.几点结论:

• 散列表技术具有很好的平均性能,优于一些传统的技术;
• 链地址法优于开地址法

• • 是查找效率,一个是链地址它是动态的,表的长度是动态的,比较容易修改,而且如果做插入和删除的操作也比较方便.所以链地址法优于开地址法.

• 除留余数法作散列函数优于其他类型函数

• • 更均匀一些,通常我们的除数取一个质数,取一个小于等于表长的质数更好.这个就会获得一个比较好的散列效果.