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, Dec 13 '14 at 22:48
Check this [topic](http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1) out — But I'm Not A Wrapper Class, Dec 13 '14 at 23:10

score 2 · Answer 1 · edited May 23 '17 at 12:05

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 '17 at 12:05

Community

1
1

answered Dec 13 '14 at 22:57

sol4me

15,233
5
34
34

1

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 Dec 13 '14 at 23:06
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)` – But I'm Not A Wrapper Class Dec 13 '14 at 23:08
@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 – sol4me Dec 13 '14 at 23:14
@CyberneticTwerkGuruOrc Java `HashMap` uses a version of a linked list for allowing multiple items in the same bucket. – Boris the Spider Dec 13 '14 at 23:17
@Vulcan But in order for hash map implementation to achieve it goal it need to relay on some data structure for bucket. OP ask for time-complexity – sol4me Dec 13 '14 at 23:18
1

Worst case complexity only happens if the hash function is degenerate - worth mentioning that. – Boris the Spider Dec 13 '14 at 23:19
@BoristheSpider i thought it is self-evident but thanks for suggesting i updated my answer. Hope it is clear now – sol4me Dec 13 '14 at 23:23
Note: in Java 8 it degenerates into a tree with O(log N) instead of O(N). – Peter Lawrey Dec 13 '14 at 23:27
@PeterLawrey didn't realise they'd changed the impl of `HashMap` in Java 8 - got a reference? Worth a read... – Boris the Spider Dec 13 '14 at 23:28
@BoristheSpider not that I know of, just had a look at the code. Actually if you look at ConcurrentHashMap, it is ~ 3x longer in Java 8 than Java 7. :P – Peter Lawrey Dec 13 '14 at 23:38
@PeterLawrey I think this optimization is described http://openjdk.java.net/jeps/180 as well – sol4me Dec 13 '14 at 23:40
@BoristheSpider for more details http://java.dzone.com/articles/hashmap-performance – sol4me Dec 13 '14 at 23:50

score 2 · Answer 2 · answered Dec 13 '14 at 23:22

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 '14 at 23:22

user207421

305,947
44
307
483

Complexity of java hashmap for hash of string

2 Answers2