文章目录
查找（4）—— 散列（Hash）字典
介绍
本文为查找第四部分，主要是整理了本人上课时讲的内容，并给出了代码实现
散列函数的构造方法
直接地址法
H ( k ) = a k + b H(k) = ak + b H(k)=ak+b
数字分析法
基本思想：当关键字值的位数大于散列地址码的位数时，对关键值各位数字进行分析，从中取出与散列地址位数相同的位
适用范围：适用于当所有关键字值都已知的情况下。但在许多情况中，这是不可能实现的，所以这时候便不合适
平方取中法
适用范围：当关键字值中的每一位取值都不够分散，或者相对比较分散的位数小于散列地址所需要的位数的情况。
叠加法
基本思想：将关键字值分割成位数相同的几个部分（最后一个部分的位数如不够，不足位左边可以空缺），然后把这几个部分的叠加和（舍去进位）作为散列地址。
适用范围：在位数很多且位值分布比较均匀时可以采用
移位叠加法
舍去进位，179作为k的散列地址
折叠叠加法
基数转换法
除留余数法
H ( k ) = k m o d p H(k) = k\ mod\ p H(k)=k mod p
其中，若m为地址范围大小（或称表长），则p可为小于等于m的素数。一般为最接近m的素数
随机数法
H ( k ) = r a n d o m ( k ) H(k) = random(k) H(k)=random(k)
一些好的哈希函数**
针对字符串好的哈希函数
unsigned int hash(char *str)
{
unsigned int h = 0;
while (*str != '\0')
h = (h << 5) + *str++;
return h % TableSize;
}
unsigned int BKDRHash(const char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF); // 处理负数情况
}
冲突的处理方法
开放地址法
D i = ( H ( k ) + d i ) m o d m D_i = (H(k) + d_i) \ mod\ m Di=(H(k)+di) mod m
线性探测
d i = 1 , 2 , 3 , 4 , 5 , 6 , d_i = 1,2,3,4,5,6, di=1,2,3,4,5,6,
二次探测
d i = 1 2 , − 1 2 , 2 2 , − 2 2 , d_i =1^2,-1^2,2^2,-2^2, di=12,−12,22,−22,
伪随机
di 为伪随机序列
特点
负载因子——衡量散列表的饱满程度
α
=
n
m
m
a
x
\alpha = \frac{n}{m_{max}}
α=mmaxn
n 代表散列表中实际存入的元素数，m 代表散列表中基本区的最大容量
α \alpha α 越大，散列表越满，一般来说小于1。
- “线性探测法”容易产生元素“聚集”的问题。
- “二次探测法”可以较好地避免元素“聚集”的问题，但不能探测到表中的所有元素（至少可以探测到表中的一半元素）。
- 只能对表项进行逻辑删除（如做删除标记），而不能进行物理删除。使得表面上看起来很满的散列表实际上存在许多未用位置。
再散列法
D i = H i ( k ) D_i = H_i(k) Di=Hi(k)
D i D_i Di 为散列地址， H i ( k ) H_i(k) Hi(k) 是不同的散列函数
链接地址法
代码实现
struct Node
{
int data;
struct Node *next;
} *Hashtable[tableSize];
// 查找并创建哈希表
struct Node *lookUp(int key, int create)
{
unsigned int h = hash(key);
struct Node *tmp = Hashtable[h];
while (tmp != NULL)
{
if (tmp->data == key)
{
return tmp;
}
tmp = tmp->next;
}
if (create)
{
tmp = (struct Node *)malloc(sizeof(struct Node));
tmp->data = key;
tmp->next = Hashtable[h];
Hashtable[h] = tmp;
}
return tmp;
}
说明
- 当散列出现冲突时，新插入的元素放在链表的头部，这样算法简洁，效率更高；
- 由于链表查找效率低，可使用一棵二叉查找树或另一个散列表来代替链表解决冲突。
特点
- 处理冲突简单，不会产生元素“聚集”现象，平均查找长度较小 。
- 适合建立散列表之前难以确定表长的情况 。
- 建立的散列表中进行删除操作简单 。
- 由于指针域需占用额外空间，当规模较小时，不如“开放地址法”节省空间。
散列表的典型应用
符号表（symbol），用于在数据值和动态符号（如变量名，关键码）集的成员间建立一种关联。符号表是编译系统中主要的数据结构，用于管理用户程序中各个变量的信息，通常编程系统使用散列表来组织符号表。
浏览器中维持最近使用的**页面踪迹、缓存最近使用过的域名及它们的IP地址。**
标签：tmp,07,int,BUAA,列表,地址,查找,哈希,散列 From： https://blog.csdn.net/cjh_cr7/article/details/139213132