任意の英数字文字列の int\long 表現を作成する方法を探しています。ハッシュの衝突、つまり表現が一意で反復可能でなければならないという余裕がないため、ハッシュコードはそれを行いません。
数値表現は、効率的な (できれば) 比較を実行するために使用されます。数値キーの作成には時間がかかりますが、それは一度だけ行う必要がありますが、それに対して膨大な数の比較を実行する必要があります。生の文字列を比較するよりもはるかに高速になることを願っています。
より高速な文字列比較に関する他のアイデアも最も高く評価されます...
文字列の長さが制限されていない限り、衝突を避けることはできません。
整数 (2^32) には 4294967296 の可能な値があります。4 つを超える ASCII 文字または 2 つを超える Unicode 文字の文字列がある場合、可能な整数値よりも多くの文字列値が可能です。考えられるすべての 5 文字の文字列に対して一意の整数値を持つことはできません。長い値にはより多くの可能な値がありますが、8 つの ASCII 文字のすべての可能な文字列に対して一意の値しか提供しません。
ハッシュ コードは 2 段階のプロセスとして役立ちます。最初にハッシュ コードが一致するかどうかを確認し、次に文字列全体を確認します。一致しないほとんどの文字列については、最初のステップを実行するだけでよく、非常に高速です。
ハッシュコードから始めて、ハッシュコードが一致する場合は、文字ごとに比較することはできませんか?
弦の長さは？それらが非常に短い場合、文字を基数 36 の数字 (26 + 10) と見なすことで、一意の ID を生成できます。これは、n桁の数値を形成します。ここで、nは文字列の長さです。一方、文字列が十分に短い場合は、直接比較しても問題はありません。
それ以外の場合は、衝突のないハッシュを生成する必要があります。これは、完全な問題空間が事前にわかっている場合 (つまり、発生する可能性のあるすべての文字列がわかっている場合) にのみ実行できます。私が知っている完全なハッシュ関数を見つけるための唯一の実行可能なアルゴリズムは確率論的であるため、理論的には衝突が依然として可能ですが、完全なハッシュを見たいと思うでしょう。
そのような関数を見つける他の方法があるかもしれません。Knuth はこれを TAoCP の「かなり面白い… パズル」と呼びましたが、アルゴリズムも示していません。
一般に、何らかの方法で問題空間全体を調査する必要のないアルゴリズムを見つけるには、情報が少なすぎます。これは常に、問題の実行時間が指数関数的であるが、機械学習ヒューリスティックを使用して解決できることを意味します。これがあなたの場合に望ましいかどうかはわかりません。
多分：
String y = "oiu291981u39u192u3198u389u28u389u";
BigInteger bi = new BigInteger(y, 36);
System.out.println(bi);
結局のところ、1 つの英数字には少なくとも 36 の可能な値があります。句読点や小文字などを含めると、72 個の可能な値を簡単に渡すことができます。
文字列をすばやく比較できる衝突しない数値は、必然的に文字列の長さに応じて指数関数的に大きくなります。
したがって、最初に、比較する予定の最長の文字列を決定する必要があります。長さが N 文字であると仮定し、大文字と数字の 0 ～ 9 のみが必要であると仮定すると、36^N までの整数表現が必要になります。
長さ 25 の文字列 (共通名フィールド) の場合、130 ビットの 2 進数が必要になります。
それを 32 ビットの数値に構成する場合は、4 が必要になります。その後、各数値を比較できます (4 つの整数の比較は、文字列をたどるのに比べて時間がかかりません)。多数のライブラリをお勧めしますが、この特殊なケースでは、独自のライブラリを作成してパフォーマンスを向上させることができると確信しています。
文字ごとに 72 の可能な値 (大文字、小文字、数字、句読点など) を処理する必要があり、10 文字が必要な場合は、62 ビットが必要になります - 2 つの 32 ビット整数 (またはオンの場合は 1 つの 64 ビット) 64 ビット コンピューティングをサポートするシステム)
ただし、文字列内の数字を制限することができず (つまり、256 個の文字/数字/文字/文字などのいずれかである可能性があります)、文字列のサイズを定義できない場合は、文字列を直接比較することは唯一の方法ですが、近道があります。
文字列のポインタを 32 ビットの符号なし整数配列にキャストし、文字列を一度に 4 バイト (または 64 ビット プロセッサでは一度に 64 ビット/8 バイト) 比較します。これは、100 文字の文字列を比較する必要があるのは、最大で 25 回だけであることを意味します。
優先順位の高い文字には 0 に近い値が割り当てられ、優先順位の低い文字には 255 に近い値が割り当てられるように、文字セットを再定義する (および文字列を変換する) 必要がある場合があります (比較方法によっては、その逆も同様です)。 .
幸運を！
-アダム
ハッシュ関数である限り、String.hashCode（）、MD5、SHA1のいずれであっても、文字列の長さに固定の制限がない限り、衝突は避けられません。無限群から有限群への1対1のマッピングを持つことは数学的に不可能です。
一歩下がって、衝突回避は絶対に必要ですか？
最初にいくつかの質問：
私が覚えている限り、Java の String はオブジェクトであり、2 つの同一の文字列が同じオブジェクトを指しています。
したがって、おそらくオブジェクトを比較するだけで十分でしょう (おそらく、文字列比較はこの方法で既に実装されています)。
それが役に立たない場合は、最初の要素が長さのときに文字列オブジェクトの Pascal 実装を使用してみることができます。文字列の長さがさまざまな場合は、CPU 時間を節約できます。
あなたの弦はどのくらいの長さですか？文字列よりも長い int 表現を選択しない限り、使用している変換に関係なく、常に衝突が発生する可能性があります。したがって、32 ビット整数を使用している場合、最大 4 バイトの文字列のみを一意に表すことができます。
あなたの弦はどのくらいの大きさですか？任意の長さの文字列は、32/64 ビット形式に圧縮できません。
衝突したくない場合は、SHA-512 のような非常識なものを試してください。衝突が起こらないとは保証できませんが、まだ見つかっていないと思います。
「英数字」が文字と数字を意味すると仮定すると、各文字/数字を base-36 の数字として扱うことができます。残念ながら、文字列が大きいと数値が急速に大きくなり、大きな整数に頼らざるを得なくなりますが、これはほとんど効率的ではありません。
比較を行うとき (つまり、特定の文字列を検索するとき) に文字列が通常異なる場合は、ハッシュが最適なオプションである可能性があります。潜在的なヒットを取得したら、文字列比較を確実に行うことができます。適切に設計されたハッシュは、衝突を非常にまれにします。
MD5ハッシュは問題なく機能するようです。ハッシュ衝突のリスクはほとんどありません。文字列の長さによっては、int/long を生成するハッシュはすぐに最大値の問題に遭遇します。
1stChar + (10 x 2ndChar) + 100 x (3rdChar) .... のようにして、各文字の単純な整数値、つまり a = 1、b = 2 など、または単に文字でない場合は整数値。これにより、順序が異なる同じ文字の 2 つの文字列であっても、各文字列に一意の値が与えられます。
もちろん、ASCII だけでなく Unicode について心配する必要がある場合はさらに複雑になり、長い文字列を使用する必要がある場合は数値が大きくなる可能性があります。
標準の Java 文字列比較関数は十分に効率的ではありませんか?
文字列の長さは異なる場合がありますが、ここでは 10 文字としましょう。
その場合、一意性を保証するために、ある種の大きな整数表現を使用する必要があります。そもそも文字列比較を行うよりも、大きな整数で比較を行う方が大幅に高速になるとは思えません。ここで他の人が言ったことを2番目に使用し、ある種のハッシュを使用し、ハッシュが一致した場合は元の文字列をチェックして衝突を取り除きます。
いずれにせよ、文字列が約 10 文字の場合、たとえば 32 ビット ハッシュの束を比較すると、文字列を直接比較するよりもはるかに高速になるとは思えません。追加の複雑さに本当に価値があるかどうかを自問する必要があると思います。