如何建设简易网站,有哪些网站使用ftp,长沙官网seo技术厂家,怎么注册公司微信文章目录 前言一、什么是散列表二、什么是哈希函数三、下面简单介绍几种哈希函数四、冲突处理散列冲突的方法开放定址法再散列函数法公共溢出区法链地址法 五、代码实现1.哈希函数2.链表和哈希表的创建3.哈希表初始化3.从哈希表中根据key查找元素4.哈希表插入元素5.元素删除6.哈… 文章目录 前言一、什么是散列表二、什么是哈希函数三、下面简单介绍几种哈希函数四、冲突处理散列冲突的方法开放定址法再散列函数法公共溢出区法链地址法 五、代码实现1.哈希函数2.链表和哈希表的创建3.哈希表初始化3.从哈希表中根据key查找元素4.哈希表插入元素5.元素删除6.哈希表销毁 前言
让我们想一下若在手机通信录中查找一个人那我们应该不会从第 1 个人一直找下去因为这样实在是太慢了。我们其实是这样做的首先看这个人的名字的首字母是什么比如姓张那么我们一定会滑到最后因为“Z”姓的名字都在最后。
还有在查字典时要查找一个单词肯定不会从头翻到尾而是首先通过这个单词的首字母找到对应的那一页再找第 2 个字母、第 3 个字母……这样可以快速跳到那个单词所在的页。
其实这里就用到了散列表的思想。
一、什么是散列表
散列表hash table我们平时叫它哈希表或者Hash 表你肯定经常听到它。
散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数叫做散列函数存放记录的数组叫做散列表。
由定义我们可以知道散列表用的是数组支持下标访问数据的特性所以散列表是数组的一种扩展有数组演化而来。
二、什么是哈希函数
哈希函数就是将键转化为数组索引的过程,这个函数应该易于计算且能够均与分布所有的键。
三、下面简单介绍几种哈希函数
直接寻址法取关键字或关键字的某个线性函数值为散列地址。数字分析法通过对数据的分析发现数据中冲突较少的部分并构造散列地址。例如同学们的学号通常同一届学生的学号其中前面的部分差别不太大所以用后面的部分来构造散列地址。平方取中法当无法确定关键字里哪几位的分布相对比较均匀时可以先求出关键字的平方值然后按需要取平方值的中间几位作为散列地址。这是因为计算平方之后的中间几位和关键字中的每一位都相关所以不同的关键字会以较高的概率产生不同的散列地址。取随机数法使用一个随机函数取关键字的随机值作为散列地址这种方式通常用于关键字长度不同的场合。除留取余法取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要一般取素数或者直接用 n。
以上方法是对数字类型的操作对字符串类型的数据可以选择通过相加或者进位转化成数字后再执行上面的计算方法。
四、冲突
冲突就是两个不同的关键字但是通过散列函数得出来的地址是一样的。 key1 ≠ key2但是fkey1 fkey2
同义词 此时的key1 和key2就被称为这个散列函数的同义词
那可不行啊一件单人间怎么可以住两个人呢
别担心这个问题自然已经被神通广大的大佬们解决了。
处理散列冲突的方法
开放定址法
开发定址法就是一旦发生了冲突就去寻找下一个空的散列地址只需要散列表足够大空的散列地址总能找到并将记录存入
例子 19 01 23 14 55 68 11 86 37 要存储在表长11的数组中其中Hkeykey MOD 11
线性探测法 公式
f1(key) (f(key)d1) MOD m(di1,2,3,....,m-1)我们取di等于1
index012345678910key55114198623冲突2368冲突68冲突6811冲突11冲突11冲突11冲突11冲突1137冲突37冲突37最终存储结果55123146811371986
二次探测法 增加平方运算的目的是为了不让关键字都聚再某一块区域我们称这种方法为二次探测法 公式
f1(key) (f(key)d1) MOD m(di1^2,-1^2,2^2,-2^2,...,q^2,-q^2,qm/2)index012345678910key55114198623冲突f(23)1f(68)-1冲突68冲突f(68)1冲突f(68)411冲突f(11)1冲突f(11)-1最终存储结果551231468198611
随机探测法 在冲突时对于位移量di采用随机函数计算得到我们称之为随机探测法 公式
f1(key) (f(key)d1) MOD m(di是一个随机数列)具体方法和上面一样 就不多赘述了
再散列函数法
对于我们的散列表来说我们事先需要准备多个散列函数
f(key)RHi(key) (i1,2...,3)这里的RHi就是不同的散列函数每当发生冲突时就换一个散列函数进行计算总有一个函数可以将冲突解决
公共溢出区法
在原先基础表的基础上再添加一个溢出表 当发生冲突时就将该数据放到溢出表中 在查找时对给定值通过散列函数计算出散列地址后先与基本表的相应位置进行对比如果相等就查找成功如果不相等则到溢出表进行顺序查找 链地址法
就时用链表将发生冲突的数据链起来在查找时只需要遍历链表即可 如下图
此方法也是我们最长用处理哈希冲突的方法
五、代码实现
1.哈希函数
//哈希函数
int Hash(int key, int TableSize)
{return key % TableSize;
}2.链表和哈希表的创建
#define DEFAULT_SIZE 16
typedef int type;
//结点
typedef struct ListNode
{struct ListNode* next;int key; //线索type* data; //数据
}ListNode;
//提高可读性
typedef ListNode* List;
typedef ListNode* Element;
//哈希表
typedef struct HashTable
{int TableSize;List* Thelists;
}HashTable;3.哈希表初始化
HashTable* InitHash(int TableSize)
{int i 0;HashTable* htable NULL;if (TableSize 0){TableSize DEFAULT_SIZE;}htable (HashTable*)malloc(sizeof(HashTable));if (htable NULL){printf(初始化失败\n);return NULL;}//为桶分配内存空间其为一个指针数组htable-Thelists (List*)malloc(sizeof(List) * TableSize);if (htable-Thelists NULL){printf(初始化失败\n);free(htable);return NULL;}//为Hash桶对应的指针数组初始化链表结点for (i 0; i TableSize; i){htable-Thelists[i] (ListNode*)malloc(sizeof(ListNode));if (htable-Thelists[i] NULL){printf(初始化失败\n);free(htable-Thelists);free(htable);return NULL;}}
}3.从哈希表中根据key查找元素
Element Find(HashTable* HashTable, int key)
{int i 0;List L NULL;Element e NULL;i Hash(key, HashTable-TableSize);L HashTable-Thelists[i];e L-next;while (e ! NULL e-key ! key)e e-next;return e;
}4.哈希表插入元素
void Insert(HashTable* HashTable, int key, type* value)
{Element e NULL, temp NULL;List L NULL;e Find(HashTable, key);if (e NULL){temp (Element)malloc(sizeof(ListNode));if (temp NULL){printf(malloc error\n);return;}L HashTable-Thelists[Hash(key, HashTable-TableSize)];temp-data value;temp-key key;L-next temp;}elseprintf(the key already exist\n);
}5.元素删除
void Delete(HashTable* HashTable, int key)
{Element e NULL, last NULL;List L NULL;int i Hash(key, HashTable-TableSize);L HashTable-Thelists[i];last L;e L-next;while (e ! NULL e-key ! key){last e;e e-next;}if (e){last-next e-next;free(e); }else{printf(该元素不存在\n);}
}6.哈希表销毁
void Destory(HashTable* HashTable)
{int i 0;List L NULL;Element cur NULL, next NULL;for (i 0; i HashTable-TableSize; i){L HashTable-Thelists[i];cur L-next;while (cur-next ! NULL){next cur-next;free(cur);cur next;}}
