Btukfyl

Suppose we have two different hashMaps, say map1 and map2.

• map1 has 1000 entries with 1000 buckets.


• map2 has 999999 entries with 999999 buckets.

And suppose, we have an object "obj1" with hashCode "1234" and we put this object as a key in both map1 and map2(with value "xyz").

Will it require more time to find "obj1" value in map2?
Will the time complexity be still O(1) for accessing obj1 from both map1 and map2?

Finding the bucket is O(1) in a HashMap, always, independent of the capacity (number of buckets).

Let's say your obj1 has a hash code of 1234567. The core of a HashMap is not to search for the correct bucket (as a TreeMap would do), but to compute its position, and immediately access the bucket with that number. That's where the hash code comes into the game.

The computation is obj.hashCode() % capacity, and the resulting number gives the index into the bucketsArray.

• For the small hash map, it's 1234567 % 1000 = 567, meaning that the relevant bucket is bucketsArray[567].




• For the big one, it's 1234567 % 999999 = 234568, resulting in bucketsArray[234568].

The time necessary for computing the division rest is constant, independent of the values. The time for accessing an array with a given index is constant as well, so it's O(1).

We have only talked about finding the bucket. If the bucket contains multiple entries, a linear search completes the hash map access, and that's O(K) with K being the (average? maximum?) number of entries in a bucket.

I thin it would be best to answer with a code and diagram. We all know what hashing (one way) function is it is. Basically it takes arbitrary input and returns number (in java it is int but that is not always the case). And int in java has 32 bits. That means that it can be between -2,147,483,648 and 2,147,483,647. Every object on every java heep that exist can calculate it's hash (using method from java.util.Object class) and it has to be in that interval.

Now let's assume that we have 3 objects.

21234 = obj1.hashCode();  

623424 = obj2.hashCode();

23124432 = obj3.hasCode();

and we want to add them to a hashMap that has 200 buckets. (this is not a working java code i typed it here)

public class MyHashMap {

    private final Buckets buckets = new Buckets[200];



    public boolean add(Object object){

        int resultModulo = object.hashCode() % 200;

        buckets[buckets].add(object);

    } 

}

Now for the final peace. For our object the resultModulo will be 34(21234), 24(623424), 32(23124432). And the calculate number will not exceed 200.

Array is allocated as a continuous piece of memory. Just array of pointers(64-bits) not the actual objects. So the bucktes looks something like that

0xB80000xB80020xB80670xC1101 ....

1      2      3      4       .... 200

and so when your code invokes bucket[34],bucket[24],bucket[32] what the hardware does is this:

  mov eax, bucktes[ecx*19] 

  ; eax now contains the pointer to the

  ; 19 element in the array

  ; this is a one clock instruction

So that is why it doesn't matter how many bucket you have.