By drawnonward

2010-05-05 07:45:32 8 Comments

It seems to be common knowledge that hash tables can achieve O(1), but that has never made sense to me. Can someone please explain it? Here are two situations that come to mind:

A. The value is an int smaller than the size of the hash table. Therefore, the value is its own hash, so there is no hash table. But if there was, it would be O(1) and still be inefficient.

B. You have to calculate a hash of the value. In this situation, the order is O(n) for the size of the data being looked up. The lookup might be O(1) after you do O(n) work, but that still comes out to O(n) in my eyes.

And unless you have a perfect hash or a large hash table, there are probably several items per bucket. So, it devolves into a small linear search at some point anyway.

I think hash tables are awesome, but I do not get the O(1) designation unless it is just supposed to be theoretical.

Wikipedia's article for hash tables consistently references constant lookup time and totally ignores the cost of the hash function. Is that really a fair measure?

Edit: To summarize what I learned:

  • It is technically true because the hash function is not required to use all the information in the key and so could be constant time, and because a large enough table can bring collisions down to near constant time.

  • It is true in practice because over time it just works out as long as the hash function and table size are chosen to minimize collisions, even though that often means not using a constant time hash function.


@Tony Delroy 2019-05-23 07:10:29

A. The value is an int smaller than the size of the hash table. Therefore, the value is its own hash, so there is no hash table. But if there was, it would be O(1) and still be inefficient.

This is a case where you could trivially map the keys to distinct buckets, so an array seems a better choice of data structure than a hash table. Still, the inefficiencies don't grow with the table size.

