188

I've seen some interesting claims on SO re Java hashmaps and their O(1) lookup time. Can someone explain why this is so? Unless these hashmaps are vastly different from any of the hashing algorithms I was bought up on, there must always exist a dataset that contains collisions.

In which case, the lookup would be O(n) rather than O(1).

Can someone explain whether they are O(1) and, if so, how they achieve this?

Stephen Niedzielski
  • 2,497
  • 1
  • 28
  • 34
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • 32
    Big O notation gives an upper bound for the particular type of analysis you are doing. You should still specify whether you are interested in worst-case, average case, etc. – Dan Homerick Jun 28 '09 at 17:18
  • 2
    I know this might not be an answer but I remember Wikipedia has a [very good article](http://en.wikipedia.org/wiki/Hash_table) about this. Don't miss the [performance analysis](http://en.wikipedia.org/wiki/Hash_table#Performance_analysis) section – victor hugo Jun 28 '09 at 16:56

15 Answers15

147

A particular feature of a HashMap is that unlike, say, balanced trees, its behavior is probabilistic. In these cases its usually most helpful to talk about complexity in terms of the probability of a worst-case event occurring would be. For a hash map, that of course is the case of a collision with respect to how full the map happens to be. A collision is pretty easy to estimate.

pcollision = n / capacity

So a hash map with even a modest number of elements is pretty likely to experience at least one collision. Big O notation allows us to do something more compelling. Observe that for any arbitrary, fixed constant k.

O(n) = O(k * n)

We can use this feature to improve the performance of the hash map. We could instead think about the probability of at most 2 collisions.

pcollision x 2 = (n / capacity)2

This is much lower. Since the cost of handling one extra collision is irrelevant to Big O performance, we've found a way to improve performance without actually changing the algorithm! We can generalzie this to

pcollision x k = (n / capacity)k

And now we can disregard some arbitrary number of collisions and end up with vanishingly tiny likelihood of more collisions than we are accounting for. You could get the probability to an arbitrarily tiny level by choosing the correct k, all without altering the actual implementation of the algorithm.

We talk about this by saying that the hash-map has O(1) access with high probability

worldofjr
  • 3,868
  • 8
  • 37
  • 49
SingleNegationElimination
  • 151,563
  • 33
  • 264
  • 304
  • 8
    Actually, what the above says is that the O(log N) effects are buried, for non-extreme values of N, by the fixed overhead. – Hot Licks Oct 26 '14 at 19:53
  • Technically, that number you gave is the expected value of the number of collisions, which can equal the probability of a single collision. – Simon Kuang Jul 23 '15 at 00:18
  • 1
    Is this similar to amortized analyis? – lostsoul29 Feb 20 '17 at 19:17
  • Your probabilities assume some good distribution of hash codes. Depending on your data and your `hashCode` method the distribution may be adverse and your argument therefore fail. – Ole V.V. Nov 30 '18 at 11:30
  • 1
    @OleV.V. good performance of a HashMap is always depentend on a good distribution of your hash function. You can trade better hash quality for hashing speed by using a cryptographic hashing function on your input. – SingleNegationElimination Dec 03 '18 at 00:16
  • You're speaking of collisions, what kind of collisions do you mean? Can you give me an example of how something would collide? – DFSFOT Nov 19 '20 at 09:52
42

You seem to mix up worst-case behaviour with average-case (expected) runtime. The former is indeed O(n) for hash tables in general (i.e. not using a perfect hashing) but this is rarely relevant in practice.

Any dependable hash table implementation, coupled with a half decent hash, has a retrieval performance of O(1) with a very small factor (2, in fact) in the expected case, within a very narrow margin of variance.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • 8
    I've always thought upper bound was worst case but it appears I was mistaken - you can have the upper bound for average case. So it appears that people claiming O(1) should have made it clear that was for average case. The worst case is a data set where there are many collisions making it O(n). That makes sense now. – paxdiablo Jun 29 '09 at 07:55
  • 2
    You should probably make it clear that when you use big O notation for the average case you are talking about an upper bound on the the expected runtime function which is a clearly defined mathematical function. Otherwise your answer doesn't make much sense. – ldog Jun 29 '09 at 20:19
  • 1
    gmatt: I'm not sure that I understand your objection: big-O notation is an upper bound on the function *by definition*. What else could I therefore mean? – Konrad Rudolph Jun 30 '09 at 07:39
  • 3
    well usually in computer literature you see big O notation representing an upperbound on the runtime or space complexity functions of an algorithm. In this case the upperbound is actually on the expectation which is itself not a function but an operator on functions (Random Variables) and is actually in fact an integral (lebesgue.) The very fact that you can bound such a thing should not be taken for granted and is not trivial. – ldog Jun 30 '09 at 17:52
39

In Java, how HashMap works?

  • Using hashCode to locate the corresponding bucket [inside buckets container model].
  • Each bucket is a LinkedList (or a Balanced Red-Black Binary Tree under some conditions starting from Java 8) of items residing in that bucket.
  • The items are scanned one by one, using equals for comparison.
  • When adding more items, the HashMap is resized (doubling the size) once a certain load percentage is reached.

So, sometimes it will have to compare against a few items, but generally, it's much closer to O(1) than O(n) / O(log n).
For practical purposes, that's all you should need to know.

Ahmed Nabil
  • 17,392
  • 11
  • 61
  • 88
FogleBird
  • 74,300
  • 25
  • 125
  • 131
  • 11
    Well, since big-O is supposed to specify the limits, it makes no difference whether it's closer to O(1) or not. Even O(n/10^100) is still O(n). I get your point about efficiency bringing then ratio down but that still puts the algorithm at O(n). – paxdiablo Jun 28 '09 at 16:59
  • 5
    Hash-maps analysis is usually on the average case, which is O(1) (with collusions) On the worst case, you can have O(n), but that is usually not the case. regarding the difference - O(1) means that you get the same access time regardless of the amount of items on the chart, and that is usually the case (as long as there is a good proportion between the size of the table and 'n' ) – Liran Orevi Jun 28 '09 at 17:06
  • 5
    It's also worth noting, that it is still exactly O(1), even if the scanning of the bucket takes a while because there are some elements already in it. As long as the buckets have a fixed maximum size, this is just a constant factor irrelevant to the O() classification. But of course there can be even more elements with "similar" keys been added, so that these buckets overflow and you can't guarantee a constant anymore. – sth Jun 28 '09 at 17:34
  • @sth Why would the buckets ever have a fixed maximum size!? – Navin Nov 22 '15 at 09:23
33

Remember that o(1) does not mean that each lookup only examines a single item - it means that the average number of items checked remains constant w.r.t. the number of items in the container. So if it takes on average 4 comparisons to find an item in a container with 100 items, it should also take an average of 4 comparisons to find an item in a container with 10000 items, and for any other number of items (there's always a bit of variance, especially around the points at which the hash table rehashes, and when there's a very small number of items).

So collisions don't prevent the container from having o(1) operations, as long as the average number of keys per bucket remains within a fixed bound.

Daniel James
  • 3,899
  • 22
  • 30
21

I know this is an old question, but there's actually a new answer to it.

You're right that a hash map isn't really O(1), strictly speaking, because as the number of elements gets arbitrarily large, eventually you will not be able to search in constant time (and O-notation is defined in terms of numbers that can get arbitrarily large).

But it doesn't follow that the real time complexity is O(n)--because there's no rule that says that the buckets have to be implemented as a linear list.

In fact, Java 8 implements the buckets as TreeMaps once they exceed a threshold, which makes the actual time O(log n).

roottraveller
  • 7,942
  • 7
  • 60
  • 65
ajb
  • 31,309
  • 3
  • 58
  • 84
5

O(1+n/k) where k is the number of buckets.

If implementation sets k = n/alpha then it is O(1+alpha) = O(1) since alpha is a constant.

roottraveller
  • 7,942
  • 7
  • 60
  • 65
  • 1
    What does the constant **alpha** signify? – Prahalad Deshpande Jun 18 '17 at 06:00
  • In `java.util.HashMap`, the `alpha` constant relates to the *load factor* parameter on the constructor. Though not exactly, because the number of buckets is *quantized* by the way that `HashMap` chooses sizes when resizing. (This analysis is also assuming that the distibution of keys to buckets is roughly uniform; i.e. it is an *average case* complexity, not a *worst case* complexity.) – Stephen C Aug 15 '20 at 04:53
4

If the number of buckets (call it b) is held constant (the usual case), then lookup is actually O(n).
As n gets large, the number of elements in each bucket averages n/b. If collision resolution is done in one of the usual ways (linked list for example), then lookup is O(n/b) = O(n).

The O notation is about what happens when n gets larger and larger. It can be misleading when applied to certain algorithms, and hash tables are a case in point. We choose the number of buckets based on how many elements we're expecting to deal with. When n is about the same size as b, then lookup is roughly constant-time, but we can't call it O(1) because O is defined in terms of a limit as n → ∞.

I. J. Kennedy
  • 24,725
  • 16
  • 62
  • 87
3

Elements inside the HashMap are stored as an array of linked list (node), each linked list in the array represents a bucket for unique hash value of one or more keys.
While adding an entry in the HashMap, the hashcode of the key is used to determine the location of the bucket in the array, something like:

location = (arraylength - 1) & keyhashcode

Here the & represents bitwise AND operator.

For example: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

During the get operation it uses same way to determine the location of bucket for the key. Under the best case each key has unique hashcode and results in a unique bucket for each key, in this case the get method spends time only to determine the bucket location and retrieving the value which is constant O(1).

Under the worst case, all the keys have same hashcode and stored in same bucket, this results in traversing through the entire list which leads to O(n).

In the case of java 8, the Linked List bucket is replaced with a TreeMap if the size grows to more than 8, this reduces the worst case search efficiency to O(log n).

Ramprabhu
  • 195
  • 1
  • 13
2

We've established that the standard description of hash table lookups being O(1) refers to the average-case expected time, not the strict worst-case performance. For a hash table resolving collisions with chaining (like Java's hashmap) this is technically O(1+α) with a good hash function, where α is the table's load factor. Still constant as long as the number of objects you're storing is no more than a constant factor larger than the table size.

