• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

HashMap ContainsKey() method asymptotic analysis

 
Vijaykumar Ramalingam
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 20671
65
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 50289
80
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic