怎么可能对Java的HashMap来进行不断的查找时间O（1）＆QUOT;获得＆QUOT;操作？ [英] How is it possible for Java HashMap to perform constant time lookup O(1) for "get" operations?

问题描述

我明白如何HashMap的工作的基础 - hm.put（OBJ）找到正确的桶将对象转换成的基础上，obj.hash code值。然后是内斗，如果另一个对​​象.equals（OBJ），然后取代它，如果不将其添加到桶中。

I understand the basics of how a HashMap works - hm.put(obj) finds the correct bucket to place the object into, based on the obj.hashCode value. Then within that bucket if another object .equals(obj) then replace it, if not add it to the bucket.

但我不清楚HashMap.put和HashMap.get怎么能是恒定的时间为O（1）。据我了解，桶的数量应根据散列codeS，所以把100个对象到一个HashMap将（大致）创建100桶（我明白有时有散列codeS的碰撞，所以它可以是小于100，但不经常）。

But I am unclear on how HashMap.put and HashMap.get can be constant time O(1). As I understand it, the number of buckets should be based on the hashcodes, so putting 100 objects into a hashmap will (roughly) create 100 buckets (I do understand there are sometimes collisions in hashcodes, so it could be less than 100 but not often).

因此​​，作为对象的数量添加到一个HashMap的增长，所以没有桶的数量 - 既然冲突是罕见的话并不意味着该桶的数量几乎呈线性增长与对象的数量增加，其中案例HashMap.put / HashMap.get会为O（n），因为它有每个桶上搜索找到了合适的人之前。

So as the number of objects added to a hashmap grows, so does the number of buckets - and since collisions are rare then doesn't that mean that the number of buckets grows almost linearly with the number of objects added, in which case HashMap.put/HashMap.get would be O(n) as it has to search over every bucket before it finds the right one.

我在想什么？

推荐答案

下面是我的两个美分，朋友。想想一个HashMap的你认为数组的方式。事实上，它是一个数组。如果我给你指数11，你不必通过数组迭代找对象的索引11.你干脆直接去那里。这就是一个HashMap的工作原理：诀窍是让指数一样的价值 - 本质

Here is my two cent, friend. Think of a HashMap the way you think of an array. In fact, it is an array. If I give you index 11, you don't have to iterate through the array to find the object at index 11. You simply go there directly. That's how a HashMap works: the trick is to make the index the same as the value -- essentially.

所以这就是一个散列code进来。让我们来看看在琐碎的情况下，你的哈希函数是一个单位乘数（即1）。然后，如果你有值0到99，你想将它们存储在一个数组，那么他们将被存储在索引0到99分别。这样一放和GET显然是O（1）由于获取和放置的东西在一个数组是O（1）。现在让我们想象一个没有价值的散列函数，说，Y = X + 2。因此，在这种情况下，值0到99将存储在索引2〜101。在此给出的值，比方说11，则必须计算哈希找到它或者把它（散列为11 + 2 = 13）。所以还行，散列函数做了一些工作来计算给定的值正确的索引（在我们的例子Y = X + 2 = 11 + 2 = 13）。但是努力，进入了工作量无关，与多少个数据点你。如果我需要把999或123，工作了一个看跌期权的数量或获得仍然是相同的：Y = X + 2：我只有给每个我认沽或得到的时间增加两个：这是持续的工作。

So that is where a hashcode comes in. Let's look at the trivial case where your hash function is a unit multiplier (i.e. 1). Then if you have the values 0 to 99 and you want to store them in an array, then they will be stored at indices 0 to 99 respectively. So that a put and a get is clearly O(1) since getting and putting things in an array is O(1). Now let's imagine a less trivial hash function, say, y = x+2. So in this case the values 0 to 99 will be stored at indices 2 to 101. Here given a value, say 11, you must compute the hash to find it or put it (the hash being 11+2 =13). So okay, the hash function is doing some work to calculate the correct index given the value (in our case y = x+2= 11+2=13). But the amount of effort that goes into that work has nothing to do with how many data points you have. If I need to put 999 or 123, the amount of work for a single put or get is still the same: y= x+2: I only have to add two each time I do a put or a get: that's constant work.

您的混乱可能是你想要把n个值一次。那么在这种情况下，每个人都戴上仍然是固定 C 。但 C 乘以n是 C *ñ =为O（n）。因此，n具有无关认沽本身，而是你用N投入的一次。我希望这个解释会有所帮助。

Your confusion may be that you want to put n values at once. Well in that case each put is still constant c. But c multiplied by n is c*n=O(n). So the n has nothing to do with the put itself, but rather that you are making n puts all at once. I hope this explanation helps.

这篇关于怎么可能对Java的HashMap来进行不断的查找时间O（1）＆QUOT;获得＆QUOT;操作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！