Hash）又称散列，它是一个很常见的算法。在Java的HashMap数据结构中主要就利用了哈希。哈希算法包括了哈希函数和哈希表两部分。我们数组的特性可以知道，可以通过下标快速（O(1)）的定位元素，同理在哈希表中我们可以通过键（哈希值）快速的定位某个值，这个哈希值的计算就是通过哈希函数(hash(key) = address )计算得出的。通过哈希值即能定位元素[address] = value，原理同数组类似。
最好的哈希函数当然是每个key值都能计算出唯一的哈希值，但往往可能存在不同的key值的哈希值，这就造成了冲突，评判一个哈希函数是否设计良好的两个方面：
1.冲突少。
2.计算快。
下面给出几种常用的哈希函数，它们的背后都有一定的数学原理且经过大量实践，其数学原理不在这里探究。
BKDR哈希函数（h = 31 * h + c）
Java的字符串哈希值计算。
DJB2 哈希函数（h = h << 5 + h + c = h = 33 * h + c）
就利用了DJB2哈希函数对要索引文档的指定key进行哈希。
SDBM哈希函数（h = h << 6 + h << 16 - h + c = 65599 * h + c）
SDBM（一种简单的数据库引擎）中被应用。
以上只是列举了三种哈希函数，我们做下试验，看看它们的冲突情况是怎么样的。
Java
讯享网
10万、100万、200万的冲突数情况：
反复试验实际上三种哈希函数的冲突数差不多。
Python3
——《算法笔记》。一般来讲它就是一个定长的存储空间，比如HashMap默认的哈希表就是定长为16的Entry数组。有了定长的存储空间过后，剩下的问题就是如何将值放入哪个位置，通常如果哈希值是m，长度为n，那么这个值就放到m mod n位置处。
java基础之hashtable
上图就是哈希和哈希表，以及产生冲突的解决办法（拉链法）。产生冲突后的解决办法有很多，有再哈希一次直到没有冲突，也有向上图一样采用拉链法利用链表将相同位置的元素串联。
10，产生了1次冲突，如果哈希表长度为20，那么就不会产生冲突查找更快但会浪费更多空间，如果哈希表长度为2，将会倒置3次冲突查找更慢但这样又会节省不少空间。所以哈希表的长度选择至关重要，但同时也是一个重要的难题。
补充：
哈希在很多方面有应用，例如在不同的值有不同的哈希值，但也可以将哈希算法设计精妙使得相似或相同的值有相似或相同的哈希值。也就是说如果两个对象完全不同，那么它们的哈希值也完全不同；如果两个对象完全相同，那么它们的哈希值也完全相同；两个对象越相似，那么它们的哈希值也就越相似。这实际上就是相似性问题，也就是说这个思想可以被推广应用到相似性的计算（例如Jaccard距离问题），最终应用到广告精准投放、商品推荐等。
另外，一致性哈希也可应用在负载均衡，如何保证每台服务器能均匀的分摊负载压力，一个好的哈希算法也可做到。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/6897.html