关于Hash表,你不得不知道的知识点

本文主要是介绍关于Hash表,你不得不知道的知识点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

定义：

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，也称为hash函数，存放记录的数组叫做散列表。

给定表M，如果存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

基础概念：

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。对于查找一个特定的key，我们仅仅需要进行常数次的运算（考虑到hash冲突）即可得到key对应的位置，因此hash表的查找复杂度为O(1)。
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称做同义词。hash表的构造过程通常是：根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址区间上，并以关键字在地址区间中的“散列地址（hash值）”作为记录在表中的存储位置。
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

哈希函数：

将关键字映射为hash地址是通过哈希函数来实现的，不同的hash函数

通过将关键字(key)映射到表中一个位置，可以直接访问记录，以提高查找的速率，相比较其他的查找结构，哈希表查找的时间复杂度更低。其中用于映射的函数称为哈希函数，哈希函数有多种，常见的哈希函数包括CRC32，MD5，SHA等。其实哈希函数就是一种特殊的函数，通过输入x,得到唯一的f(x),从而实现尽可能地降低对key对应得hash值得重复问题，减少哈希冲突发生的概率。

常见的hash函数有：

1.直接寻址法：取关键字或关键字的某个线性函数值为散列地址。

2. 数字分析法：分析一组数据，比如一组员工的出生年月日，这时就会发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3.平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

哈希冲突：

哈希冲突就是两个不同的key，经过哈希函数运算之后，得到了相同的hash值，再对值进行存储时，发现要存储的地址空间已被他值占用，此时发生冲突问题。产生哈希冲突的原因并不是因为我们选取的哈希函数不合理，而是因为我们进行运算的键key，可能性太多了，总会存在一些情况导致hash值出现相同。所以说，hash冲突时必然的，我们需要对哈希冲突进行处理。

小李和小王通过哈希函数的运算之后，映射到了哈希表下标为1的同一位置，此时发生hash碰撞。