到底什么是hash? - 知乎 - Lance

以下内容摘自《Data Structures for Game Programmers》,顺便安利一下这本书（只有英文版），表达清晰易懂，行文诙谐幽默。如果想入门数据结构却又看不进去国内枯燥的教材，可以翻翻这本。

一个需要使用hash表的情景：有三个分布于0--1000000的稀疏数据(Sparse Data) 键，我想根据这些键的数值插入数组的相应位置，这样查找起来很方便。但问题在于只有三个键却要用长度为1000001的数组！而如果用链表的话又失去了查找方便的特性。

一个基础的hash表就是一个数组，现在我想把三个稀疏数据插到一个长度只有10的数组里，就需要把这三个数都做有损压缩，最简单的方法便是对10取模，这一步计算就是一个简单hash函数。而这种方法很容易导致造成两个不同的数hash成同一个，TIP里还说采用对素数取模可以有效减小哈希碰撞。

这里介绍了另一种可以减少哈希碰撞的算法，即把key的各个位相加得出的数作为hash结果，相应的hash表的长度也要增加为54。也可以将每一位乘以位数再相加，这样会进一步减少哈希碰撞的几率，不过hash表的长度也需要增加。实际上有无数种hash函数，各有各的优缺点。

由于无论使用多么高明的hash函数，总会产生哈希碰撞，因此可以使用一些方法来处理这些冲突问题，其中一个方法便是给哈希表的每个cell一个链表结构。

Original url: Access
Created at: 2019-04-12 18:43:59
Category: default
Tags: none

未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到

请先后发表评论
  • 最新评论
  • 总共0条评论