哈希表 – 分析目标并选择一个好的哈希函数

发布时间：2020-12-15 00:39:09 所属栏目：Java 来源：网络整理

导读：这不是具体解决方案的具体问题;但它反而是对我无法找到关于如何为哈希表和类似任务选择好的哈希函数的任何好的Stack Overflow问题的回应. 所以！让我们来谈谈哈希函数,以及如何选择哈希函数.如果一个编程菜鸟需要为他们的特定任务选择一个好的哈希函数,那么

这不是具体解决方案的具体问题;但它反而是对我无法找到关于如何为哈希表和类似任务选择好的哈希函数的任何好的Stack Overflow问题的回应.

所以！让我们来谈谈哈希函数,以及如何选择哈希函数.如果一个编程菜鸟需要为他们的特定任务选择一个好的哈希函数,那么选择一个呢？简单快速的Fowler-Noll-Vo什么时候适合？他们什么时候应该在MurmurHash3中供应？在比较各种选项时,您是否有良好的资源链接？

解决方法

哈希表的哈希函数应该具有这两个属性

>均匀性H()的所有输出应尽可能均匀分布.换句话说,对于32位散列函数,每个输出的概率应该等于1/2 ^ 32. (对于n位,它应该是1/2 ^ n).使用统一散列函数,对于任何可能的输入,碰撞的可能性被最小化到最低.
>低计算成本与加密散列函数相比,表格的散列函数预计是快速的,其中速度是针对前映像阻力进行交易的(例如,很难从给定的散列值中找到消息)和碰撞阻力.

出于哈希表的目的,所有加密函数都是BAD选择,因为计算成本是巨大的.因为此处的散列不是用于安全性而是用于快速访问. MurmurHash被认为是适用于大型哈希表或哈希索引的速度最快且统一的函数之一.对于小型表,一个简单的哈希函数应该没问题.一个简单的哈希是我们混合对象的值(通过乘法,加法和减法与一些素数).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!