关于哈希表

2018-03-24 本文已影响19人 8fe8946fa366

昨天去面试被问到的第一个问题就是，哈希表是什么？？？

哈希表并不是字典啊，女人，你昨天回答的那是字典，并不是真的哈希表。

哈希表是根据key值直接访问数据的一种数据结构，也就是说通过一个映射函数（散列函数）把key值映射到表中的一个位置来访问记录，增加了查找的速度。

这个表其实就是一个存放数据的数组，也可以叫做散列表或者哈希表。

记录的存储位置=f(关键字)，f()就是散列函数。

首先要把一组数据存储在规定了散列函数的哈希表里。首先每一个key对应一个value，根据散列函数计算出key在数组中对应的下标，把value存储到这个下标对应的数组空间里。

使用的时候，根据key值计算出对应的数组下标，也就找到了这个下标对应的value值。

哈希表可以把不同数量的数据压缩到同一个大小的数据集里，这种方式在海量数据查找的时候应用非常广泛。

哈希表应用于数据安全领域的加密算法，把一些长度不同的信息转化成长度相同的编码。比如说：❓

哈希表的查找速度非常快，只要知道了key值就可以在O(1)的时间复杂度内找到对应的value。

不同的关键字经过散列函数的计算得到了相同的地址。

好的散列函数＝计算简单＋散列地址分布均匀

优点：哈希表对于查找，插入和删除操作的速度都非常快，而且编程实现也相对简单。

缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据。

除法散列 index = key % 16

平方散列 index = (key * key) >> 28

斐波那契散列 index = (key * 2654435769) >> 28 2654435769这个数就是n位对应的F(n)

1.再散列法

就是当遇到散列冲突的时候给这个key值再找一个新的哈希值。

线性探测再散列，当遇到散列冲突以后，顺序遍历表单元，直到找到一个空的表单元或遍历完整个表单元。

二次探测再散列，遇到散列冲突以后设置di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )，在冲突表单元的左右两侧寻找新的表单元，

伪随机探测再散列，把d设置为一个随机数序列。

例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。

线性探测再散列：，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入6号单元。

二次探测再散列：下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。

伪随机探测再散列：伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

2.再哈希法

同时构造多个哈希函数，当用第一个哈希函数发生冲突以后，换成第二个哈希函数，这种方法增加了计算成本。

3.链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。