Java HashMap如何使用相同的散列代码处理不同的对象?

hashcode决定要检查hashmap的哪个bucket。如果存储桶中有多个对象，则执行线性搜索以查找存储桶中的哪个项目等于所需的项目(使用equals()方法)。

换句话说，如果你有一个完美的哈希码，那么哈希映射访问是恒定的，你将永远不需要迭代一个桶(技术上你也必须有MAX_INT桶，Java实现可以在同一个桶中共享一些哈希码，以减少空间需求)。如果您有最差的hashcode(总是返回相同的数字)，那么您的hashmap访问就变成线性的，因为您必须搜索映射中的每一项(它们都在同一个bucket中)以获得您想要的内容。

大多数情况下，编写良好的hashcode并不完美，但它足够独特，可以为您提供或多或少的恒定访问。

你的第三个断言是不正确的。

两个不相等的对象拥有相同的哈希码是完全合法的。它被HashMap用作“首通过滤器”，以便映射可以快速找到具有指定键的可能的项。然后测试具有相同哈希码的键是否与指定的键相等。

你不希望要求两个不相等的对象不能有相同的哈希码，否则会限制你只有2³²个可能的对象。(这也意味着不同类型甚至不能使用对象的字段来生成哈希码，因为其他类可以生成相同的哈希码。)

你在第三点上错了。两个条目可以具有相同的哈希码，但不相等。看一下HashMap。从OpenJdk中获取的实现。你可以看到它检查哈希值是否相等键值是否相等。如果第三点成立，那么检查键值是否相等就没有必要了。哈希码在键之前进行比较，因为前者是更有效的比较。

如果你有兴趣了解更多这方面的知识，可以看看维基百科上关于开放寻址冲突解决的文章，我相信这是OpenJdk实现使用的机制。这种机制与另一个答案中提到的“桶”方法略有不同。

hashmap是这样工作的(这有点简化，但它说明了基本机制):

它有许多“桶”，用来存储键值对。每个桶都有一个唯一的编号——用来标识该桶。当您将一个键值对放入映射时，hashmap将查看键的哈希码，并将该对存储在标识符为键的哈希码的bucket中。例如:密钥的哈希码为235 ->，存储在桶号为235的桶中。(注意，一个桶可以存储多个键-值对)。

当您在hashmap中查找一个值时，通过给它一个键，它将首先查看您给出的键的哈希代码。然后，hashmap将查看相应的存储桶，然后它将通过与equals()比较，将您给出的键与存储桶中所有对的键进行比较。

现在，您可以看到这对于在map中查找键-值对是多么高效:通过键的哈希代码，哈希映射立即知道要在哪个bucket中查找，因此它只需要测试该bucket中的内容。

看看上面的机制，你也可以看到对键的hashCode()和equals()方法有什么必要的要求:

• 如果两个键相同(比较它们时equals()返回true)，它们的hashCode()方法必须返回相同的数字。如果键违反了这一点，那么相等的键可能存储在不同的存储桶中，hashmap将无法找到键-值对(因为它将在同一个存储桶中查找)。

• 如果两个键不同，那么它们的哈希码是否相同并不重要。如果它们的哈希码相同，它们将被存储在同一个存储桶中，在这种情况下，哈希映射将使用equals()来区分它们。

你可以在http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html找到很好的信息

总结:

HashMap的工作原理是哈希

put(关键字,值): HashMap将键和值对象都存储为Map.Entry。Hashmap应用hashcode(key)来获取桶。如果有碰撞，HashMap使用LinkedList存储对象。

得到(重要): HashMap使用Key Object的hashcode来查找桶的位置，然后调用keys.equals()方法来识别LinkedList中的正确节点，并在Java HashMap中为该键返回相关的值对象。

HashMap是Entry对象的数组。

将HashMap视为一个对象数组。

看看这个Object是什么:

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
…
}

每个Entry对象表示一个键值对。如果一个桶有多个Entry，则字段next指向另一个Entry对象。

当你用默认构造函数创建HashMap时

HashMap hashMap = new HashMap();

数组的大小为16，默认负载平衡为0.75。

添加新的键-值对

1. 计算键的hashcode
2. 计算元素应该放置的位置hash % (arrayLength-1)(桶号)
3. 如果你试图用一个已经保存在HashMap中的键添加一个值，那么值将被覆盖。
4. 否则元素被添加到桶中。

