HashMap map=new HashMap();//HashMap key random order.
map.put("Amit","Java");
map.put("Saral","J2EE");
关于Java中HashMap的实现
5
- DON
3
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;
}
hashcode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
需要注意的是，这个实现中有一个有趣的事情，那就是String实际上缓存了它的哈希码。它可以这样做，因为String是不可变的。
如果我计算字符串"Amit"的哈希码，它将会得到这个整数：
System.out.println("Amit".hashCode());
> 2044535
让我们先了解一下简单的将数据放入 map 中的过程，但首先我们必须确定 map 是如何构建的。关于 Java HashMap 最有趣的事实是它总是具有 2^n 个桶。因此，如果你调用它，默认桶的数量为 16，这显然是 2^4。
对这个 map 进行 put 操作时，它首先会获取 key 的哈希码。对这个哈希码进行了一些奇怪的位运算操作，以确保贫弱的哈希函数（特别是那些在低位上没有区别的哈希函数）不会“超载”一个单独的桶。
真正负责将您的键分配到桶中的函数如下：
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倍，这保证了是二的幂次方，以不破坏查找桶的功能。
由于桶数改变，我们必须重新散列表中所有当前条目。这非常耗费时间，因此，如果您知道有多少项，请使用该计数初始化HashMap，这样它就不必一直调整大小。
- Thomas Jungblut
3
很好的解释，但还有一件事情不太清楚，那就是2044535和15 = 7。您能详细解释一下它是如何得出7的吗？ - DON
有一件令人困惑的事情是，根据我在帖子中更新的快照，amit被存储在10个桶中，请解释一下到达第10个桶的详细公式。 - DON
0
问题1：查看String对象的hashCode()方法实现
问题2：创建一个简单的类，并将其hashCode()方法实现为return 1。这意味着您使用该类创建的每个对象都将具有相同的hashCode，因此将保存在HashMap中的同一桶中。
- mishadoff
0
理解哈希码的两个基本要求：
- 当为给定对象重新计算哈希码（未在其内部更改以改变其标识的方式）时，它必须生成与先前计算相同的值。同样，两个“相同”的对象必须生成相同的哈希码。
- 当为两个不同的对象（从其内部内容的角度来看不被认为是“相同”的）计算哈希码时，这两个哈希码应该有很高的概率是不同的。
如何实现这些目标是数学专家们感兴趣的主题，但了解细节对于了解哈希表的工作原理并不重要。
- Hot Licks
-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;
}
}
}
- It's Rammy
1
3欢迎来到 Stack Overflow！请不要仅仅发布代码：解释一下它的作用，这样你的回答就能对更多人有价值。 - Vincent
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
java.util.HashMap的确切行为，为什么不阅读其源代码呢？或者在调试器中逐步执行它的方法呢？ - meriton