JAva容器の深い理解---mapとハッシュとハッシュコード
4564 ワード
collectionから派生したjavaコンテナについて私のブログは共有しません.似ているので、更新するのは面倒です.私のブログを見ているすべての人は、間違っているところをコメントして指摘してほしいと思っています.今日はmapについてお話ししますが、マッピングテーブル(関連配列)の考え方を理解し、関連配列によってキー値ペアを維持する必要があります.次の例です(現在のjava.utilではmapの実装ではありません).
AssociativeArrayクラスには2つの基本メソッドputとgetがあり,putメソッドにより伝達された値を2次元配列に保存した.値を取るときはgetメソッドで遍歴比較を行い,ある場合は返す.
2.ハッシュとハッシュコード
我々がnewの2つの同じオブジェクトA,Bをシーケンス化すると,オブジェクトには同じ内容がa.equals(b)-->falst.
デフォルトのObject.equals()はオブジェクトのアドレスを比較するだけなのでfalstであり、HashMapのキーとして独自のクラスを使用する場合はhashCode()とequals()を同時にリロードする必要があります.
Set entrySet=map.entrySet();//entrySet()メソッドはmapキー値を反映するマッピング関係を返しset集合に格納する
ハッシュを使用する目的は、あるオブジェクトを使用して別のオブジェクトを検索することです.
map線形クエリーを使用すると非常に遅いクエリーであり、ハッシュを使用するとクエリーの速度が速くなるので、mapに適用するのは素晴らしいでしょう.
ハッシュを使用してキーをどこかに保存し、すぐに見つけることができます.要素のセットを格納する最も速いデータ構造は配列です.キーの情報を配列に保存することができます.配列容量に制限があるため、配列にキー自体を保存させないことができます.キーを押して数字を生成して下付き文字にします.この数字はハッシュコードです.各ハッシュコードはリストを1つ保存し、リストに本当のキーを格納します.すなわち,valueをキーで探す場合,アルゴリズムにより対応するハッシュコードを見つけ,ハッシュコードを介してlistを見つけ,この場合線形クエリにより比較する.線形クエリーもありますが、100個から何を行うか10個から線形クエリーを行う効果は明らかです.さあ、mapへのハッシュの応用を理解して、私たちは自分のmapを実現しましょう.(コードが不完全で、直接実行できない)Map.entrySet()メソッドはMapを生成する必要がある.Entryオブジェクトセット、MapEntryを作成してMapを実装する必要があります.Entryインタフェースでいいです.
これは簡単な自分のmapとjavaです.utilの中のはまだ遠いですが、効果は出ています.
public class AssociativeArray {
private Object[][] pairs;
private int index;
public AssociativeArray(int length){
pairs = new Object[length][2];
}
public void put(K key,V value){
if (index >= pairs.length)
throw new ArrayIndexOutOfBoundsException();
pairs[index++] = new Object[]{key,value};
}
public V get(K key){
for (int i=0;i map = new AssociativeArray(6);
map.put("sky","blue");
map.put("grass","green");
map.put("ocean","dancing");
System.out.println(map);
System.out.println(map.get("ocean"));
}
}
AssociativeArrayクラスには2つの基本メソッドputとgetがあり,putメソッドにより伝達された値を2次元配列に保存した.値を取るときはgetメソッドで遍歴比較を行い,ある場合は返す.
2.ハッシュとハッシュコード
我々がnewの2つの同じオブジェクトA,Bをシーケンス化すると,オブジェクトには同じ内容がa.equals(b)-->falst.
デフォルトのObject.equals()はオブジェクトのアドレスを比較するだけなのでfalstであり、HashMapのキーとして独自のクラスを使用する場合はhashCode()とequals()を同時にリロードする必要があります.
Set entrySet=map.entrySet();//entrySet()メソッドはmapキー値を反映するマッピング関係を返しset集合に格納する
ハッシュを使用する目的は、あるオブジェクトを使用して別のオブジェクトを検索することです.
map線形クエリーを使用すると非常に遅いクエリーであり、ハッシュを使用するとクエリーの速度が速くなるので、mapに適用するのは素晴らしいでしょう.
ハッシュを使用してキーをどこかに保存し、すぐに見つけることができます.要素のセットを格納する最も速いデータ構造は配列です.キーの情報を配列に保存することができます.配列容量に制限があるため、配列にキー自体を保存させないことができます.キーを押して数字を生成して下付き文字にします.この数字はハッシュコードです.各ハッシュコードはリストを1つ保存し、リストに本当のキーを格納します.すなわち,valueをキーで探す場合,アルゴリズムにより対応するハッシュコードを見つけ,ハッシュコードを介してlistを見つけ,この場合線形クエリにより比較する.線形クエリーもありますが、100個から何を行うか10個から線形クエリーを行う効果は明らかです.さあ、mapへのハッシュの応用を理解して、私たちは自分のmapを実現しましょう.(コードが不完全で、直接実行できない)Map.entrySet()メソッドはMapを生成する必要がある.Entryオブジェクトセット、MapEntryを作成してMapを実装する必要があります.Entryインタフェースでいいです.
package a_rongqi.map;
import java.util.*;
public class SimpleHashMap extends AbstractMap {
static final int SIZE = 997;
LinkedList>[] buckets = new LinkedList[SIZE];
public V put(K key,V value){
V oldValue = null;
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null)
buckets[index] = new LinkedList>();
LinkedList> bucket = buckets[index];
MapEntry pair = new MapEntry(key,value);
boolean found = false;
ListIterator> it = bucket.listIterator();
while (it.hasNext()){
MapEntry ipair = it.next();
if (ipair.getKey().equals(key)){
oldValue = ipair.getValue();
it.set(pair);
found = true;
break;
}
}
if (!found)
buckets[index].add(pair);
return oldValue;
}
public V get(Object key){
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null)
return null;
for (MapEntry ipair : buckets[index])
if (ipair.getKey().equals(key))
return ipair.getValue();
return null;
}
@Override
public Set> entrySet() {
Set> set = new HashSet>();
for (LinkedList> bucket : buckets){
if (bucket == null) continue;
for (MapEntry mpair : bucket)
set.add(mpair);
}
return set;
}
public static void main(String[] args) {
Countries c = new Countries();
SimpleHashMap m1 = new SimpleHashMap();
m1.put("1","0");
m1.put("2","1");
m1.put("1","2");
m1.put("4","3");
SimpleHashMap m = new SimpleHashMap();
m.putAll(m1);
System.out.println(m);
System.out.println(m.get("2"));
System.out.println(m.entrySet());
}
}
これは簡単な自分のmapとjavaです.utilの中のはまだ遠いですが、効果は出ています.