如果存储桶已经有至少一个元素，则添加一个新元素并将其放置在存储桶的第一个位置。它的next字段指向旧元素。

删除

1. 计算给定键的hashcode
2. 计算桶号hash % (arrayLength-1)
3. 获取桶中第一个Entry对象的引用，并通过equals方法遍历给定桶中的所有条目。最终我们将找到正确的Entry。 如果没有找到所需的元素，则返回null

import java.util.HashMap;


public class Students  {
String name;
int age;


Students(String name, int age ){
this.name = name;
this.age=age;
}


@Override
public int hashCode() {
System.out.println("__hash__");
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}


@Override
public boolean equals(Object obj) {
System.out.println("__eq__");
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Students other = (Students) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}


public static void main(String[] args) {


Students S1 = new Students("taj",22);
Students S2 = new Students("taj",21);


System.out.println(S1.hashCode());
System.out.println(S2.hashCode());


HashMap<Students,String > HM = new HashMap<Students,String > ();
HM.put(S1, "tajinder");
HM.put(S2, "tajinder");
System.out.println(HM.size());
}
}


Output:


__ hash __


116232


__ hash __


116201


__ hash __


__ hash __


2

因此，在这里我们可以看到，如果对象S1和S2都有不同的内容，那么我们可以非常确定，我们覆盖的Hashcode方法将为两个对象生成不同的Hashcode(116232,11601)。因为有不同的哈希码，所以它甚至不需要调用EQUALS方法。因为不同的Hashcode保证对象中不同的内容。

    public static void main(String[] args) {


Students S1 = new Students("taj",21);
Students S2 = new Students("taj",21);


System.out.println(S1.hashCode());
System.out.println(S2.hashCode());


HashMap<Students,String > HM = new HashMap<Students,String > ();
HM.put(S1, "tajinder");
HM.put(S2, "tajinder");
System.out.println(HM.size());
}
}


Now lets change out main method a little bit. Output after this change is


__ hash __


116201


__ hash __


116201


__ hash __


__ hash __


__ eq __


1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally  calls Equal method to verify this.




Conclusion
If hashcode is different , equal method will not get called.
if hashcode is same, equal method will get called.


Thanks , hope it helps.

下面是HashMap机制的粗略描述，对于Java 8版本，(它可能与Java 6略有不同)。

数据结构

<李> 哈希表 < br > 哈希值通过key上的hash()计算，并决定对于给定的key使用哈希表的哪个桶 <李> 链表 (单独) < br > 当桶中的元素数量较小时，使用单链表 <李> 红黑树 < br > 当桶中的元素数量较大时，使用红黑树

类(内部)

<李> Map.Entry < br > 在map中表示单个实体，即键/值实体 <李> < p > HashMap.Node < br >

它可以表示:

• 哈希桶 因为它有哈希属性
• 单链表中的一个节点，(因此也是linkedlist的头)。
李< / ul > < / > <李> HashMap.TreeNode < br >

---

字段(内部)

<李> Node[] table < br > 桶表(链表的头)。
如果桶不包含元素，则桶为空，因此只占用引用的空间 <李> Set<Map.Entry> entrySet <李> int size < br > .实体个数 <李> float loadFactor < br > 在调整大小之前，指示允许的哈希表有多满 <李> int threshold < br > 下一个要调整大小的大小 李公式:threshold = capacity * loadFactor < / >

---

方法(内部)

<李> int hash(key) < br > 如何将哈希映射到桶?< br > 使用以下逻辑:

static int hashToBucket(int tableSize, int hash) {
return (tableSize - 1) & hash;
}

李< /引用> < / >

---

关于能力

在哈希表中，容量是指桶数，可以从table.length中获取 Also可以通过threshold和loadFactor计算，因此不需要定义为类字段

可以通过:capacity()获得有效容量

---

操作

