File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
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
JavaRanch » Java Forums » Java » Java in General
Bookmark "HashMap ContainsKey() method asymptotic analysis" Watch "HashMap ContainsKey() method asymptotic analysis" New topic
Author

HashMap ContainsKey() method asymptotic analysis

Vijaykumar Ramalingam
Greenhorn

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.

Thanks,
-Vijay
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19695
    
  20

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.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Vijaykumar Ramalingam
Greenhorn

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

Joined: Oct 13, 2005
Posts: 38851
    
  23
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