ハッシュ -- 一般的なアルゴリズムの概要

ハッシュ (Hash) はハッシュとも呼ばれ、非常に一般的なアルゴリズムです。ハッシュは主にJavaのHashMapデータ構造で使用されます。ハッシュ アルゴリズムには、ハッシュ関数とハッシュ テーブルの 2 つの部分が含まれます。配列の特性は添字 (O(1)) を通じて簡単に見つけることができます。同様に、ハッシュ テーブルでは、キー (ハッシュ値) を通じて特定の値を素早く見つけることができます。ハッシュ値はハッシュ関数(ハッシュ(キー) = アドレス)によって計算されます。要素 [address] = value は、ハッシュ値を通じて見つけることができます。原理は配列の原理と似ています。

最適なハッシュ関数は、もちろん、keyの値ごとに一意のハッシュ値を計算できるものですが、異なるkeyの値のハッシュ値が存在することがよくあり、それが競合を引き起こす可能性があります。ハッシュ関数が適切に設計されているかどうかを判断するには:

1. 競合が少ない。

2. 計算が速い。

一般的に使用されるハッシュ関数のいくつかを以下に示します。それらはすべて特定の数学的原理を背景にしていますが、ここではその数学的原理については説明しません。

BKDRハッシュ関数(h = 31 * h + c)

このハッシュ関数は、Javaにおける文字列のハッシュ値計算に適用されます。

//String#hashCodepublic int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char val[] = value;for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];    //BKDR 哈希函数，常数可以是131、1313、13131……        }
        hash = h;
    }return h;
}

DJB2 ハッシュ関数 (h = h << 5 + h + c = h = 33 * h + c) ElasticSearch ただDJB2

ハッシュ関数を使用して、インデックスを作成するドキュメントの指定されたkeyをハッシュします。 SDBMハッシュ関数(

h = h < SDBM (簡易データベースエンジン))を使用します。 上記は 3 つのハッシュ関数をリストしただけです。それらの競合がどのように見えるかを実験してみましょう。 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, String> bkdrMap = new HashMap<String, String>();16         HashMap<String, String> djb2Map = new HashMap<String, String>();17         HashMap<String, String> sdbmMap = new HashMap<String, 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, String> bkdrMap, HashMap<String, String> djb2Map, HashMap<String, String> sdbmMap) {32         for (int i = 0; i < length; i++) {33             System.out.println(i);34             String str = UUID.randomUUID().toString();35             bkdrMap.put(String.valueOf(str.hashCode()), str);   //Java的String.hashCode就是BKDR哈希函数， h = 31 * h + c36             djb2Map.put(djb2(str), str);    //DJB2哈希函数37             sdbmMap.put(sdbm(str), str);    //SDBM哈希函数38         }39     }40 41     /**42      * djb2哈希函数43      * @param str44      * @return45      */46     private static String djb2(String str) {47         int hash = 0;48         for (int i = 0; i != str.length(); i++) {49             hash = hash * 33 + str.charAt(i);    //h = h << 5 + h + c = h = 33 * h + c50         }51         return String.valueOf(hash);52     }53 54     /**55      * sdbm哈希函数56      * @param str57      * @return58      */59     private static String sdbm(String str) {60         int hash = 0;61         for (int i = 0; i != str.length(); i++) {62             hash = 65599 * hash + str.charAt(i);    //h = h << 6 + h << 16 - h + c = 65599 * h + c63         }64         return String.valueOf(hash);65     }66 }

以下は、10

million、

100million、

200

millionの競合数です。

試行を重ねると、実際には 3 つのハッシュ関数の衝突回数はほぼ同じになりました。

Python

3

 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 << 5 + h + c22     return hash23 24 #SDBM哈希函数25 def sdbm(string):26     hash = 027     for i in range(len(string)):28         hash = 65599 * hash + ord(string[i])    # h = h << 6 + h << 16 - h + c29     return hash30 31 length = 10032 bkdrDic = dict() #bkdrDic = {}33 djb2Dic = dict()34 sdbmDic = dict()35 hash_test(length, bkdrDic, djb2Dic, sdbmDic)36 print("BKDR哈希函数100万字符串的冲突数：%d"%(length - len(bkdrDic)))37 print("DJB2哈希函数100万字符串的冲突数：%d"%(length - len(djb2Dic)))38 print("SDBM哈希函数100万字符串的冲突数：%d"%(length - len(sdbmDic)))

ハッシュテーブルは、クイック検索用のインデックスを作成するためにハッシュ関数とともに使用する必要があるデータ構造です——「アルゴリズムノート」。一般的に言えば、これは固定長の記憶域です。たとえば、HashMapのデフォルトのハッシュテーブルは、16の固定長のEntry配列です。固定長の記憶域を確保した後、残りの問題は、値をどの位置に配置するかです。通常、ハッシュ値が m で、長さが n の場合、値は に配置されます。 m mod n の位置。

上の図は、ハッシュとハッシュ テーブル、および競合の解決策 (ジッパー メソッド) を示しています。競合を解決するには、競合がなくなるまで再度ハッシュする方法や、上図に示すように、ジッパー方式を使用してリンク リストを使用して同じ位置の要素を連結する方法など、さまざまな方法があります。

上記の例のハッシュ テーブルの長さが 10 で、1 の競合が発生すると想像してください。ハッシュ テーブルの長さが 20 の場合、競合は発生しません。検索は高速になりますが、ハッシュ テーブルの長さが 2 回の場合、競合検索は遅くなりますが、多くのスペースを節約できます。空間。 したがって、ハッシュ テーブルの長さの選択は非常に重要ですが、同時に重要な問題でもあります。 補足:

ハッシュは、異なる値が異なるハッシュ値を持つなど、さまざまな場面で使用されますが、ハッシュアルゴリズムは、類似または同一の値を類似または類似させるように絶妙に設計することもできます。ハッシュ値は同じです。つまり、2 つのオブジェクトが完全に異なる場合、それらのハッシュ値は完全に異なります。2 つのオブジェクトがまったく同じである場合、それらのハッシュ値もまったく同じになります。それらのハッシュ値も完全に異なります。これは実際には類似性の問題です。つまり、この考え方は一般化して類似性の計算 (Jaccard 距離問題など) に適用でき、最終的には正確な広告の掲載や製品の推奨などに適用できます。

さらに、コンシステントハッシュは負荷分散にも適用でき、各サーバーが負荷圧力を均等に共有できるようにする方法として、優れたハッシュアルゴリズムを使用することもできます。