• 按键查找实体 首先通过哈希值找到桶，然后循环链表或搜索排序树
• 添加带有键的实体 首先根据key的哈希值找到桶 然后试着找出它的值:
  • 如果找到，则替换该值。
  • 否则，在链表的开头添加一个新节点，或插入到排序树中。
  李< / ul > < / > <李>调整< br > 当threshold达到时，将哈希表的容量加倍(table.length)，然后对所有元素重新哈希以重建表 这可能是一个昂贵的操作。

  ---

  性能

  <李>得到,把< br > 时间复杂度为O(1)，因为:
  • 桶通过数组索引访问，因此O(1)。
  • 每个bucket中的链表长度较小，因此可以视为O(1)。
  • 树的大小也是有限的，因为会扩展容量&当元素数增加时重新哈希，因此可以将其视为O(1)，而不是O(log N)。
  李< / ul > < / >

哈希映射的工作原理是哈希

HashMap get(Key k)方法调用Key对象上的hashCode方法，并将返回的hashValue应用于它自己的静态哈希函数，以查找bucket位置(后台数组)，其中键和值以称为Entry (Map.Entry)的嵌套类的形式存储。因此，您已经从前面的行中得出结论，key和value都以Entry对象的形式存储在bucket中。所以认为只有价值存储在桶里是不正确的，也不会给面试官留下好印象。

• 每当我们调用HashMap对象上的get(Key k)方法时。首先，它检查key是否为空。注意，HashMap中只能有一个空键。

如果key为null，则null键总是映射到哈希0，因此索引为0。

如果key不为空，那么它将在key对象上调用hashfunction，参见上述方法中的第4行，即key. hashcode()，因此在key. hashcode()返回hashValue之后，第4行如下所示

            int hash = hash(hashValue)

现在，它将返回的hashValue应用到自己的哈希函数中。

我们可能想知道为什么要再次使用hash(hashvalue)计算哈希值。答案是它可以防御低质量的哈希函数。

现在使用final hashvalue来查找存储Entry对象的bucket位置。条目对象像这样存储在桶中(哈希，键，值，bucketindex)

每个Entry对象表示键值对。如果一个桶有多于1个Entry，则字段next指向其他Entry对象。

数组的大小为16，默认负载平衡为0.75。

(来源)

我不会详细介绍HashMap是如何工作的，但是会给出一个例子，这样我们就可以通过将HashMap与现实联系起来来记住它是如何工作的。

我们有Key, Value,HashCode和bucket。

在一段时间内，我们将把它们与以下内容联系起来:

• 一个社会
• HashCode ->社会地址(总是唯一的)
• 社会中的房子
• Key ->房屋地址。

使用Map.get(key):

• SSN协会名称
• 92313(Josse’s) -爪哇
• 13214—AngularJSLovers
• 98080—javalover
• 53808 -生物爱好者

1. 这个SSN(密钥)首先给我们一个HashCode(来自索引表)，它只是社会的名字。
2. 现在，多个房子可以在同一个社会中，所以HashCode可以是公共的。
3. 假设，社会对两个房子都是公用的，我们如何识别我们要去哪个房子，是的，通过使用(SSN)密钥，它只是房子的地址

使用Map.put(关键字,值)

这将通过查找HashCode为该值找到一个合适的社会，然后存储该值。

我希望这能有所帮助，而且这是可以修改的。

这将是一个很长的答案，拿着饮料继续阅读…

哈希就是在内存中存储一个键-值对，可以更快地读写。它将键存储在数组中，值存储在LinkedList中。

假设我想存储4个键值对

{
“girl” => “ahhan” ,
“misused” => “Manmohan Singh” ,
“horsemints” => “guess what”,
“no” => “way”
}

为了存储键，我们需要一个4元素的数组。现在我如何将这4个键中的一个映射到4个数组索引(0,1,2,3)呢?

1) reverse the string.


2) keep on multiplying ascii of each character with increasing power of 31 . then add the components .


3) So hashCode() of girl would be –(ascii values of  l,r,i,g are 108, 114, 105 and 103) .


e.g. girl =  108 * 31^0  + 114 * 31^1  + 105 * 31^2 + 103 * 31^3  = 3173020

哈希和女孩!!我知道你在想什么。你对狂野二重唱的迷恋可能会让你错过一件重要的事情。

为什么java用31乘以它

Array Index 0 –
Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”)
Array Index 2 – LinkedList (“way”)
Array Index 3 –

Array Index 0 –
Array Index 1 - LinkedIst (<”girl” => “ahhan”> , <” misused” => “Manmohan Singh”> , <”horsemints” => “guess what”>)
Array Index 2 – LinkedList (<”no” => “way”>)
Array Index 3 –