It's also been explained that strictly speaking it's possible to construct input that requires O(n) lookups for any deterministic hash function. But it's also interesting to consider the worst-case expected time, which is different than average search time. Using chaining this is O(1 + the length of the longest chain), for example Θ(log n / log log n) when α=1.

If you're interested in theoretical ways to achieve constant time expected worst-case lookups, you can read about dynamic perfect hashing which resolves collisions recursively with another hash table!

jtb
  • 889
  • 11
  • 27
2

It is O(1) only if your hashing function is very good. The Java hash table implementation does not protect against bad hash functions.

Whether you need to grow the table when you add items or not is not relevant to the question because it is about lookup time.

Antti Huima
  • 25,136
  • 3
  • 52
  • 71
1

This basically goes for most hash table implementations in most programming languages, as the algorithm itself doesn't really change.

If there are no collisions present in the table, you only have to do a single look-up, therefore the running time is O(1). If there are collisions present, you have to do more than one look-up, which drives down the performance towards O(n).

Tobias Svensson
  • 149
  • 1
  • 5
  • 1
    That assumes the running time is bounded by the lookup time. In practice you'll find a lot of situations where the hash function provides the boundary (String) – Stephan Eggermont Aug 05 '09 at 21:49
1

It depends on the algorithm you choose to avoid collisions. If your implementation uses separate chaining then the worst case scenario happens where every data element is hashed to the same value (poor choice of the hash function for example). In that case, data lookup is no different from a linear search on a linked list i.e. O(n). However, the probability of that happening is negligible and lookups best and average cases remain constant i.e. O(1).