(You might still use a hash table because you don't trust the ints to remain smaller than the table size as the program evolves, you want to make the code potentially reusable when that relationship doesn't hold, or you just don't want people reading/maintaining the code to have to waste mental effort understanding and maintaining the relationship).

B. You have to calculate a hash of the value. In this situation, the order is O(n) for the size of the data being looked up. The lookup might be O(1) after you do O(n) work, but that still comes out to O(n) in my eyes.

We need to distinguish between the size of the key (e.g. in bytes), and the size of the number of keys being stored in the hash table. Claims that hash tables provide O(1) operations mean that operations (insert/erase/find) don't tend to slow down further as the number of keys increases from hundreds to thousands to millions to billions (at least not if all the data is accessed/updated in equally fast storage, be that RAM or disk - cache effects may come into play but even the cost of a worst-case cache miss tends to be some constant multiple of best-case hit).

Consider a telephone book: you may have names in there that are quite long, but whether the book has 100 names, or 10 million, the average name length is going to be pretty consistent, and the worst case in history...

Guinness world record for the Longest name used by anyone ever was set by Adolph Blaine Charles David Earl Frederick Gerald Hubert Irvin John Kenneth Lloyd Martin Nero Oliver Paul Quincy Randolph Sherman Thomas Uncas Victor William Xerxes Yancy Wolfeschlegelsteinhausenbergerdorff, Senior

...wc tells me that's 215 characters - that's not a hard upper-bound to the key length, but we don't need to worry about there being massively more.

That holds for most real world hash tables: the average key length doesn't tend to grow with the number of keys in use. There are exceptions, for example a key creation routine might return strings embedding incrementing integers, but even then every time you increase the number of keys by an order of magnitude you only increase the key length by 1 character: it's not significant.

It's also possible to create a hash from a fixed-size amount of key data. For example, Microsoft's Visual C++ ships with a Standard Library implementation of std::hash<std::string> that creates a hash incorporating just ten bytes evenly spaced along the string, so if the strings only vary at other indices you get collisions (and hence in practice non O(1) behaviours on the post-collision searching side), but the time to create the hash has a hard upper bound.

And unless you have a perfect hash or a large hash table, there are probably several items per bucket. So, it devolves into a small linear search at some point anyway.

Generally true, but the awesome thing about hash tables is that the number of keys visited during those "small linear searches" is - for the separate chaining approach to collisions - a function of the hash table load factor (ratio of keys to buckets).

For example, with a load factor of 1.0 there's an average of ~1.58 to the length of those linear searches, regardless of the number of keys (see my answer here). For closed hashing it's a bit more complicated, but not much worse when the load factor isn't too high.

It is technically true because the hash function is not required to use all the information in the key and so could be constant time, and because a large enough table can bring collisions down to near constant time.

This kind of misses the point. Any kind of associative data structure ultimately has to do operations across every part of the key sometimes (inequality may sometimes be determined from just a part of the key, but equality generally requires every bit be considered). At a minimum, it can hash the key once and store the hash value, and if it uses a strong enough hash function - e.g. 64-bit MD5 - it might practically ignore even the possibility of two keys hashing to the same value (a company I worked for did exactly that for the distributed database: hash-generation time was still insignificant compared to WAN-wide network transmissions). So, there's not too much point obsessing about the cost to process the key: that's inherent in storing keys regardless of the data structure, and as said above - doesn't tend to grow worse on average with there being more keys.

As for large enough hash tables bringing collisions down, that's missing the point too. For separate chaining, you still have a constant average collision chain length at any given load factor - it's just higher when the load factor is higher, and that relationship is non-linear. The SO user Hans comments on my answer also linked above that:

average bucket length conditioned on nonempty buckets is a better measure of efficiency. It is a/(1-e^{-a}) [where a is the load factor, e is 2.71828...]

So, the load factor alone determines the average number of colliding keys you have to search through during insert/erase/find operations. For separate chaining, it doesn't just approach being constant when the load factor is low - it's always constant. For open addressing though your claim has some validity: some colliding elements are redirected to alternative buckets and can then interfere with operations on other keys, so at higher load factors (especially > .8 or .9) collision chain length gets more dramatically worse.

It is true in practice because over time it just works out as long as the hash function and table size are chosen to minimize collisions, even though that often means not using a constant time hash function.

Well, the table size should result in a sane load factor given the choice of close hashing or separate chaining, but also if the hash function is a bit weak and the keys aren't very random, having a prime number of buckets often helps reduce collisions too (hash-value % table-size then wraps around such that changes only to a high order bit or two in the hash-value still resolve to buckets spread pseudo-randomly across different parts of the hash table).

@Edman 2019-02-02 13:50:10

TL;DR: Hash tables guarantee O(1) expected worst case time if you pick your hash function uniformly at random from a universal family of hash functions. Expected worst case is not the same as average case.

Disclaimer: I don't formally prove hash tables are O(1), for that have a look at this video from coursera [1]. I also don't discuss the amortized aspects of hash tables. That is orthogonal to the discussion about hashing and collisions.

I see a surprisingly great deal of confusion around this topic in other answers and comments, and will try to rectify some of them in this long answer.

Reasoning about worst case

There are different types of worst case analysis. The analysis that most answers have made here so far is not worst case, but rather average case [2]. Average case analysis tends to be more practical. Maybe your algorithm has one bad worst case input, but actually works well for all other possible inputs. Bottomline is your runtime depends on the dataset you're running on.

Consider the following pseudocode of the get method of a hash table. Here I'm assuming we handle collision by chaining, so each entry of the table is a linked list of (key,value) pairs. We also assume the number of buckets m is fixed but is O(n), where n is the number of elements in the input.

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

As other answers have pointed out, this runs in average O(1) and worst case O(n). We can make a little sketch of a proof by challenge here. The challenge goes as follows:

(1) You give your hash table algorithm to an adversary.

(2) The adversary can study it and prepare as long as he wants.

(3) Finally the adversary gives you an input of size n for you to insert in your table.

The question is: how fast is your hash table on the adversary input?

From step (1) the adversary knows your hash function; during step (2) the adversary can craft a list of n elements with the same hash modulo m, by e.g. randomly computing the hash of a bunch of elements; and then in (3) they can give you that list. But lo and behold, since all n elements hash to the same bucket, your algorithm will take O(n) time to traverse the linked list in that bucket. No matter how many times we retry the challenge, the adversary always wins, and that's how bad your algorithm is, worst case O(n).

How come hashing is O(1)?

What threw us off in the previous challenge was that the adversary knew our hash function very well, and could use that knowledge to craft the worst possible input. What if instead of always using one fixed hash function, we actually had a set of hash functions, H, that the algorithm can randomly choose from at runtime? In case you're curious, H is called a universal family of hash functions [3]. Alright, let's try adding some randomness to this.

First suppose our hash table also includes a seed r, and r is assigned to a random number at construction time. We assign it once and then it's fixed for that hash table instance. Now let's revisit our pseudocode.

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

If we try the challenge one more time: from step (1) the adversary can know all the hash functions we have in H, but now the specific hash function we use depends on r. The value of r is private to our structure, the adversary cannot inspect it at runtime, nor predict it ahead of time, so he can't concoct a list that's always bad for us. Let's assume that in step (2) the adversary chooses one function hash in H at random, he then crafts a list of n collisions under hash modulo m, and sends that for step (3), crossing fingers that at runtime H[r] will be the same hash they chose.

This is a serious bet for the adversary, the list he crafted collides under hash, but will just be a random input under any other hash function in H. If he wins this bet our run time will be worst case O(n) like before, but if he loses then well we're just being given a random input which takes the average O(1) time. And indeed most times the adversary will lose, he wins only once every |H| challenges, and we can make |H| be very large.

Contrast this result to the previous algorithm where the adversary always won the challenge. Handwaving here a bit, but since most times the adversary will fail, and this is true for all possible strategies the adversary can try, it follows that although the worst case is O(n), the expected worst case is in fact O(1).

Again, this is not a formal proof. The guarantee we get from this expected worst case analysis is that our run time is now independent of any specific input. This is a truly random guarantee, as opposed to the average case analysis where we showed a motivated adversary could easily craft bad inputs.

@nak 2018-05-27 23:54:52

It seems based on discussion here, that if X is the ceiling of (# of elements in table/# of bins), then a better answer is O(log(X)) assuming an efficient implementation of bin lookup.

@ChaosPredictor 2018-03-09 17:33:04

There are two settings under which you can get O(1) worst-case times.

  1. If your setup is static, then FKS hashing will get you worst-case O(1) guarantees. But as you indicated, your setting isn't static.
  2. If you use Cuckoo hashing, then queries and deletes are O(1) worst-case, but insertion is only O(1) expected. Cuckoo hashing works quite well if you have an upper bound on the total number of inserts, and set the table size to be roughly 25% larger.

Copied from here

@Eugene D 2015-03-28 03:31:29

Hashing is O(1) only if there are only constant number of keys in the table and some other assumptions are made. But in such cases it has advantage.

If your key has an n-bit representation, your hash function can use 1, 2, ... n of these bits. Thinking about a hash function that uses 1 bit. Evaluation is O(1) for sure. But you are only partitioning the key space into 2. So you are mapping as many as 2^(n-1) keys into the same bin. using BST search this takes up to n-1 steps to locate a particular key if nearly full.

You can extend this to see that if your hash function uses K bits your bin size is 2^(n-k).

so K-bit hash function ==> no more than 2^K effective bins ==> up to 2^(n-K) n-bit keys per bin ==> (n-K) steps (BST) to resolve collisions. Actually most hash functions are much less "effective" and need/use more than K bits to produce 2^k bins. So even this is optimistic.

You can view it this way -- you will need ~n steps to be able to uniquely distinguish a pair of keys of n bits in the worst case. There is really no way to get around this information theory limit, hash table or not.

However, this is NOT how/when you use hash table!

The complexity analysis assumes that for n-bit keys, you could have O(2^n) keys in the table (e.g. 1/4 of all possible keys). But most if not all of the time we use hash table, we only have a constant number of the n-bit keys in the table. If you only want a constant number of keys in the table, say C is your maximum number, then you could form a hash table of O(C) bins, that guarantees expected constant collision (with a good hash function); and a hash function using ~logC of the n bits in the key. Then every query is O(logC) = O(1). This is how people claim "hash table access is O(1)"/

There are a couple of catches here -- first, saying you don't need all the bits may only be a billing trick. First you cannot really pass the key value to the hash function, because that would be moving n bits in the memory which is O(n). So you need to do e.g. a reference passing. But you still need to store it somewhere already which was an O(n) operation; you just don't bill it to the hashing; you overall computation task cannot avoid this. Second, you do the hashing, find the bin, and found more than 1 keys; your cost depends on your resolution method -- if you do comparison based (BST or List), you will have O(n) operation (recall key is n-bit); if you do 2nd hash, well, you have the same issue if 2nd hash has collision. So O(1) is not 100% guaranteed unless you have no collision (you can improve the chance by having a table with more bins than keys, but still).

Consider the alternative, e.g. BST, in this case. there are C keys, so a balanced BST will be O(logC) in depth, so a search takes O(logC) steps. However the comparison in this case would be an O(n) operation ... so it appears hashing is a better choice in this case.

@Mark Byers 2010-05-05 07:51:28

You have two variables here, m and n, where m is the length of the input and n is the number of items in the hash.

The O(1) lookup performance claim makes at least two assumptions:

  • Your objects can be equality compared in O(1) time.
  • There will be few hash collisions.

If your objects are variable size and an equality check requires looking at all bits then performance will become O(m). The hash function however does not have to be O(m) - it can be O(1). Unlike a cryptographic hash, a hash function for use in a dictionary does not have to look at every bit in the input in order to calculate the hash. Implementations are free to look at only a fixed number of bits.

For sufficiently many items the number of items will become greater than the number of possible hashes and then you will get collisions causing the performance rise above O(1), for example O(n) for a simple linked list traversal (or O(n*m) if both assumptions are false).

In practice though the O(1) claim while technically false, is approximately true for many real world situations, and in particular those situations where the above assumptions hold.

@JeremyP 2010-05-05 08:05:27

As well as the above, if you are using immutable objects as your keys e.g. Java Strings, having calculated the hash once, you can remember it and not have to calculate it again. On the other hand, you can't usually rely on the hash to tell if two keys are equal once you have found the right bucket, so for strings you need to do an O(m) traversal to find out if they are equal.

@Mark Byers 2010-05-05 08:22:57

@JeremyP: Good point on the O(m) equality comparison. I missed that - updated post. Thanks!

@Thomas Ahle 2014-05-30 12:40:47

The O(1) claim is true if you're hashing ints or something else that fits in a machine word. That's what most theory on hashing assumes.

@Steve K 2014-06-02 23:43:54

I like that explanation of yours Mark, I quoted it on my article about hash tables on

@spandey 2016-12-07 11:59:28

I dont think O(1) and O(n) ever happens in real life.

@Tony Delroy 2018-02-20 14:26:53

In "m is the length of the input" - input is overly vague - it might mean all keys & values being inserted, but it becomes clear later (at least to those who already understand the topic) you mean the key. Just suggesting using "key" in the answer for clarity. BTW - concrete example - Visual C++'s std::hash of textual keys combines 10 characters evenly spaced along the text into the hash value, so it's O(1) regardless of text length (but massively more collision prone than GCC!). Separately, claims of O(1) have another assumption (normally correctly) that m is much less than n.

@mpen 2010-05-05 08:03:57

You have to calculate the hash, so the order is O(n) for the size of the data being looked up. The lookup might be O(1) after you do O(n) work, but that still comes out to O(n) in my eyes.

What? To hash a single element takes constant time. Why would it be anything else? If you're inserting n elements, then yes, you have to compute n hashes, and that takes linear time... to look an element up, you compute a single hash of what you're looking for, then find the appropriate bucket with that. You don't re-compute the hashes of everything that's already in the hash table.

And unless you have a perfect hash or a large hash table there are probably several items per bucket so it devolves into a small linear search at some point anyway.

Not necessarily. The buckets don't necessarily have to be lists or arrays, they can be any container type, such as a balanced BST. That means O(log n) worst case. But this is why it's important to choose a good hashing function to avoid putting too many elements into one bucket. As KennyTM pointed out, on average, you will still get O(1) time, even if occasionally you have to dig through a bucket.

The trade off of hash tables is of course the space complexity. You're trading space for time, which seems to be the usual case in computing science.

You mention using strings as keys in one of your other comments. You're concerned about the amount of time it takes to compute the hash of a string, because it consists of several chars? As someone else pointed out again, you don't necessarily need to look at all the chars to compute the hash, although it might produce a better hash if you did. In that case, if there are on average m chars in your key, and you used all of them to compute your hash, then I suppose you're right, that lookups would take O(m). If m >> n then you might have a problem. You'd probably be better off with a BST in that case. Or choose a cheaper hashing function.

@Nick Dandoulakis 2010-05-05 08:08:28

hash tables don't use BSTs. BSTs don't require hash values. Maps and Sets can be implemented as BSTs though.

@mpen 2010-05-05 08:12:02

@Nick: Eh? No...BSTs don't require hash values... that's the point. We're assuming that at this point we already have a collision (same hash... or at least same bucket), so we need to look at something else to find the right element, i.e., the actual value.

@Nick Dandoulakis 2010-05-05 08:20:41

oh, I see your point. But I'm not sure that mixing BSTs and hashes worth the trouble. Why not just use BSTs?

@mpen 2010-05-05 08:25:35

I'm just saying that you could to get rid of that O(n) for collisions. If you are expecting lots of collisions, then you're right, probably better off going with a BST in the first place.

@spaaarky21 2017-03-31 01:41:38

@mpen I guess hashing a string doesn't have to look at every character but MS has C#'s string hashing method documented as O(N) and Java's is too if you take a look at the source.‌​e/…

@mpen 2017-03-31 19:38:37

@spaaarky21 Right, but N in that case is the length of the string. We only need to hash one string to determine which 'bucket' it needs to go in -- it does not grow with the length of the hashmap.

@David M 2010-05-05 07:50:48

The hash is fixed size - looking up the appropriate hash bucket is a fixed cost operation. This means that it is O(1).

Calculating the hash does not have to be a particularly expensive operation - we're not talking cryptographic hash functions here. But that's by the by. The hash function calculation itself does not depend on the number n of elements; while it might depend on the size of the data in an element, this is not what n refers to. So the calculation of the hash does not depend on n and is also O(1).

@Nick Dandoulakis 2010-05-05 07:54:44

looking up the hash bucket is O(1). But locating the right key, is a O(n) procedure, where n depends on the number of hash collisions.

@drawnonward 2010-05-05 08:00:41

So of 3 steps, calculate the hash, find the bucket, search the bucket, the middle step is constant? Searching the bucket is usually constant. Calculating the hash is usually several orders of magnitude cheaper than other means of finding the bucket. But does that really add up to constant time? In a naive substring search, you would say O(n*m) for the two lengths, so why is the length of the key disregarded here?

@jk. 2010-05-05 08:13:37

finding a fixed length key is only O(n) only if its list backed, a balanced tree backed hash table will be O(log(n))

@Thomas Ahle 2014-05-30 12:41:33

@Jk For good hash functions, the worst case is always logn, see my answer at‌​ty/…

@Saurabh Chandra Patel 2018-01-04 06:07:46

On worst case complexity will be o(n) in case of collision

Related Questions

Sponsored Content

14 Answered Questions

[SOLVED] How does a hash table work?

16 Answered Questions

[SOLVED] Why should hash functions use a prime number modulus?

41 Answered Questions

[SOLVED] How can you speed up Eclipse?

  • 2008-11-25 03:18:56
  • user2427
  • 608106 View
  • 1277 Score
  • 41 Answer
  • Tags:   eclipse performance

29 Answered Questions

[SOLVED] How can you profile a Python script?

36 Answered Questions

[SOLVED] How can I pair socks from a pile efficiently?

15 Answered Questions

[SOLVED] How to define hash tables in Bash?

24 Answered Questions

[SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition

4 Answered Questions

[SOLVED] List of Big-O for PHP functions

Sponsored Content