各種Hash関数の衝突率分析

10540 ワード
sh
文字列Hash関数の比較
 今日は自分の理解に基づいて、いくつかの文字列hash関数を整理し直しました。テンプレートを使って、広い文字列をサポートします。コードは下記の通りです。
/// @brief BKDR Hash Function
/// @detail       Brian Kernighan Dennis Ritchie 《The C Programming Language》        ，        hash  ，  Java         Hash  （     31）。
template<class T>
size_t BKDRHash(const T *str)
{
	register size_t hash = 0;
	while (size_t ch = (size_t)*str++)
	{		
		hash = hash * 131 + ch;   //      31、131、1313、13131、131313..
		//                       ，       ：hash = hash << 7 + hash << 1 + hash + ch;
		//     Intel   ，CPU                ，
		//       100         ，           0（   Debug ，             1/3）；
		//  ARM  RISC        ，  ARM    Booth's Algorithm   32       ，         ：
		//    8-31   1 0 ，  1     
		//    16-31   1 0 ，  2     
		//    24-31   1 0 ，  3     
		//   ，  4     
		//   ，         ，                		
	}
	return hash;
}
/// @brief SDBM Hash Function
/// @detail            SDBM（          ）       ，  BKDRHash    ，        。
template<class T>
size_t SDBMHash(const T *str)
{
	register size_t hash = 0;
	while (size_t ch = (size_t)*str++)
	{
		hash = 65599 * hash + ch;		
		//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
	}
	return hash;
}
/// @brief RS Hash Function
/// @detail  Robert Sedgwicks  《Algorithms in C》        。
template<class T>
size_t RSHash(const T *str)
{
	register size_t hash = 0;
	size_t magic = 63689;	
	while (size_t ch = (size_t)*str++)
	{
		hash = hash * magic + ch;
		magic *= 378551;
	}
	return hash;
}
/// @brief AP Hash Function
/// @detail  Arash Partow     hash  。
template<class T>
size_t APHash(const T *str)
{
	register size_t hash = 0;
	size_t ch;
	for (long i = 0; ch = (size_t)*str++; i++)
	{
		if ((i & 1) == 0)
		{
			hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
		}
		else
		{
			hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
		}
	}
	return hash;
}
/// @brief JS Hash Function
///  Justin Sobel     hash  。
template<class T>
size_t JSHash(const T *str)
{
	if(!*str)		 //        ，            0
		return 0;
	register size_t hash = 1315423911;
	while (size_t ch = (size_t)*str++)
	{
		hash ^= ((hash << 5) + ch + (hash >> 2));
	}
	return hash;
}
/// @brief DEK Function
/// @detail       Donald E. Knuth 《Art Of Computer Programming Volume 3》      。
template<class T>
size_t DEKHash(const T* str)
{
	if(!*str)		 //        ，            0
		return 0;
	register size_t hash = 1315423911;
	while (size_t ch = (size_t)*str++)
	{
		hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
	}
	return hash;
}
/// @brief FNV Hash Function
/// @detail Unix system          hash  ，       hash_map   。
template<class T>
size_t FNVHash(const T* str)
{
	if(!*str)	//        ，            0
		return 0;
	register size_t hash = 2166136261;
	while (size_t ch = (size_t)*str++)
	{
		hash *= 16777619;
		hash ^= ch;
	}
	return hash;
}
/// @brief DJB Hash Function
/// @detail  Daniel J. Bernstein       hash  。
template<class T>
size_t DJBHash(const T *str)
{
	if(!*str)	//        ，            0
		return 0;
	register size_t hash = 5381;
	while (size_t ch = (size_t)*str++)
	{
		hash += (hash << 5) + ch;
	}
	return hash;
}
/// @brief DJB Hash Function 2
/// @detail  Daniel J. Bernstein       hash  。
template<class T>
size_t DJB2Hash(const T *str)
{
	if(!*str)	//        ，            0
		return 0;
	register size_t hash = 5381;
	while (size_t ch = (size_t)*str++)
	{
		hash = hash * 33 ^ ch;
	}
	return hash;
}
/// @brief PJW Hash Function
/// @detail       AT&T      Peter J. Weinberger         hash  。
template<class T>
size_t PJWHash(const T *str)
{
	static const size_t TotalBits		= sizeof(size_t) * 8;
	static const size_t ThreeQuarters	= (TotalBits  * 3) / 4;
	static const size_t OneEighth		= TotalBits / 8;
	static const size_t HighBits		= ((size_t)-1) << (TotalBits - OneEighth);	
	
	register size_t hash = 0;
	size_t magic = 0;	
	while (size_t ch = (size_t)*str++)
	{
		hash = (hash << OneEighth) + ch;
		if ((magic = hash & HighBits) != 0)
		{
			hash = ((hash ^ (magic >> ThreeQuarters)) & (~HighBits));
		}
	}
	return hash;
}
/// @brief ELF Hash Function
/// @detail    Unix Extended Library Function         hash  ，     PJW Hash   。
template<class T>
size_t ELFHash(const T *str)
{
	static const size_t TotalBits		= sizeof(size_t) * 8;
	static const size_t ThreeQuarters	= (TotalBits  * 3) / 4;
	static const size_t OneEighth		= TotalBits / 8;
	static const size_t HighBits		= ((size_t)-1) << (TotalBits - OneEighth);	
	register size_t hash = 0;
	size_t magic = 0;
	while (size_t ch = (size_t)*str++)
	{
		hash = (hash << OneEighth) + ch;
		if ((magic = hash & HighBits) != 0)
		{
			hash ^= (magic >> ThreeQuarters);
			hash &= ~magic;
		}		
	}
	return hash;
}
これらのhashのハッシュ品質と効率について簡単なテストを行いました。テスト結果は以下の通りです。
テスト1：1000個の大きさ文字と数字でランダムなANSI文字列（重複なし、各文字列の最大長さは64文字を超えない）に対してハッシュを行います。
文字列関数
衝突の数
100003を除いた後の衝突数
BKDRHash
0
4826
SDBMHash
2
4814
RSHash
2
4886
APhash
0
4846
ELFHash
1515
6120
Jshas
779
5587
DEKHash
863
5643
FNVHash
2
4872
DJ Bhash
832
5645
DJ 2 Hash
695
5309
PJWHAS
1515
6120
 
