hashcodeに31係数が使われている問題について
2608 ワード
hashcodeの中で31のこの係数を使うことについての研究
まず、hashcodeとは何ですか?何の効果がありますか
hashcodeはハッシュコードであり、hashcodeは高い効率のハッシュアルゴリズムを使用して検索対象を特定する.
私たちは容器を使ってデータを格納する時、一連のハッシュコードを計算して、データを容器に入れます.
例えば、Stering s="java"では、コンピュータはハッシュコードを先に計算して、それから対応する配列の中に入れます.配列のインデックスはハッシュから計算されますか?そして、Listのような配列の容器に入れます.これは、あなたが保存したいデータをいくつかの大きな部分に分けて、それぞれの部分に多くの値を保存しています.検索する時に、先に大きな部分を調べてください.大きな部分で小さいのを調べたら、先に調べたよりずっと早いです.
オブジェクトのHashCodeは簡単なHashアルゴリズムの実装ですが、それらは本当に複雑です!Hashアルゴリズムは本物のアルゴリズムとは言えませんが、どうやってそれを実現するかは、プログラマのプログラミングレベルの問題だけではなく、あなたのオブジェクトのアクセス時のパフォーマンスに関係する非常に重要な問題です.
java Stringは、このタイプのインスタンスオブジェクトを印刷するとき、常に以下のように表示されます. test.Test$tt@c17164
上のtest.Testは類名です.ttは自分で書いた部類ですが、@の後の部分は何ですか?彼は実はttという実例類のhashcodeは16進制です.
Objectの中のtoString()の方法を使いました.
引き続きjavaのString hashcodeのソースコードを見てください.
コンピュータの乗算はシフト計算に関連することが知られています.一つの数に2をかけると、その数をそのまま持って左に1桁だけ移動すればいいです.31を選んだ理由は31が素数なので!
素数とは:
素数は素数とも呼ばれる.1より大きい自然数のうち、1とこの整数自体を除いて、他の自然数によって割り切れない数を指す.
素数は使う時に一つの効果があります.もしこの素数を一つの数字で掛けたら、最終的に出てきた結果は素数そのものと乗数のあと1で割り切れます.例えば、素数3を係数として選択すると、3*nは3とnまたは1で割り算され、このnは3 nで簡単に計算できます.これも一つの原因です.
データを格納してhashアドレスを計算する時、私達はできるだけ同じhash住所があることを減らしたいです.いわゆる「衝突」です.同じhashアドレスのデータを使いすぎると、これらのデータからなるhashチェーンが長くなり、クエリの効率が低下します.したがって、係数を選択する際には、できるだけ長い係数を選択し、できるだけオーバーフローしないように乗算する必要があります.算出されたhashアドレスが大きいほど、いわゆる「衝突」は少なくなり、検索効率も高くなります.
!
31は、i*31=(\<5)-1によって表されることができ、現在、多くの仮想マシンの中で、関連した最適化が行われています.使用31の原因は、hashアドレスをより良い分配するためかもしれません.31は5 bittsだけを占めています.
java乗算では、大会が数字を掛け合わせた場合、オーバーフローの問題が発生し、データが失われます.
31は素数(素数)であり、長くない数字であり、最終的には相乗係数として選択される理由はこれに過ぎない.
参考文献:http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
http://www.cogs.susx.ac.uk/courses/dats/notes/html/node114.html
引き続き検討します.>>
まず、hashcodeとは何ですか?何の効果がありますか
hashcodeはハッシュコードであり、hashcodeは高い効率のハッシュアルゴリズムを使用して検索対象を特定する.
私たちは容器を使ってデータを格納する時、一連のハッシュコードを計算して、データを容器に入れます.
例えば、Stering s="java"では、コンピュータはハッシュコードを先に計算して、それから対応する配列の中に入れます.配列のインデックスはハッシュから計算されますか?そして、Listのような配列の容器に入れます.これは、あなたが保存したいデータをいくつかの大きな部分に分けて、それぞれの部分に多くの値を保存しています.検索する時に、先に大きな部分を調べてください.大きな部分で小さいのを調べたら、先に調べたよりずっと早いです.
オブジェクトのHashCodeは簡単なHashアルゴリズムの実装ですが、それらは本当に複雑です!Hashアルゴリズムは本物のアルゴリズムとは言えませんが、どうやってそれを実現するかは、プログラマのプログラミングレベルの問題だけではなく、あなたのオブジェクトのアクセス時のパフォーマンスに関係する非常に重要な問題です.
java Stringは、このタイプのインスタンスオブジェクトを印刷するとき、常に以下のように表示されます. test.Test$tt@c17164
上のtest.Testは類名です.ttは自分で書いた部類ですが、@の後の部分は何ですか?彼は実はttという実例類のhashcodeは16進制です.
Objectの中のtoString()の方法を使いました.
return getClass().getName() + "@" + Integer.toHexString(hashCode());
引き続きjavaのString hashcodeのソースコードを見てください.
public int hashCode() {
int h = hash;
int len = count;
if (h == 0 && len > 0) {
int off = offset;
char val[] = value;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
実は上の実現は数学の中です.s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
の実現!私達はその犬の血の31のこの係数に注意します.どうしていつも中で乗りますか?なぜ32または他の数字が適用されないですか?コンピュータの乗算はシフト計算に関連することが知られています.一つの数に2をかけると、その数をそのまま持って左に1桁だけ移動すればいいです.31を選んだ理由は31が素数なので!
素数とは:
素数は素数とも呼ばれる.1より大きい自然数のうち、1とこの整数自体を除いて、他の自然数によって割り切れない数を指す.
素数は使う時に一つの効果があります.もしこの素数を一つの数字で掛けたら、最終的に出てきた結果は素数そのものと乗数のあと1で割り切れます.例えば、素数3を係数として選択すると、3*nは3とnまたは1で割り算され、このnは3 nで簡単に計算できます.これも一つの原因です.
データを格納してhashアドレスを計算する時、私達はできるだけ同じhash住所があることを減らしたいです.いわゆる「衝突」です.同じhashアドレスのデータを使いすぎると、これらのデータからなるhashチェーンが長くなり、クエリの効率が低下します.したがって、係数を選択する際には、できるだけ長い係数を選択し、できるだけオーバーフローしないように乗算する必要があります.算出されたhashアドレスが大きいほど、いわゆる「衝突」は少なくなり、検索効率も高くなります.
!
31は、i*31=(\<5)-1によって表されることができ、現在、多くの仮想マシンの中で、関連した最適化が行われています.使用31の原因は、hashアドレスをより良い分配するためかもしれません.31は5 bittsだけを占めています.
java乗算では、大会が数字を掛け合わせた場合、オーバーフローの問題が発生し、データが失われます.
31は素数(素数)であり、長くない数字であり、最終的には相乗係数として選択される理由はこれに過ぎない.
参考文献:http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
http://www.cogs.susx.ac.uk/courses/dats/notes/html/node114.html
引き続き検討します.>>