散列表原理与应用场景

短命女 2023-06-15 15:26 10阅读 0赞

***散列表的原理和hash函数、解决hash冲突的方法，装填因子、hash性能、应用场景***

# **哈希表（散列表）查找定义** #

想象一个场景，如果想在一个学校中找出一个叫王五的学生，一般思路是去学生处把全校的学生名单列表拿出一个，一个一个的查找，这种方法就是普通的顺序查找，依赖的是姓名关键字的比较。如果你恰巧遇见了一个王五班里的同学张三，他就直接可以带你去找到王五同学，这样就不需要去遍历比较姓名，就可以直接找到王五。  
也就是说，只需要通过某个函数f（张三），使得

存储位置（王五） = f（关键字）

那样我们可以查找关键字f不需要比较就可以获得需要记录的位置，这种存储技术就叫做**散列技术**。

散列技术是在记录存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。我们把这种对应关系f称为散列函数，又称为哈希（Hash）函数。采用散列技术将基础存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表（HashTable）。

# **哈希表实现步骤** #

整个过程其实只有两步：

1.  存储时，通过哈希函数计算记录的哈希地址，并按此地址存储该记录。
2.  查找记录时，同样通过哈希函数计算记录的散列地址，按此散列地址访问该记录。

所以说散列技术既是一种存储方法，也是一种查找方法。它与线性表、树、图等数据结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，而哈希技术之间数据元素不存在逻辑关系，它只与关键字有关系。因此，哈希主要是面向查找的存储结构。

# **哈希表性能分析** #

在没有哈希冲突的情况下，哈希表是在查找中效率最高的，因为它的时间复杂度为O(1)。然而在实际应用中，冲突是不可避免的，那么散列表的平均查找长度取决于那些因素呢？

1.  处理冲突的方法：相同的关键字，相同的散列函数，处理冲突的方法不同，会使得平均查找长度不同。
2.  哈希表的装填因子α： α=填入表中的记录个数/哈希表长度。α标志着哈希表的装满程度。当填入表中的记录越多，α越大，产生冲突的可能性就越大。也就是说哈希表的平均查找长度取决于装填因子，而不是取决于集合中的记录个数。可以通过将哈希表的空间设置的比查找集合大，通过牺牲空间，在换取查找效率。这样我们的哈希查找的时间复杂度就是真的是O(1)了。

# **哈希表的应用场景** #

哈希表适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况。

1. 校验安装文件的完整性  
　　在软件部署的时候，计算软件包当前的哈希值是否与预设值相等，防止软件包被篡改或被替换。Linux提供了基于sha算法的命令，用于计算文件的哈希值

sha256sum fileName

2. 存储和校验用户口令

用户口令不能用明文存储，更进一步，如果系统不知道用户口令明文，那就更好了，而哈希算法就可以做到既不知道用户明文，又可以校验用户口令。详见《基于哈希算法的web账户口令存储方法》，[http://www.cnblogs.com/todsong/archive/2012/04/22/2465178.html][http_www.cnblogs.com_todsong_archive_2012_04_22_2465178.html]

3. 校验重复提交的消息

用户可能因为误操作重复提交数据，而这些数据会对系统产生影响，若要拒绝这些消息，最好的方法就是在每次提交时，计算消息的哈希值，当发现疑似重复提交的时候，做消息哈希值的对比。这是一个CPU密集型的操作，如果系统的CPU负载比较低，可以考虑使用。至于如何在代码中使用哈希算法，这里就不描述了，Java、C++都有现成的算法库可用。

4. 作为数据库乐观锁的条件

数据库中，最常用的乐观锁方法是在表中增加额外的一列，用于记录一行数据的版本值，通常是一个计数或是时间戳。但是，一张已经存在大量数据的表需要增加额外的版本列，似乎不太可行，也不太方便，此时可以通过哈希计算出虚拟的版本列，用于乐观锁定控制。Oracle数据库提供了哈希算法的存储过程，输入某几个列数据的字符连接，输出该条记录的哈希值，通过比较该值判断数据是否被修改。下面是摘自《Oracle 9i&10g 编程艺术》的例子

5. 作为数据库表分区的分区条件

如果难以按照某一个列对数据库表做分区，表中的数据又没有太多的业务逻辑，那么通过哈希函数强行分区是个不错的选择。详见《Oracle分区表，哈希分区的新建与增加》，[http://www.cnblogs.com/todsong/archive/2012/08/26/2657158.htm][http_www.cnblogs.com_todsong_archive_2012_08_26_2657158.htm]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 2][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 4][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 5][]![20191123100231955.png][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 6][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 7][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 8][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 9][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 10][]

[http_www.cnblogs.com_todsong_archive_2012_04_22_2465178.html]: http://www.cnblogs.com/todsong/archive/2012/04/22/2465178.html
[http_www.cnblogs.com_todsong_archive_2012_08_26_2657158.htm]: http://www.cnblogs.com/todsong/archive/2012/08/26/2657158.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191123100228825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191123100232582.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191123100232236.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191123100232500.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191123100232400.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191123100229120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[20191123100231955.png]: https://img-blog.csdnimg.cn/20191123100231955.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191123100232588.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20191123100232580.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20191123100229938.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20191123100522451.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20191123100537720.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDM4Nzkz,size_16,color_FFFFFF,t_70