到底什么是hash? - 知乎 - Victor Chen

哈希不是一种算法而是一类算法，你可以按照不同的需求编写适合的算法。在计算机范畴中应用非常广泛，它最开始的用途是更快的查找。中文散列表很清楚地描述这种数据结构的样子，键值对分散地排列在一个表里面，而分散到哪一列上是根据它的键和适合的算法计算出来的值决定的，分散的方式最基本的原则就是避免冲突。

跟其他基本的算法一样，它也是五六十年代就已经发明出来了，相对其他数据结构，它在各种操作在时间复杂度以及空间复杂度它有什么哪些优势和劣势呢？（这个表里没有常见的 AVL 树和 B 类树）

部分常见符号表数据结构对比（Algorithms 4th Edition By Robert Sedgewick）

离开这个算法就没有高级编程语言甚至汇编语言中变量这个概念，那样我们只能像使用机器语言那样用地址序号操作内存里的数据。

它基本的数据结构：

题主说的整数型数值、字符串类型和二进制数组类型都是通过跟上面类似的形式塞到通过哈希函数计算出来的值对应的 bucket 里面，而各个 bucket 里面存储着一个键值对（通常用一个存键和一个存值的数组维护）。但话是那么说，为了解决上图 Sandra Dee 的尴尬，计算机科学家们发明了各式各样的方法避免这种冲突，否则 152 里储存的是 Smith 还是 Dee 呢？最基本的解决办法是利用链表的数据结构扩展各个 bucket。

还有一个方法，动态改变数组大小（实时检测和保持一个固定的密度，这在用数组顺序排列的队列或栈中也有应用）和把冲突键值对推后到下一个的方式，下面显示了更小的密度冲突出现的可能性更小，这一算法虽然容许冲突但冲突需要更多的时间计算，影响到性能，这也叫线性探测法。

好像还没回答题主字符串和二进制文件如何哈希的问题，各种基本数据类型的哈希方法可以参考下 OpenJDK 中对应的包装类的源码，每种数据类型都有自己的 hash() 方法，最简单的方法就是把一个值中能代表它唯一性的每个属性（比如对象的每一个变量的实例变量的值，数组中的各个元素）哈希一次再加起来，然后再跟一个你要的哈希表长度来个模运算。

在 Java 中判断两个对象相等更快的方法是判断它们的 hash code 是否相等，可见解决安全性问题的哈希方法也归约于哈希函数对于唯一性问题的解决。所以才有什么 MD5、SHA-1、SHA-2 之类的加密算法，因为其中一个二进制值的不同就会引起十亿个二进制值组成的 hash 值的不同，所以几乎不存在两个哈希值相同的而且都有意义的二进制数组存在。（为什么说是几乎，如果无数多的猴子在无数多的打字机上随机的打字,并持续无限久的时间,那么在某个时候，它们必然会打出莎士比亚的全部著作，也就是猴子和打字机问题。）

Original url: Access
Created at: 2019-04-12 18:46:07
Category: default
Tags: none

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

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