The moose likes Java in General and the fly likes HashMap ContainsKey() method asymptotic analysis Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "HashMap ContainsKey() method asymptotic analysis" Watch "HashMap ContainsKey() method asymptotic analysis" New topic

HashMap ContainsKey() method asymptotic analysis

Vijaykumar Ramalingam

Joined: Mar 03, 2011
Posts: 15
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.

Rob Spoor

Joined: Oct 27, 2005
Posts: 19651

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.

How To Ask Questions How To Answer Questions
Vijaykumar Ramalingam

Joined: Mar 03, 2011
Posts: 15
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?

Campbell Ritchie

Joined: Oct 13, 2005
Posts: 37953
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.
I agree. Here's the link: http://aspose.com/file-tools
subject: HashMap ContainsKey() method asymptotic analysis
Similar Threads
comparing keys of two hashmaps
Enumerated type toString()
Single table / Simple Locking - WeakHashMap vs WeakReferences
How to check duplicates in hashmap
using method with Argument in logic:equals