1.散列表的概念:
根据要存储的数据记录的关键字值计算出应该存储的位置
基本思想:记录的存储位置与关键字之间存在对应关系
Loc(i)=H(keyi)-----等号右边就称之为hash函数.等号左边就是对应的存储位置;
2.哈希表的优缺点
这个就是散列表的特点:查找效率高,空间利用率低;（以空间换时间）
3.使用散列表要解决好两个问题:
(1) 构造好的散列函数:所选函数尽可能简单,以便提高转化速度;
所选函数对关键码计算出的地址,应在散列地址中均匀分布,以减少空间浪费;
(2) 指定一个好的解决冲突的方案:查找时,如果从散列函数计算出的地址中查不到关键码,则应当依据解决冲突的规则,有规律地查询其他相关单元.
那么构造散列函数需要考虑的因素有哪些呢?(了解)
1.执行速度(即计算散列函数所需的时间); 2,关键字的长度; 3,散列表的大小
4,关键字的分布情况; 5查找频率;
4.构造散列函数的6个方法
1.直接地址法 2数字分析法 3平方取中法 4折叠法 5除留余数法 6随机数法
1. 直接定址法:
H(key)=a*key+b (a,b为常数),
例子:{100,300,500,700,800,900},哈希函数为Hash(key)=key/100,其实就是a=1/100,b=0;
那么以此函数建立的哈希表为:
优点:以关键码Key的某个线性函数值为散列地址,不会产生冲突;
为什么不会产生冲突?
y=ax+b 线性函数,x唯一,那么y唯一
缺点:要占用连续的地址空间,空间效率低.
直接定址法我们也比较常用,因为简单,同时优点是不会产生冲突,缺点是要占用连续的地址空间,空间效率低.
2.除留余数法
用关键字除以p得到的余数作为关键字的存储位置.
Hash(key)=key%p(p是一个整数)
那么关键是怎么取到合适的除数p?
技巧:设表长为m,取p<=m且为质数
例如{15,23,27,38,53,61,70},散列函数Hash(key)=key%7,那么哈希表为:
查找的时候同样用这个哈希函数,比如我们要查找70.用10除以7余数为0,直接去0号位置查找.
以上就是我们常用的散列表的构造方法:直接定址法和除留余数法.
5.处理冲突的方法
处理冲突的方法:
1.开放地址法(开地址法) 2.链地址法(拉链法) 3.再散列法(双散列函数法)
4.建立一个公共溢出区;
开地址法:
基本思想:有冲突时就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将元素存入.(开放地址法的常用方法:线性探测法,二次探测法,伪随机探测法)
Hi=(Hash(key)+di)%m (1<=i<m)
m为哈希表长度,di为增量序列1,2,……m-1,且di=i;
代码实现:
//这是配置好的模板文件
#include <iostream>
#include <string>
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 <iostream>
#include <string.h>
#include<assert.h>
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.几点结论:
- 散列表技术具有很好的平均性能,优于一些传统的技术;
- 链地址法优于开地址法
- 是查找效率,一个是链地址它是动态的,表的长度是动态的,比较容易修改,而且如果做插入和删除的操作也比较方便.所以链地址法优于开地址法.
- 除留余数法作散列函数优于其他类型函数
- 更均匀一些,通常我们的除数取一个质数,取一个小于等于表长的质数更好.这个就会获得一个比较好的散列效果.
