Complexity of java hashmap for hash of string

Question

I was looking at java source code in HashMap class.

final int hash(Object k) {
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }

    h ^= k.hashCode();

So, what is the time complexity of hashmapObject.put("somestring") ? Is it O(1) or O(n) where n is number of characters in a string.

Adding something to a HashMap is guaranteed to be O(1) (assuming perfect hash distribution). Your hash function might be O(whatever) though... And your equals... — Boris the Spider
– Boris the Spider, Commented Dec 13, 2014 at 22:48

user207421 · Accepted Answer · 2014-12-13 23:22:41Z

2

It is O(1) w.r.t. the size of the map, which is what is usually of interest. It is O(N) w.r.t. the length of the string.

answered Dec 13, 2014 at 23:22

user207421

312k45 gold badges324 silver badges493 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Community · Accepted Answer · 2017-05-23 12:05:52Z

2

In worst case time(In practise it happens rarely , only when we have a bad hashing function) complexity for put method in hashmap is O(N), because although we add the element at the beginning of the linked list(O(1)) but we still need to loop through the bucket(linked list) to determine if that new element already exists or not.
Updated: As per Peter Lawery comment in java 8 its O(log n). This optimization is described here but in a nutshell an ad-hoc implementation of tree map is used as a bucket when the size of the bucket crosses the threshold value. The threshold value is setted by the variable static final int TREEIFY_THRESHOLD = 8; in HashMap.java

edited May 23, 2017 at 12:05

CommunityBot

11 silver badge

answered Dec 13, 2014 at 22:57

sol4me

15.8k6 gold badges37 silver badges35 bronze badges

12 Comments

But I'm Not A Wrapper Class Over a year ago

Hash map (or hash table) is an associative array. It can be implemented with a linked list, but I don't believe the Java one is. I didn't down vote by the way.

But I'm Not A Wrapper Class Over a year ago

That being said, your answer isn't wrong. Just can be more accurate. You are correct in saying the put function has a worse case scenario of O(n)

sol4me Over a year ago

@CyberneticTwerkGuruOrc The bucket in java is linkedList(not java.util.LinkedList but simpler version). There is also a variable table which is indeed an array that contains object of type linkedList

Boris the Spider Over a year ago

@CyberneticTwerkGuruOrc Java HashMap uses a version of a linked list for allowing multiple items in the same bucket.

Boris the Spider Over a year ago

Worst case complexity only happens if the hash function is degenerate - worth mentioning that.

|

Collectives™ on Stack Overflow

Complexity of java hashmap for hash of string

2 Answers 2

Comments

12 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

12 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related