HashMap ContainsKey() method asymptotic analysis

[Vijaykumar Ramalingam]

Hello All,
Could you tell me the analysis of ContainsKey() method in HashMap class.
Are all keys of the HashMap stored in a array and each value is compared if it exists and so is it O(n).
Could you tell me how the keys are stored and how it maps to values and How the operations in hashmap is O(1) time.

Thanks,
-Vijay

[Rob Spoor]

Welcome to the Ranch!

If you check your JDK installation folder, there is a file called "src.zip". Inside you will find the Java source code for most of the core API. HashMap is certainly in there.

With an ideal hashing function the operations would be O(1). However, because of hash conflicts the order is more like O(M) where M is the maximum bucket size. With an ideal hashing function M == 1.

[Vijaykumar Ramalingam]

Rob,
I am trying to understand how the hashbuckets works.

and How hashcode ASCII code works.

How elements are inserted in each of hashbuckets.

Insertion of characters as Key Values in Hashmap is different from insertion of Integer values as keys in Hashmap?

Why different approach is followed for CHaracter and Integer keys?

Thanks,
-Vijay

[Campbell Ritchie]

All the keys and values are inserted as type Object. So there is no difference in handling Integers or Strings as keys. The only difference you would get is in the behaviour of their hashCode methods.