Hash--Introduction to common algorithms

Hash (Hash), also known as hashing, is a very common algorithm. Hash is mainly used in JavaHashMap data structure. The hash algorithm consists of two parts: hash function and hash table. We can know the characteristics of our array. We can quickly locate elements through subscripts (O(1)). Similarly, in the hash table, we can use the key (hash value) To quickly locate a certain value, the hash value is calculated through the hash function (hash(key) = address). The element [address] = value can be located through the hash value. The principle is similar to that of an array.

The best hash function is of course one that can calculate a unique hash value for each key value, but there may often be different keyvalue hash value, which causes conflicts. There are two aspects to judge whether a hash function is well designed:

　1. Few conflicts .

　2. Calculation is fast.

The following are several commonly used hash functions. They all have certain mathematical principles behind them and have undergone a lot of practice. Their mathematical principles will not be explored here.

BKDRHash function (h = 31 * h + c)

This hash function is applied to string hash value calculation in Java.

//String#hashCodepublic int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char val[] = value;for (int i = 0; i 

##DJB2 Hash function (h = h ）

ElasticSearch

uses DJB2The hash function hashes the specified key of the document to be indexed.

##SDBMHash function (h = h ) is applied in

SDBM

(a simple database engine). The above is just a list of three hash functions. Let’s do an experiment to see how they conflict.

　

Java

 1 package com.algorithm.hash; 2  3 import java.util.HashMap; 4 import java.util.UUID; 5  6 /** 7  * 三种哈希函数冲突数比较 8  * Created by yulinfeng on 6/27/17. 9  */10 public class HashFunc {11 12     public static void main(String[] args) {13         int length = 1000000;   //100万字符串14         //利用HashMap来计算冲突数，HashMap的键值不能重复所以length - map.size()即为冲突数15         HashMap<string> bkdrMap = new HashMap<string>();16         HashMap<string> djb2Map = new HashMap<string>();17         HashMap<string> sdbmMap = new HashMap<string>();18         getStr(length, bkdrMap, djb2Map, sdbmMap);19         System.out.println("BKDR哈希函数100万字符串的冲突数：" + (length - bkdrMap.size()));20         System.out.println("DJB2哈希函数100万字符串的冲突数：" + (length - djb2Map.size()));21         System.out.println("SDBM哈希函数100万字符串的冲突数：" + (length - sdbmMap.size()));22     }23 24     /**25      * 生成字符串，并计算冲突数26      * @param length27      * @param bkdrMap28      * @param djb2Map29      * @param sdbmMap30      */31     private static void getStr(int length, HashMap<string> bkdrMap, HashMap<string> djb2Map, HashMap<string> sdbmMap) {32         for (int i = 0; i <div class="cnblogs_code"> The following are </div>10<p><span style="font-family: Calibri;">万、</span><span style="font-family: SimSun;">100</span><span style="font-family: Calibri;"> Ten thousand, </span><span style="font-family: SimSun;">200</span><span style="font-family: Calibri;"> Conflict number situation: </span><span style="font-family: SimSun;"></span></p>
<p><span style="font-family: SimSun;"><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/001/6d0143f1fa951707d245c36e169c2fd5-0.png?x-oss-process=image/resize,p_40" class="lazy" alt=""></span></p>
<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/001/6d0143f1fa951707d245c36e169c2fd5-1.png?x-oss-process=image/resize,p_40" class="lazy" alt=""></p>
<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/001/6d0143f1fa951707d245c36e169c2fd5-2.png?x-oss-process=image/resize,p_40" class="lazy" alt=""> After repeated trials, the number of collisions of the three hash functions is actually about the same. </p>
<p> 　</p>
<p>Python<span style="font-size: 18px;"><strong>3</strong><strong></strong></span></p>
<pre class="brush:php;toolbar:false"> 1 import uuid 2  3 def hash_test(length, bkdrDic, djb2Dic, sdbmDic): 4     for i in range(length): 5         string = str(uuid.uuid1())  #基于时间戳 6         bkdrDic[bkdr(string)] = string 7         djb2Dic[djb2(string)] = string 8         sdbmDic[sdbm(string)] = string 9 10 #BDKR哈希函数11 def bkdr(string):12     hash = 013     for i in range(len(string)):14         hash = 31 * hash + ord(string[i])   # h = 31 * h + c15     return hash16 17 #DJB2哈希函数18 def djb2(string):19     hash = 020     for i in range(len(string)):21         hash = 33 * hash + ord(string[i])   # h = h <p> A hash table is a data structure that needs to be used with a hash function to create an index for quick search <span style="font-family: Calibri;">——</span><span style="font-family: SimSun;">"Algorithm Notes". Generally speaking, it is a fixed-length storage space. For example, </span><span style="font-family: Calibri;">HashMap</span><span style="font-family: SimSun;">The default hash table is a fixed-length hash table of </span><span style="font-family: Calibri;">16</span><span style="font-family: SimSun;"></span><span style="font-family: Calibri;">Entry</span><span style="font-family: SimSun;">Array. After having a fixed-length storage space, the remaining question is how to put the value into which position. Usually if the hash value is </span><span style="font-family: Calibri;">m</span><span style="font-family: SimSun;">, the length is </span><span style="font-family: Calibri;"> n</span><span style="font-family: SimSun;">, then this value is placed at the </span><span style="font-family: Calibri;">m mod n</span><span style="font-family: SimSun;"> position. </span></p><p> <img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/001/6d0143f1fa951707d245c36e169c2fd5-3.png?x-oss-process=image/resize,p_40" class="lazy" alt=""></p><p> The picture above shows the hash and hash table, as well as the solution to the conflict (zipper method). There are many solutions to conflicts, including hashing again until there is no conflict, and also using the zipper method to use linked lists to concatenate elements at the same position as shown in the figure above. </p><p> Imagine that the length of the hash table in the above example is <span   style="max-width:90%">10</span><span style="font-family: SimSun;">, resulting in </span><span style="font-family: Calibri;">1</span><span style="font-family: SimSun;"> conflicts. If the hash The table length is </span><span style="font-family: Calibri;">20</span><span style="font-family: SimSun;">, then there will be no conflict. The search is faster but will waste more space. If the hash table length is </span><span style="font-family: Calibri;">2</span><span style="font-family: SimSun;">, the conflict search will be inverted </span><span style="font-family: Calibri;">3</span><span style="font-family: SimSun;"> times slower, but this will save a lot of space. <strong>So the length selection of the hash table is crucial, but it is also an important problem. </strong></span></p><p><em> Supplement: </em></p><p><em> Hashes are used in many aspects. For example, different values ​​have different hash values, but The hash algorithm can also be designed so that similar or identical values ​​have similar or identical hash values. That is to say, if two objects are completely different, then their hash values ​​are completely different; if two objects are exactly the same, then their hash values ​​are also exactly the same; the more similar the two objects are, then their hash values ​​are also completely different. The more similar they are. This is actually a similarity problem, which means that this idea can be generalized and applied to similarity calculations (such as the Jaccard distance problem), and ultimately applied to accurate advertising placement, product recommendation, etc. </em></p><p><em> In addition, consistent hashing can also be applied in load balancing. How to ensure that each server can evenly distribute the load pressure, a good hash algorithm can also do it. </em></p>

The above is the detailed content of Hash--Introduction to common algorithms. For more information, please follow other related articles on the PHP Chinese website!