Nizar Grira
  • 743
  • 2
  • 7
  • 21
1

Only in theoretical case, when hashcodes are always different and bucket for every hash code is also different, the O(1) will exist. Otherwise, it is of constant order i.e. on increment of hashmap, its order of search remains constant.

sn.anurag
  • 617
  • 7
  • 14
0

Of course the performance of the hashmap will depend based on the quality of the hashCode() function for the given object. However, if the function is implemented such that the possibility of collisions is very low, it will have a very good performance (this is not strictly O(1) in every possible case but it is in most cases).

For example the default implementation in the Oracle JRE is to use a random number (which is stored in the object instance so that it doesn't change - but it also disables biased locking, but that's an other discussion) so the chance of collisions is very low.

Grey Panther
  • 12,870
  • 6
  • 46
  • 64
  • "it is in most cases". More specifically, the total time will tend towards K times N (where K is constant) as N tends towards infinity. – ChrisW Jun 28 '09 at 16:58
  • 8
    This is wrong. The index in the hash table is going to be determined via `hashCode % tableSize` which means there can certainly be collisions. You aren't getting full use of the 32-bits. That's kind of the point of hash tables... you reduce a large indexing space to a small one. – FogleBird Jun 28 '09 at 16:58
  • 2
    "you are guaranteed that there will be no collisions" No you're not because the size of the map is smaller than the size of the hash: for example if the size of the map is two, then a collision is guaranteed (not matter what the hash) if/when I try to insert three elements. – ChrisW Jun 28 '09 at 16:59
  • But how do you convert from a key to the memory address in O(1)? I mean like x = array["key"]. The key is not the memory address so it would still have to be an O(n) lookup. – paxdiablo Jun 28 '09 at 17:09
  • If your hashtable's key is the object's address, then you don't need a hashtable at all. The point is to have a relatively small table (255 buckets, for example), and to have *uniform distribution*. Then you can predict that each bucket will contain approximately the same number of items. – vgru Jun 28 '09 at 17:20
  • 1
    "I believe that if you don't implement hashCode, it will use the memory address of the object". It could use that, but the default hashCode for the standard Oracle Java is actually a 25-bit random number stored in the object header, so 64/32-bit is of no consequence. – Boann Mar 29 '14 at 17:01
  • @Boann - that's perfectly true, I'll edit the response to reflect this. – Grey Panther Mar 31 '14 at 04:57
0

Academics aside, from a practical perspective, HashMaps should be accepted as having an inconsequential performance impact (unless your profiler tells you otherwise.)

Ryan Emerle
  • 15,461
  • 8
  • 52
  • 69
  • 4
    Not in practical applications. As soon as you use a string as a key, you'll notice that not all hash functions are ideal, and some are really slow. – Stephan Eggermont Aug 05 '09 at 21:44