プログラマ必須:文字列ハッシュ関数の比較

ある株式取引システムのバックグラウンドでは、様々な株式コードのTickを迅速に検索するために、ハッシュ値を計算し、ハッシュテーブルに格納します.良いハッシュ関数は,衝突を低減するために良好な分布性を実現できるはずである.ここではBKDRHAsh,APHash,JSHash,RSHash,SDBMHash,PJWHAsh,ELFHash,DJBHashを含むいくつかの一般的な文字列ハッシュを選択し,異なる文字列集合でテストすることによってその性能をテストした.

各種常用アルゴリズム

BKDRHash

BKDRHAshはKernighanとDennisが『The C programming language』で提案したものである.このアルゴリズムの定数131がどのように選択されたのかは不明であり,知る者から伝言が得られる.

   public static int bkdrhash(String str) {
      final int seed = 131;
      
      int hash = 0;
      
      for (int i = 0; i < str.length(); i++) {
         hash = hash * seed + (int)str.charAt(i);
      }
      
      return hash & 0x7FFFFFFF;
   }

APHash

Arash Partowはこのアルゴリズムを提案し,よく分布していると主張した.

   public static int aphash(String str) {
      int hash = 0;
      
      for (int i = 0; i < str.length(); i++) {
         if ((i & 1) == 0) {
            hash ^= (hash << 7) ^ (str.charAt(i)) ^ (hash >> 3);
         } else {
            hash ^= ~((hash << 11) ^ (str.charAt(i)) ^ (hash >> 5));
         }
      }
      
      return hash & 0x7FFFFFFF;
   }

JSHash

Justin Sobelが提案したビットベースの関数.

   public static int jshash(String str) {
      int hash = 0;
      
      for (int i = 0; i < str.length(); i++) {
         hash ^= (hash << 5) + (int)str.charAt(i) + (hash >> 2);
      }
      
      return hash & 0x7FFFFFFF;
   }

RSHash

その著者はRobert Sedgwicksである.次のようになります.

   public static int rshash(String str) {
      int hash = 0;
      
      int a = 63689;
      final int b = 378551;
      
      for (int i = 0; i < str.length(); i++) {
         hash = hash * a + (int)str.charAt(i);
         a *= b;
      }
      
      return hash & 0x7FFFFFFF;
   }

SDBMHash

SDBMプロジェクトで使用されるハッシュ関数は,すべてのデータセットに対して良好な分布性があると主張している.

   public static int sdbmhash(String str) {
      int hash = 0;
      
      for (int i = 0; i < str.length(); i++) {
         hash = (int)str.charAt(i) + (hash << 6) + (hash << 16) - hash;
      }
      
      return hash & 0x7FFFFFFF;
   }

PJWHash

Peter J.Weinbergerがそのコンパイラの著作で提出した.

   public static int pjwhash(String str) {
       int BitsInUnignedInt = 32;
       int ThreeQuarters    = 24;
       int OneEighth        = 4;
       int HighBits         = (int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
       int hash             = 0;
       int test             = 0;

       for (int i = 0; i < str.length(); i++) {
           hash = (hash << OneEighth) + (int)str.charAt(i);
           if ((test = hash & HighBits) != 0)
           {
               hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
           }
       }

       return hash & 0x7FFFFFFF;
   }

ELFHash

Unixシステムで広く使用されているハッシュ関数.

   public static int elfhash(String str) {
      int hash = 0;
      int x = 0;
      
      for (int i = 0; i < str.length(); i++) {
         hash = (hash << 4) + (int)str.charAt(i);
         
         if ((x & hash & 0xF0000000L) != 0) {
            hash ^= x >> 24;
            hash &= ~x;
         }
      }
      
      return hash & 0x7FFFFFFF;
   }

DJBHash

Daniel J.Bernsteinはcomp.lang.cメールリストに発表されたのは,これまで比較的効率的なハッシュ関数の一つである.

   public static int djbhash(String str) {
      int hash = 5381;
      
      for (int i = 0; i < str.length(); i++) {
         hash += (hash << 5) + (int)str.charAt(i);
      }
      
      return hash & 0x7FFFFFFF;
   }

DEKHash

Donald E.Knuthが『コンピュータプログラム設計の芸術』で提案したハッシュ関数.

   public static int dekhash(String str) {
      int hash = str.length();
      
      for (int i = 0; i < str.length(); i++) {
         hash = (hash << 5) ^ (hash >> 27) ^ (int)str.charAt(i);
      }
      
      return hash & 0x7FFFFFFF;
   }

BPHash

   public static int bphash(String str) {
      int hash = str.length();
      
      for (int i = 0; i < str.length(); i++) {
         hash = (hash << 7) ^ (int)str.charAt(i);
      }
      
      return hash & 0x7FFFFFFF;
   }   

FNVHash

   public static int fnvhash(String str) {
      int fnvprime = 0x811C9DC5;
      int hash = 0;
      
      for (int i = 0; i < str.length(); i++) {
         hash *= fnvprime;
         hash ^= (int)str.charAt(i);
      }
      
      return hash & 0x7FFFFFFF;
   }

Java String Hashcode

これはJavaの文字列クラスのHashアルゴリズムで、簡単で実用的で効率的です.JDK 6から直接取り出したコード:

   public static int javahash(String str) {
      int hash = 0;
      
      for (int i = 0; i < str.length(); i++) {
         hash = hash * 31 + (int)str.charAt(i);
      }
      
      return hash & 0x7FFFFFFF;
   }   

じっけんとうけい

ネット上で提供されている英語の単語ファイルを使用します.http://www.cs.duke.edu/~ola/ap/linuxwords,合計45402単語を用いて,ハッシュテーブル長が1001000および10000の各アルゴリズムの最大衝突数をそれぞれ比較し,理論的に平均455,46および5であった.結果は次のとおりです.
アルゴリズム#アルゴリズム#
長さ100のハッシュ
長さ1000のハッシュ
長さ10000のハッシュ
bkdrhash
509
72
14
aphash
519
72
15
jshash
494
66
15
rshash
505
74
15
sdbmhash
518
67
15
pjwhash
756
131
34
elfhash
801
158
91
djbhash
512
64
17
dekhash
536
75
22
bphash
1391
696
690
fnvhash
516
65
14
javahash
523
69
16

結論

上記の統計データから,jshash,djbhash,fnvhashはいずれも英語単語セットに対して良好に分散していることが分かる.株式取引システムの実現を開始する前に、比較的包括的な株式コードを取得し、様々なアルゴリズムの性能を詳細に比較し、システムの性能に対する推定を得ることができる.より詳細な分析は、私の独立したブログを参照してください.