GetHashCode()函数如何生成整数哈希？这是一个不是唯一的随机值吗？
在字符串中,它被覆盖以确保特定字符串只存在一个哈希码.怎么做？
如何使用哈希码加速搜索哈希表中的特定键？
使用哈希代码而不是直接在集合中使用索引(比如在数组中)有什么好处？
有人可以帮忙吗？
Bob*_*Gee 17
基本上,散列函数使用一些通用函数来消化数据并为该数据生成指纹(以及此处的整数).与索引不同,此指纹仅取决于数据,并且不应基于数据进行任何可预测的排序.对单个数据位的任何更改也应该相当大地改变指纹.
请注意,这无法保证不同的数据不会提供相同的哈希值.事实上恰恰相反:这种情况经常发生,被称为碰撞.但是,对于一个整数,概率大约相当于40亿分之一(1 ^ 2 ^ 32).如果发生碰撞,您只需比较要散列的实际对象,看它们是否匹配.
然后,该指纹可以用作存储值的数组(或arraylist)的索引.由于指纹仅依赖于数据,因此您可以计算某些内容的哈希值,并检查该数组元素是否存在该哈希值以查看它是否已存储.否则,如果它与项目匹配,则必须检查整个数组.
您还可以通过使用2个数组非常快速地执行关联数组,一个具有Key值(通过哈希索引),另一个具有映射到这些键的值.如果使用散列,则只需知道密钥的散列即可找到密钥的匹配值.这比在排序键列表上执行二进制搜索或扫描整个数组以查找匹配键要快得多.
有很多种方法可以生成哈希,并且所有方法都有各种优点,但很少有简单的方法.我建议您查看关于哈希函数的维基百科页面以获取更多信息.
小智 5
哈希码是索引,哈希表处于最低级别,是一个数组.但是对于给定的键值,我们以不同的方式确定哈希表中的索引,以便更快地进行数据检索.
示例:您有1,000个单词及其定义.您希望存储它们,以便您可以非常非常快速地检索单词的定义 - 比二进制搜索更快,这是您必须对数组执行的操作.
所以你创建一个哈希表.你从一个大于1,000个条目的阵列开始 - 比如5000(越大,时间效率越高).
您将使用表格的方式是,单词查找,并将其转换为0到4,999之间的数字.你选择算法来做这个; 这是哈希算法.但你无疑会写一些非常快的东西.
然后使用转换后的数字作为5,000元素数组的索引,并在该索引处插入/查找定义.根本没有搜索:你直接从搜索词创建了索引.
我所描述的所有操作都是恒定的时间; 当我们增加条目数时,它们都不会花费更长的时间.我们只需要确保哈希中有足够的空间来最小化"冲突"的可能性,即两个不同的词将转换为相同的整数索引的可能性.因为任何哈希算法都可能发生这种情况,我们需要添加检查以查看是否存在冲突,并执行一些特殊操作(如果"hello"和"world"都哈希到1,234并且"hello"已经在表中,那么我们将使用"世界"吗？最简单的是将它放在1,235中,并调整我们的查找逻辑以允许这种可能性.)
编辑:重新阅读你的帖子后:哈希算法绝对不是随机的,它必须是确定性的.在我的例子中为"hello"生成的索引每次必须是1,234; 这是查找可以工作的唯一方法.