一意のハッシュは最大4文字ですか？

Stringのハッシュを作成する最良の方法は、ハッシュが4文字を超えていない可能性があり、4文字が小文字または数字のみである場合です。一意のハッシュは最大4文字ですか？

ハッシュする文字列の長さは1〜255文字です。私は衝突なしで4文字ハッシュとして作成することはおそらく不可能であることを知っています。しかし、可能な衝突が最小限に抑えられる良いハッシュがあれば十分でしょう。 http://introcs.cs.princeton.edu/java/61data/CRC16CCITT.java

public class CRC16CCITT { 

    public static void main(String[] args) { 
     int crc = 0xFFFF;   // initial value 
     int polynomial = 0x1021; // 0001 0000 0010 0001 (0, 5, 12) 

     // byte[] testBytes = "123456789".getBytes("ASCII"); 

     byte[] bytes = args[0].getBytes(); 

     for (byte b : bytes) { 
      for (int i = 0; i < 8; i++) { 
       boolean bit = ((b >> (7-i) & 1) == 1); 
       boolean c15 = ((crc >> 15 & 1) == 1); 
       crc <<= 1; 
       if (c15^bit) crc ^= polynomial; 
      } 
     } 

     crc &= 0xffff; 
     StdOut.println("CRC16-CCITT = " + Integer.toHexString(crc)); 
    } 

}

しかし、これはあまりにも多くの衝突を与える：私が試した何

はこちらからCRC16CCITTです。より良いアルゴリズムはありますか？

出典

2016-11-17 membersound

小文字と数字は、36^4種類のハッシュしかないことを意味します。したがって、一様分布のハッシュを生成するハッシュ関数を使用しても、〜sqrt（36^4）= 1296値（誕生日パラドックスによる）。ハッシュスペースにはもっと多くの値が必要です。 –

これを見て参考になるかもしれません：http://stackoverflow.com/questions/12076846/using-a-larger-prime-as-a-multiplier-when-overrid-hashcode – posdef

@AndyTurner明確化のためにありがとう。とにかく私は4文字に制限されているので、私は設計によって非ユニークなハッシュを持つだろうと知っています。しかし、私は最高の "衝突の可能性が低い"ハッシュを与えるアルゴリズムを探しています。 – membersound

あなたは "文字" を "16進数" を勘違いしている：のみ2バイトだ

int crc = 0xFFFF;   // initial value

（0xFFはわずか1バイトです）。 4 ANSI文字のCRCの場合、4バイト（0xFFFFFFFF）が必要です。
レッグスを2倍にするには、残りのコードを変更する必要があります。その方法を知らなければコメントしてください。

_{PS：これは4バイト未満でも可能ですが、それは必要以上に複雑になります。}

出典

2016-11-17 10:57:25 walen

私はcrcアルゴリズムやバイトエンコーディングに慣れていません。私はちょうど私の質問にリンクされているサンプルクラスを取った。あなたは4 ansi文字に応じて適応アルゴリズムを与えることができれば素晴らしいでしょう。 – membersound

32ビット（4バイト）のバージョンを見てください。「直接計算」の部分は最後です：http://introcs.cs.princeton.edu/java/61data/CRC32.java.html – walen

一意のハッシュは最大4文字ですか？

答えて

関連する問題