1

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.

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).

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.

What am I missing?

CleanCoder
  • 13
  • 3
  • 2
    possible duplicate of [Is a Java hashmap really O(1)?](http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1) – Haifeng Zhang Mar 06 '15 at 17:15
  • 5
    The whole point of a hash table is that it _doesn't_ need to search every bucket. – SLaks Mar 06 '15 at 17:15
  • Look at a hash map as an array of buckets indexed by the objects' hash-code. That is `O(1)` unless a collision occurs; the bucket gets more items. – Joop Eggen Mar 06 '15 at 17:18
  • Why do you think get() has to search over every bucket ? As you mentioned in your first line, key's hashcode will give the bucket location in the array, so you don't have to search through all buckets. – Arkantos Mar 06 '15 at 18:12

3 Answers3

1

A hash table does not need to search every bucket, just like you don't need to search every shelf on the library, because you can look up it's location in the index cards, and you don't need to search every card in the index because they are sorted... (not sure if that helps as I'm not sure if people still go to libraries or if they still have index cards)

user1133275
  • 2,642
  • 27
  • 31
1

Think of it this way: when you call get(key), the hashcode of the key is calculated and from this the one bucket among hundreds is pointed to in a single (set of) operation(s), i.e. you don't have to search through all 100 to arrive at the right bucket (in which case that would be a linear operation)

GlobalVariable
  • 181
  • 8
1

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.

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.

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.

Konsol Labapen
  • 2,424
  • 2
  • 15
  • 12
  • I think what I am missing is, how does the hashcode give me the exact location in the array? Do the hashcode values literally point to an index of an array in the JVM memory? So: String s = new String("hi"); System.out.println(s.hashCode()); //prints out 97730 So there is an array with index number 97730 out there and the value at that array is the bucket (a List of items in the bucket) where this object would be stored if I put it into a collection? – CleanCoder Mar 06 '15 at 19:18
  • That is exactly correct: the very value of the element is translated to the index needed. A hash function may convert the word "love" to the index 1, the word "pencil" to the index 2, and so on. When a hash function hashes two different words to the same index/address, we call that a collision. For example, if your hash function returns 3 for "book" and 3 for "cars", then that is a collision. Let me know if you have more questions. – Konsol Labapen Mar 07 '15 at 16:38
  • Also notice that it is practically impossible to avoid collisions. So a good hash function, so called "universal hash function", uses double hashing: first you hash to find the index of an object; if you end up with a collision, instead of using a list, you use yet another hashing function to resolve the collision. – Konsol Labapen Mar 07 '15 at 16:41
  • @Konsol Labapen if the hash (which is typically a 32 bit integer) is the index for the array, the array would have the length 2^32. And even if each element had one byte, the total size of the array would be more than 4 GB. But a hashmap does not allocate 4 GB each time. So how does that work? – Lensflare Nov 11 '16 at 10:14