5

私はハッシュマップの調査を試みていて、次の分析を思いつきました。

https://stackoverflow.com/questions/11596549/how-does-javas-hashmap-work-internally/18492835#18492835

Q1プロセスを示すことができる簡単なマップを教えてください..この式を使用して、特定のキーのハッシュコードがどのように詳細に計算されるか..要素を配置する場所のハッシュ％（arrayLength-1）を計算する）バケット番号）、このハッシュマップがあるとしましょう

HashMap map=new HashMap();//HashMap key random order.
         map.put("Amit","Java");
         map.put("Saral","J2EE");

Q22つの異なるオブジェクトのhashCodesが同じである場合があります。この場合、2つのオブジェクトが1つのバケットに保存され、LinkedListとして表示されます。エントリポイントは、最近追加されたオブジェクトです。このオブジェクトは、次のフィールドを持つ他のオブジェクトを参照します。最後のエントリはnullを参照しています。実例で見せてくれませんか。

。

「Amit」は、ビットがいじられるため、10番目のバケットに配布されます。2044535＆15 = 7であるため、少し調整がなかった場合は7番目のバケットに移動します。これがどのように可能であるかを計算全体の詳細を説明してください。

スナップショットが更新されました...

ここに画像の説明を入力してください

そして他の画像は...

ここに画像の説明を入力してください

4

4 に答える 4

2

この式を使用して、特定のキーのハッシュコードがどのように詳細に計算されるか

これの場合、次のように実装されてString計算さ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;
    }

基本的に、JavaDocの式に従います。

 hashcode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

この実装で注目すべき興味深い点の1つは、String実際にハッシュコードをキャッシュすることです。Stringは不変であるため、これを行うことができます。

String「Amit」のハッシュコードを計算すると、次の整数になります。

System.out.println("Amit".hashCode());
>     2044535

マップへの簡単な配置を見てみましょうが、最初にマップがどのように作成されるかを決定する必要があります。Javaの最も興味深い事実は、JavaHashMapには常に2^n個のバケットがあるということです。したがって、これを呼び出すと、バケットのデフォルト数は16であり、明らかに2^4です。

このマップでput操作を実行すると、最初にキーのハッシュコードが取得されます。貧弱なハッシュ関数（特に下位ビットが異ならないもの）が単一のバケットを「オーバーロード」しないようにするために、このハッシュコードでいくつかの凝ったビットの調整が行われます。

キーをバケットに配布する実際の機能は次のとおりです。

 h & (length-1); // length is the current number of buckets, h the hashcode of the key

これは、モジュロではなく＆を使用してキーをバケットにマップするため、2つのバケットサイズの累乗に対してのみ機能します。

「Amit」は、ビットがいじられるため、10番目のバケットに配布されます。少し調整がなければ、7番目のバケットに移動し2044535 & 15 = 7ます。

インデックスができたので、バケットを見つけることができます。バケットに要素が含まれている場合は、それらを繰り返し処理し、見つかった場合は等しいエントリを置き換える必要があります。リンクリストにアイテムが見つからない場合は、リンクリストの先頭に追加します。

次に重要なのHashMapはサイズ変更です。したがって、マップの実際のサイズがしきい値（現在のバケット数と負荷率によって決定されます。この場合は16 * 0.75 = 12）を超えると、バッキング配列のサイズが変更されます。サイズ変更は常に2*現在のバケット数です。これは、バケットを見つける機能を壊さないように2の累乗であることが保証されています。

バケットの数が変わるため、テーブル内の現在のすべてのエントリを再ハッシュする必要があります。これは非常にコストがかかるため、アイテムの数がわかっている場合は、HashMapそのカウントで初期化して、全体のサイズを変更する必要がないようにする必要があります。

于 2012-08-04T19:07:40.673 に答える
0

Q1：オブジェクトのhashCode()メソッド実装を見てくださいString

Q2：単純なクラスを作成し、そのhashCode()メソッドをとして実装しreturn 1ます。つまり、そのクラスを持つ各オブジェクトは同じhashCodeを持つため、HashMapの同じバケットに保存されます。

于 2012-08-04T18:11:59.757 に答える
0

ハッシュコードには2つの基本的な要件があることを理解してください。

  1. ハッシュコードが特定のオブジェクト（そのIDを変更するような方法で内部的に変更されていない）に対して再計算される場合、前の計算と同じ値を生成する必要があります。同様に、2つの「同一の」オブジェクトは同じハッシュコードを生成する必要があります。
  2. ハッシュコードが2つの異なるオブジェクト（内部コンテンツの観点から「同一」とは見なされない）に対して計算される場合、2つのハッシュコードが異なる可能性が高いはずです。

これらの目標がどのように達成されるかは、そのようなことに取り組む数学オタクにとって非常に興味深い主題ですが、詳細を理解することは、ハッシュテーブルがどのように機能するかを理解するためにまったく重要ではありません。

于 2012-08-04T19:22:33.810 に答える
-1 
import java.util.Arrays;
public class Test2 {
public static void main(String[] args) {
    Map<Integer, String> map = new Map<Integer, String>();
    map.put(1, "A");
    map.put(2, "B");
    map.put(3, "C");
    map.put(4, "D");
    map.put(5, "E");

    System.out.println("Iterate");
    for (int i = 0; i < map.size(); i++) {

        System.out.println(map.values()[i].getKey() + " : " + map.values()[i].getValue());
    }

    System.out.println("Get-> 3");
    System.out.println(map.get(3));

    System.out.println("Delete-> 3");
    map.delete(3);

    System.out.println("Iterate again");
    for (int i = 0; i < map.size(); i++) {

        System.out.println(map.values()[i].getKey() + " : " + map.values()[i].getValue());
    }
}

}

class Map<K, V> {

private int size;
private Entry<K, V>[] entries = new Entry[16];

public void put(K key, V value) {

    boolean flag = true;
    for (int i = 0; i < size; i++) {

        if (entries[i].getKey().equals(key)) {
            entries[i].setValue(value);
            flag = false;
            break;
        }
    }

    if (flag) {
        this.ensureCapacity();
        entries[size++] = new Entry<K, V>(key, value);
    }
}

public V get(K key) {

    V value = null;

    for (int i = 0; i < size; i++) {

        if (entries[i].getKey().equals(key)) {
            value = entries[i].getValue();
            break;
        }
    }
    return value;
}

public boolean delete(K key) {
    boolean flag = false;
    Entry<K, V>[] entry = new Entry[size];
    int j = 0;
    int total = size;
    for (int i = 0; i < total; i++) {

        if (!entries[i].getKey().equals(key)) {
            entry[j++] = entries[i];
        } else {
            flag = true;
            size--;
        }
    }

    entries = flag ? entry : entries;
    return flag;
}

public int size() {
    return size;
}

public Entry<K, V>[] values() {
    return entries;
}

private void ensureCapacity() {

    if (size == entries.length) {
        entries = Arrays.copyOf(entries, size * 2);
    }
}

@SuppressWarnings("hiding")
public class Entry<K, V> {

    private K key;
    private V value;

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Entry(K key, V value) {
        super();
        this.key = key;
        this.value = value;
    }

}
}
于 2017-12-12T16:09:40.303 に答える