hash 和 hash桶

hash

1. hash

1.1 什么是hash？

Hash（哈希），又称“散列”。

1. hash 就是通过一种hash函数(如 value = key % 3)进行计算方便查找的一种方法
2. 通过我们说进行hash计算是hash值的概念: 把任意长度的输入通过散列算法变换成固定长度的输出
   这个是为了解决文件是否相同的一种方法。

1.2 为什么有hash？

通常我们使用数组或者链表来存储元素，查找通过对比进行，但是当数量大时比较次数太多，复杂度太大。
而通过哈希计算，可以大大减少比较次数。

1.3 举例子

比如现在有5个元素{1,15,2,55,94,}
现在要查找94是不是在其中，如果数组或者链表就是挨个进行比较。
hash方法：
首先确定一个hash函数，f(x) = x % 5;

f(1) = 1%5 = 1
f(2) = 2%5 = 2
f(15) = 15%5 = 0
f(55) = 55%5 = 0
f(94) = 94%5 = 4
1
2
3
4
5

现在找95是不是在其中，只有通过hash函数计算一下hash值然后在hash表中查找即可：
hash表

key <--> value
1 <--> 1
2 <--> 2
0 <--> 15
0 <--> 55
4 <--> 94
1
2
3
4
5
6

1.4 hash函数

hash函数：记录的关键字和存储位置建立映射关系
对应关系f（）称为散列函数，或者哈希函数
如举例子中的 f(x) = x % 5;
哈希函数是一种映射关系

1.5 hash表

通过hash计算并存储对应关系的表叫做hash表。
如上面例子中的hash表

key <--> value
1 <--> 1
2 <--> 2
0 <--> 15
0 <--> 55
4 <--> 94
1
2
3
4
5
6

1.6 哈希函数有6种实现方式

1. 直接定址法：取关键字的线性函数值作为哈希地址。例如f(key)=3*key+1
2. 数字分析法：取关键字中若干位作为哈希地址。例如手机号中间四位为归属地
3. 平方取中法：取关键字平方后的中间几位作为哈希地址。例如1234 平方后为1522756，取其中的三位就是227。
4. 折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为哈希地址。
   例如：9876543210 分为987 654 321 0 求和为1962 再取三位得到散列地址：962。
5. 除留余数法(最常用)：f(key)=key mode p (p<=m) m 为不大于哈希表的数。
   如f(x) = x % 5
6. 随机数法：取随机数作为散列地址。

1.7 hash冲突

就是通过hash函数计算的时候，不同的key值，相同的value。
如例子中通过hash函数：f(x) = x % 5计算15 55时，value都为0
f(15) = 15%5 = 0
f(55) = 55%5 = 0
这就是hash冲突。

1.8 解决冲突的方法

1. 开放定址法：是一旦发生了冲突，就去寻找下一个空的散列地址
   f(key)=(f(key)+d) mod m。
   只要散列表足够大，空的散列地址总能够找到，并将其记录存入。
   a.d=1,2,3……m-1时，称为线性探测再散列。
   b.d=1^2,-12,2^2,-22,……(-)k^2时，称为二次线性再散列。
   c.d为伪随机序列时，称为伪随机序列再散列。
2. 再散列函数法：f(key)=RH(key),RH()为不同的哈希函数，即在地址冲突的时计算另一个哈希函数地址，直到不发生冲突为止。
3. 链地址法（又称链接法/拉链法）：将所有的哈希地址冲突的记录存储在同一个线性链表中。
4. 公共溢出区法：将所有的哈希地址冲突的记录都填入到溢出表中。

1.9 哈希的应用-哈希表

哈希表（hash table）是哈希函数最主要的应用。
用哈希函数计算关键字的哈希值（hash value）,通过哈希值这个索引就可以找到关键字的存储位置，即桶（bucket）。

哈希表不同于二叉树、栈、序列的数据结构一般情况下，在哈希表上的插入、查找、删除等操作的时间复杂度是 O(1)。

参考：

http://www.nowamagic.net/librarys/veda/detail/1273
https://blog.csdn.net/u012835097/article/details/79407591

2. 哈希桶

2.1 哈希桶

哈希桶就是为了解决哈希冲突
哈希桶算法其实就是链地址解决冲突的方法

2.2 哈希桶结构

哈希桶一般数据结构如下：

typedef struct tagHASH_BUCKET
{
	int iHashBucketSize; //哈希桶大小 如 1024
	int (*pfHash)(const void *); //哈希计算函数 如简单的 y = 3x +1 (key=1时，value = 4 value就是索引) 
	SinList *pstBucket; //哈希桶中每个桶的单链表
}
1
2
3
4
5
6

如下图所示：
有哈希桶，桶大小1024，每个桶都是一个链表来存储数据。
桶1，链表中有三个节点，分别存储了 a，b，c
桶2，链表中有一个节点，存储了数据 f
桶1024，链表中有一个节点，存储了数据 q

2.3. 哈希桶实现

如上如所示，
哈希桶大小是：1024
哈希计算函数：y = 3x +1 (key=0时，value = 1)
哈希桶中每个桶的单链表

现在需要将 （key,value） 0,k
对key=0计算haxi y=3x+1 =1 即：索引时1的桶
那么就在桶1的链表后面加一个节点，节点值为k

参考

https://www.cnblogs.com/xqn2017/p/7997666.html
https://blog.csdn.net/tanggao1314/article/details/51457585