根据我的理解,我认为:
两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法),则它们具有相同的hashcode。 如果两个对象不相等,那么它们就不能有相同的hashcode
我说的对吗?
如果我没猜错的话,我有以下问题: HashMap在内部使用对象的hashcode。那么,如果两个对象可以具有相同的hashcode,那么HashMap如何跟踪它使用的键呢?
有人能解释一下HashMap内部是如何使用对象的hashcode的吗?
根据我的理解,我认为:
两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法),则它们具有相同的hashcode。 如果两个对象不相等,那么它们就不能有相同的hashcode
我说的对吗?
如果我没猜错的话,我有以下问题: HashMap在内部使用对象的hashcode。那么,如果两个对象可以具有相同的hashcode,那么HashMap如何跟踪它使用的键呢?
有人能解释一下HashMap内部是如何使用对象的hashcode的吗?
当前回答
哈希映射的工作原理是哈希
HashMap get(Key k) method calls hashCode method on the key object and applies returned hashValue to its own static hash function to find a bucket location(backing array) where keys and values are stored in form of a nested class called Entry (Map.Entry) . So you have concluded that from the previous line that Both key and value is stored in the bucket as a form of Entry object . So thinking that Only value is stored in the bucket is not correct and will not give a good impression on the interviewer .
每当我们调用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)
其他回答
hashmap是这样工作的(这有点简化,但它说明了基本机制):
它有许多“桶”,用来存储键值对。每个桶都有一个唯一的编号——用来标识该桶。当您将一个键值对放入映射时,hashmap将查看键的哈希码,并将该对存储在标识符为键的哈希码的bucket中。例如:密钥的哈希码为235 ->,存储在桶号为235的桶中。(注意,一个桶可以存储多个键-值对)。
当您在hashmap中查找一个值时,通过给它一个键,它将首先查看您给出的键的哈希代码。然后,hashmap将查看相应的存储桶,然后它将通过equals()比较您给出的键与存储桶中所有对的键。
现在,您可以看到这对于在map中查找键-值对是多么高效:通过键的哈希代码,哈希映射立即知道要在哪个bucket中查找,因此它只需要测试该bucket中的内容。
看看上面的机制,你也可以看到对键的hashCode()和equals()方法有什么必要的要求:
If two keys are the same (equals() returns true when you compare them), their hashCode() method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it's going to look in the same bucket). If two keys are different, then it doesn't matter if their hash codes are the same or not. They will be stored in the same bucket if their hash codes are the same, and in this case, the hashmap will use equals() to tell them apart.
哈希映射的工作原理是哈希
HashMap get(Key k) method calls hashCode method on the key object and applies returned hashValue to its own static hash function to find a bucket location(backing array) where keys and values are stored in form of a nested class called Entry (Map.Entry) . So you have concluded that from the previous line that Both key and value is stored in the bucket as a form of Entry object . So thinking that Only value is stored in the bucket is not correct and will not give a good impression on the interviewer .
每当我们调用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)
我不会详细介绍HashMap是如何工作的,但是会给出一个例子,这样我们就可以通过将HashMap与现实联系起来来记住它是如何工作的。
我们有Key, Value,HashCode和bucket。
在一段时间内,我们将把它们与以下内容联系起来:
一个社会 HashCode ->社会地址(总是唯一的) 社会中的房子 Key ->房屋地址。
使用Map.get(key):
Stevie想去他的朋友(Josse)的房子,他住在一个VIP社会的别墅里,让它成为javalavers社会。 Josse的地址是他的SSN(每个人都不一样)。 有一个索引,我们可以根据社会安全号找到协会的名字。 这个索引可以被认为是一个找出HashCode的算法。
SSN协会名称 92313(Josse’s) -爪哇 13214—AngularJSLovers 98080—javalover 53808 -生物爱好者
这个SSN(密钥)首先给我们一个HashCode(来自索引表),它只是社会的名字。 现在,多个房子可以在同一个社会中,所以HashCode可以是公共的。 假设,社会对两个房子都是公用的,我们如何识别我们要去哪个房子,是的,通过使用(SSN)密钥,它只是房子的地址
使用Map.put(关键字,值)
这将通过查找HashCode为该值找到一个合适的社会,然后存储该值。
我希望这能有所帮助,而且这是可以修改的。
你可以在http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html上找到很好的信息
总结:
HashMap的工作原理是哈希
put(key, value): HashMap将key和value对象都存储为Map.Entry。Hashmap应用hashcode(key)来获取桶。如果有碰撞,HashMap使用LinkedList存储对象。
get(key): HashMap使用key Object的hashcode来查找桶的位置,然后调用keys.equals()方法来识别LinkedList中的正确节点,并在Java HashMap中返回该键的相关值对象。
hashcode决定要检查hashmap的哪个bucket。如果存储桶中有多个对象,则执行线性搜索以查找存储桶中的哪个项目等于所需的项目(使用equals()方法)。
In other words, if you have a perfect hashcode then hashmap access is constant, you will never have to iterate through a bucket (technically you would also have to have MAX_INT buckets, the Java implementation may share a few hash codes in the same bucket to cut down on space requirements). If you have the worst hashcode (always returns the same number) then your hashmap access becomes linear since you have to search through every item in the map (they're all in the same bucket) to get what you want.
大多数情况下,编写良好的hashcode并不完美,但它足够独特,可以为您提供或多或少的恒定访问。