java - 关于java中的HashMap实现

Question

我试图对 hashmap 进行研究并提出以下分析：

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

Q1 你们可以给我看一个简单的地图，你可以在其中显示过程..如何使用这个公式详细计算给定键的哈希码..计算位置哈希 % (arrayLength-1)) 元素应该放置的位置（桶号），假设我有这个 hashMap

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

Q2 有时可能会发生 2 个不同对象的 hashCode 相同的情况。在这种情况下，2 个对象将保存在一个存储桶中，并将显示为 LinkedList。入口点是最近添加的对象。该对象引用具有下一个字段的其他对象，等等。最后一个条目是指空值。你们能用真实的例子告诉我这个吗..!!

.

“Amit”将被分配到第 10 个桶，因为比特旋转。如果没有一点玩弄，它会转到第 7 个桶，因为 2044535 & 15 = 7。这怎么可能请详细解释整个计算..？

快照已更新...

在此处输入图像描述

另一个图像是......

在此处输入图像描述

score 2 · Accepted Answer

使用此公式如何详细计算给定键的哈希码

在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;
    }

基本上遵循java doc中的等式

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

关于这个实现的一个有趣的事情是它String实际上缓存了它的哈希码。它可以做到这一点，因为String它是不可变的。

如果我计算String“Amit”的哈希码，它将产生这个整数：

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

让我们通过一个简单的 put to a map，但首先我们必须确定地图是如何构建的。关于 Java 最有趣的事实HashMap是它总是有 2^n 个桶。所以如果你调用它，默认的桶数是16，显然是2^4。

在这个map上做put操作，首先会得到key的hashcode。在这个哈希码上发生了一些花哨的比特旋转，以确保糟糕的哈希函数（尤其是那些在低位上没有差异的函数）不会“过载”单个存储桶。

实际负责将密钥分发到存储桶的真正功能如下：

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

这仅适用于两个存储桶大小的幂，因为它使用 & 将密钥映射到存储桶而不是模数。

“Amit”将被分配到第 10 个桶，因为比特旋转。如果没有一点玩弄，它会进入第 7 个桶，因为2044535 & 15 = 7.

现在我们有了它的索引，我们可以找到存储桶。如果桶包含元素，我们必须遍历它们并在找到时替换相等的条目。如果在链表中没有找到任何项目，我们将把它添加到链表的开头。

下一个重要的事情HashMap是调整大小，所以如果地图的实际大小超过阈值（由当前的桶数和负载因子确定，在我们的例子中为 16*0.75=12），它将调整后备数组的大小。调整大小始终为 2 * 当前存储桶数，保证为 2 的幂，以不破坏查找存储桶的功能。

由于桶的数量发生了变化，我们必须重新散列表中的所有当前条目。这是相当昂贵的，所以如果你知道有多少项目，你应该HashMap用那个计数来初始化它，这样它就不必一直调整大小。

score 0 · Accepted Answer

Understand that there are two basic requirements for a hash code:

When the hash code is recalculated for a given object (that has not been changed internally in a way that would alter its identity) it must produce the same value as the previous calculation. Similarly, two "identical" objects must produce the same hash codes.
When the hash code is calculated for two different objects (which are not considered "identical" from the standpoint of their internal content) there should be a high probability that the two hash codes would be different.

How these goals are accomplished is the subject of much interest to the math nerds who work on such things, but understanding the details is not at all important to understanding how hash tables work.

score 0 · Accepted Answer

Q1：查看对象的hashCode()方法实现String

Q2：创建简单的类并将其hashCode()方法实现为return 1. 这意味着具有该类的每个对象都将具有相同的 hashCode，因此将保存在 HashMap 的同一个存储桶中。

score -1 · Accepted Answer

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;
    }

}
}

java - 关于java中的HashMap实现

4 回答 4

Related

Reference