テスト2：1000個のユニコムからなる任意の文字列（重複なし、各文字列の最大長さは64文字を超えない）に対してハッシュを行います。
文字列関数
衝突の数
100003を除いた後の衝突数
BKDRHash
3
4710
SDBMHash
3
4904
RSHash
3
4822
APhash
2
4891
ELFHash
16
4869
Jshas
3
4812
DEKHash
1
4755
FNVHash
1
4803.
DJ Bhash
1
4749
DJ 2 Hash
2
4817
PJWHAS
16
4869
 
テスト3：1000個のランダムANSI文字列（重複なし、各文字列の最大長さは64文字を超えない）をハッシュする：
文字列関数
所要時間(ミリ秒)
BKDRHash
109
SDBMHash
109
RSHash
124
APhash
187
ELFHash
249
Jshas
172
DEKHash
140
FNVHash
125
DJ Bhash
125
DJ 2 Hash
125
PJWHAS
234
 
結論：私のサンプルにはいくつかの特殊性があるかもしれません。ASCIIコード文字列をハッシュする時、PJWとELF Hash（実は同じアルゴリズムです。）は品質も効率もかなり悪いです。例えば、「b 5」と「aE」の2つの文字列はPJWでハッシュされたshの値と同じです。また、他のいくつかの種類のハッシュ関数は、JS/DEK/DJB Hashのように、アルファベットと数字からなる文字列のハッシュ効果もあまり良くないです。相対的にBKDRとSDBMのような簡単なHashの効率と効果が良いです。
その他:
著者：icefireelf
よく使われる文字列Hash関数にはELFHash、APHashなどがあります。これらの関数はビット演算を使用して各文字が最後の関数値に影響を与えます。また、MD 5とSHA 1に代表される寄せ集め関数もあります。これらの関数はほとんど衝突を見つけることができません。
常用文字列のハッシュ関数はBKDRHash、APhash、DJ Bhash、JSHsh、RSHash、SDBMHash、PJWHAS、ELLFHashなどです。これらのハッシュ関数については、小さな評価を行いました。
Hash関数
データ1
データ2
データ3
データ4
データ1得点
データ2得点
データ3得点
データ4得点
平均点
BKDRHash
2
0
4774
481
96.55
100
90.95
82.05
92.64
APhash
2
3
4754
493
96.55
88.46
100
51.28
86.28
DJ Bhash
2
2
4975
474
96.55
92.31
0
100
83.43
Jshas
1
4
4761
506
100
84.62
96.83
17.95
81.94
RSHash
1
0
4861
505
100
100
51.58
20.51
75.96
SDBMHash
3
2
4849
504
93.1
92.31
57.01
23.08
72.41
PJWHAS
30
26
4878
513
0
0
43.89
0
21.95
ELFHash
30
26
4878
513
0
0
43.89
0
21.95
データ1は100000文字と数字からなるランダム・シリアル・ハッシュの個数です。データ2は100000個の意味のある英文の文のハッシュの衝突個数です。データ3は、データ1のハッシュ値と100003（大きい素数）のモジュラスを求めて線形テーブルに格納された衝突の個数です。データ4は、データ1のハッシュ値と1000019（より大きい素数）のモジュレータを求めて線形テーブルに格納された数です。
以上の平均得点が得られました。平均数は平方平均です。BKDRHashは実際の効果や符号化の実現においても効果が最も優れています。APHashも優れたアルゴリズムです。DJ Bhash、Jsh、RSHashはSDBMHashとそれぞれ長所があります。PJWHASとELLFHashは最も悪いですが、得点は似ています。アルゴリズムの本質は似ています。
unsigned int SDBMHash(char *str)
{
    unsigned int hash = 0;
 
    while (*str)
    {
        // equivalent to: hash = 65599*hash + (*str++);
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// RS Hash Function
unsigned int RSHash(char *str)
{
    unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int hash = 0;
 
    while (*str)
    {
        hash = hash * a + (*str++);
        a *= b;
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// JS Hash Function
unsigned int JSHash(char *str)
{
    unsigned int hash = 1315423911;
 
    while (*str)
    {
        hash ^= ((hash << 5) + (*str++) + (hash >> 2));
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
    unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
    unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
    unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
    unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
    unsigned int hash             = 0;
    unsigned int test             = 0;
 
    while (*str)
    {
        hash = (hash << OneEighth) + (*str++);
        if ((test = hash & HighBits) != 0)
        {
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// ELF Hash Function
unsigned int ELFHash(char *str)
{
    unsigned int hash = 0;
    unsigned int x    = 0;
 
    while (*str)
    {
        hash = (hash << 4) + (*str++);
        if ((x = hash & 0xF0000000L) != 0)
        {
            hash ^= (x >> 24);
            hash &= ~x;
        }
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
 
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// DJB Hash Function
unsigned int DJBHash(char *str)
{
    unsigned int hash = 5381;
 
    while (*str)
    {
        hash += (hash << 5) + (*str++);
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// AP Hash Function
unsigned int APHash(char *str)
{
    unsigned int hash = 0;
    int i;
 
    for (i=0; *str; i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
        }
    }
 
    return (hash & 0x7FFFFFFF);
}
スクロールバーの出現、ページのぶれの問題を解決します。
画像回転アルゴリズム