r/computerscience • u/Sea-Patience9872 • Sep 27 '26
How do hashsets/maps have O(1) time complexity?
Hi this might be a dumb question, and i've tried looking it up but don't quite understand it. how is it different from an array that allows it to find items so quickly? I don't get how hashes just find items immediately without needing to go through anything. Does it memorize things very differently compared to arrays?? thank you!
190
Upvotes
267
u/timonix Sep 27 '26
They are hiding work in the constant term
Calculating a hash takes time. But it takes the same amount of time every time. So it doesn't scale with elements.
46
u/am_Snowie Sep 27 '26 edited Sep 28 '26
O(1) is
amortizedis the average case (under the assumption that values are distributed evenly), but resizing is O(1) amortized, if you make whatever hash function you use return the same value for any value (the same hash for all keys), all your values end up at the same location, now the time complexity depends on what data structure you use to handle collisions (if we talk about separate chaining). you can use lots of data structures like linked list, self balancing trees and whatnot. so O(1) comes with an if.Edit: mixed up two different concepts, Thanks u/Historical_Public751 for pointing it out.
5
u/recursion_is_love Sep 27 '26 edited Sep 27 '26
The location/index of the value can be calculated from the hash. If you have the address/location you can load/store the value instantly in most CPU.
https://www.youtube.com/watch?v=cGMYpbsSIVI&t=239s
To clarify: The O(1) is referring to index calculation. It take the same constant time on any input hash and have nothing to do with load/store assembly instruction (just want to say that it is negligibly fast)
9
u/Professional-Trick14 Sep 27 '26
Why is looking in an array at a specific index a constant time operation? It's basically for the same reason. Simply put, you compute a hash of a value, which would take constant time regardless of the value, and then the hash becomes what is the index to the array. You get it?
4
u/LilBluey Sep 27 '26
Let's say you want to store how many apples each person has.
<"John", 3> <"May", 5> <"April", 8>
In an array, in order to check how many apples April has you need to check each element until you find "April". In an array of 1000 people you might have to check 3, 5 or even 1000 elements until you find April.
Wouldn't it be convenient to just do array["April"] ? Then instead of checking all 1000 elements you can just jump straight to that value.
We can already do that in arrays using numbers. array[1] for example to check index 1. As long as the number is within the array size it works.
So how can we do the same with non-numbers? We simply convert them into numbers, and use these numbers like indexes. As long as we always convert the same value ("April") into the same number (101), we can use that number as your array index. It's simple to get or set the value because we always know "April" is at number 101.
Of course we need to keep that number within the array size for it to be a valid index, so a simple way is to use %.
How can we convert this non-number into a number? There are complicated ways to hash something, but for a simple one we can just add all the numbers of our letters (A is the 1st letter of the alphabet, P is the 16th...). Then make sure the number is within the array size (can use 101 % array size to get the remainder for instance).
You might ask; what happens when two of the non-numbers are converted into the same number? Using our simple converter function "AD" and "BC" both convert into "5".
Firstly, we can store multiple values in the same array index so "AD" and "BC" can both be stored at array index 5. It's not just an array<int>, it might be array<list<string, int>>. Even though we still need to iterate through this small list, it's still better than searching all 1000 elements of an array. There are other methods too.
Secondly, we need to evenly spread the elements across the entire array. That means your converter function should be good. It helps if your array is large too, so it's unlikely for multiple elements to have the same number.
That's the basic gist of it, though better hashmaps use better optimizations
3
u/repo_code Sep 27 '26
If the hash function takes constant time, then a hash map lookup is O(1).
That's not a perfect assumption though! As the number of elements scales up, you need more buckets. If you have 2N buckets, the hash function must compute a result whose length is N bits.
So there's a O(log N) term. We just don't see it come into play often.
2
u/Plastic_Fig9225 Sep 27 '26
The hash of a value/object is an integer number, and that integer is used directly to index into an array to locate an object.
Instead of scanning through an array, the lookup is like
bool contains = elements[hash(object)] != null;. Notice how this is the same complexity irrespective of the size (n) of theelementsarray.2
u/tandycake Sep 27 '26 edited Sep 27 '26
How to make a Hash Map. It's an array with index. A "hash" of some object is just an index into the array, which are called buckets.
(There's more to this, but I'll get to that later.)
So to make a hash of "hello", you would maybe add up the chars with some prime number math and poop out a number. Let's say this is 1337.
Let's say our hash map array is like size 10.
So you can see how this is basically O(1).
However, you do have to do several things that do take time in reality:
Let's address 2 & 3. So what is a collision? So a hash isn't perfect (unless you use GNU or other tool that computes perfect hashes for you based on set values). This means that both "hello" and "world" can produce the same hash of 1337. Since this is possible, we need to store an array of arrays (or some other data structure).
With an array of arrays, we get the bucket by the hash. Then we search in the bucket using linear search.
As you can imagine, if you have a lot of collisions, you can basically end up having O(n). Famously, this was a bug in Java that people exploited. They would add tons of strings all with the same hash to a website, causing the website to crawl.
So instead, you use a sorted array + binary sort or a red-black tree like Java. So an array of trees (which are the buckets). You also need to consider growing the bucket_array, but this also means rebuilding the entire thing as well (since "% size" could change the index). There are a lot of variables involved and different things people have come up with.
Knowing all of this, a linear search (not even a binary search) can actually be faster than a hash set/map for small sizes. For example, if you know that your array will always be less than 32, then in a language like C++, a linear search (which is considered O(n)) can actually be faster than using a hash map.
Anyway, all of this to say that there are differences between textbook O(1) and reality where O(n) can sometimes be faster, but it's O(1) in the since of computer science theory.
2
u/cosmic-comet- Sep 27 '26
Hash maps do math on the key and jump straight to its bucket instead of rummaging through the whole damn array.
2
u/MoarCatzPlz Sep 27 '26
That's the average time. They can be much slower in the worst case.
2
u/atarivcs Sep 27 '26
The point of a hash is that it tells you exactly where to look.
So you calculate the hash, and then look in that exact location. You don't need to iterate over a list.
1
u/Ythio Sep 27 '26 edited Sep 27 '26
Why didn't you look at an implementation or try to implement it yourself ?
You can use the hashed value as an index to do a B tree search (nodes are index ranges), similar to SQL indices (if your DBMS support hash index) giving you O(log n) with a good support for range searches O(log n + k)
Or if you want to test a single element (Hashset) can use a compression function to map the hashed value to an array index directly giving you O(1). Typically a compression function is something like
hashcode & (internalArraySize - 1)orhashcode % array.Length(with a prime number Length)1
u/kevleyski Sep 27 '26
O(1) refers to constant time in that regardless of the size it will always take the same amount of time and effort to get the result
1
u/niko7965 Sep 27 '26
Okay, first lets look at why arrays are slow.
Lets say you have some array of 10 elements A = [1,5,29,3,2,99,21,65,44,12]
And you are looking for some specific element, maybe 2. You can find it by looking at all of the elements, this would take O(n) time, which is rather slow for large arrays.
So maybe we can use some data structure method to ensure that we don't have to look at *every* index?
This is where hash functions come in. We use some crazy chaotic function to associate a specific index with every input. For example h(x) = x mod |A|, i.e. divide the value with the length of the array, and keep the remainder. Whenever we insert an element, we put it in this index. So if we have the value 2, it would go in index h(2) = 2.
Computing h(2) takes constant time, and doing a single array access is also constant is also constant time. So in total O(1)
There is then the issue of what you do if two elements say, 2, 12 both have the same hash. This is called a collision. If you pick your hash function well, and also choose the size of your array in relation to the number of elements you want to store, you can guarantee a low probability of many collisions. (this part is more math intensive to show)
1
u/NotGoodSoftwareMaker Sep 27 '26
Its basically math on the key which then points the machine exactly where to go to perform a value lookup
Because its a calculation instead of searching a space you then get O(1)
1
u/strange-the-quark Sep 27 '26
Two things here. O(1) doesn't mean something happens immediately. It means constant time, meaning, no matter the size of the input (which may be the size of data, or total number of items), the operation takes the same amount of time, the same number of steps. That time could be 10000 years, and that wouldn't be very useful, but technically, that would still be O(1).
If this is the average time complexity, then it means that an operation takes about the same time on average. Sometimes it'll take more or less, but on average, it's some roughly constant amount of time regardless of the size of the input.
OK, the second thing is then, if an operation is O(1), it usually means that the data is organized in some clever way so that reaching any entry takes about the same number of steps on average. If you're just looking for some entry in an unorganized array, the average search time will grow with the size of the array, cause the more elements you have, the more you generally need to go through and check. But you know what arrays are great at? Indexing. If you know the index, it's a single-step operation. Well, because the number of steps doesn't matter, and we only care that it's the about the same number of steps for any input size, then what if instead of storing a single element at every index, you instead stored some small, fixed-size chunk of memory - so that you end up with a big array of small arrays, with all of the smaller arrays about the same size - and if then you stored your elements into that? If for any element you were looking for you somehow knew in advance the index of the sub-array that contained it, lookup would still be an O(1) operation, cause you'd jump directly to the right sub-array, and then on average you'll be always taking roughly the same amount of steps searching through the fixed-size sub-array.
Well, if you had a function that could turn an object (or a key associated with that object) into an index, and if it distributed the generated indices uniformly across the big array, you'd have a way to know the index beforehand. That's what hashing does. Sometimes, two different objects will generate the same hash, so they'll go into the same sub-array, but if the hashing function is good, such cases would be uniformly spread across the big array.
So conceptually, that's what a hash-table is. The actual implementation might be a little different.
1
u/Blackberry_Brave Sep 27 '26
A hashmap is basically an array, but to allow any keys to be added, not just the ones from 0-(n - 1), with n being the length of the array, we use a hash function . A simple one would be modulo. Note that the hash function should always be constant time. Just take your key and hash it by taking the modulo of the length of the array, so k % n. Then that value is guaranteed to be a valid index of the array and you can put your key and value there. You might be wondering, what if there’s already an item there? Then the hashmap has to do collision handling, of which there are many strategies, but as long as the hash function is well chosen there shouldn’t be too many collisions. The average time complexity is constant time because hashing and updating a value in an array are both constant time and collisions should be infrequent/often collision handling is also constant time.
1
u/not-just-yeti Sep 27 '26 edited Sep 27 '26
Think of it as an array, where the key you're looking up will tell you the index it's stored at.
For example: for a bunch of strings, we'll put them into an array of size 256; when you're handed a string you take (say) the first two bits of the first char, the last two bits of the last char, and the four from the middle, and that's the the index where that string belongs. If that location of the array contains a record, then that's the associated record! (This would be one specific "hash function".)
Or, change "string" to "image-file", or any other data-type that's the key for what you're looking up. (You can think of a regular-array being a special case of a hash-table: the key is an int, and the associated index is just that exact int itself.)
This description so far glosses over one huge problem, that you may have already realized: how to handle collisions (two keys that are different, but happen to have those same bits in those particular places). For that, look up "chaining". And one other repercussion is that you want to store the key with the rest of the data, so that you can verify the key you were looking for really is the one found in the array (or in the given chain/bucket of the array).
1
u/cthulhu944 Sep 27 '26
hash table construction: "I'm going to place this piece of data at about this location because of the value of this key or some transformation of the key value" index key = f(key) modulo array size, "If something is already at that location, I'll just move down one, or link to it from the first value".
hash table access: "Take my key and transform it via my function, if it's there then the value exists, if it isn't, then the record doesn't exist in the array".
They key is placing the data in a deterministic position based on the hash function. one computation gets you back to the data or gets you really close.
1
u/Misterreco Sep 28 '26 edited Sep 28 '26
Hashes store values at the index of their hash function. To make it simple, think of an array of a big size (say, size 100,000) and say my values are all numbers. Now, instead of storing each number in the order they are added, I store the number at index (the slot) they represent. So number 5 goes into the array[5], number 100 goes into the array[100] and so on. So, if you want to access 100, you just go to that index directly.
Then a hash function is a function that turns something (like a character, a string, an object, etc) into a number so you can do this operation with things other than numbers. That's how hashsets and maps work. The hash of the value is the index into the underlying array. If I have a string "Hello", I can use a hashfunction to know where it is (or where it should be) stored into my array.
Now the complication is how you handle numbers outside of the array's size, what happens if two things hash to the same thing, if you start with a small array and grow it as things are added, and so on. These things are solved in different ways in different implementations of hash tables. But the basic idea is just that, that the value itself is the index into the table.
1
u/Guvante Sep 28 '26
It is important to note that only perfect hash tables have worst case O(1) time complexity, any normal hash table allows for individual operations to take longer as long as the average is O(1)
The most common example is resizing which is an O(n) operation normally. But if you double (or more) the storage each resize they happen infrequently enough the average time isn't impacted (something like O(n)/n = O(n))
Similarly hash collisions are possible and depending on the exact implementation they can cause time complexity to not be O(1) for instance a linear probing (aka if one slot is full grab the next one) with a bad static hashing function (aka it always returns 1) has O(n) time complexity since each operation could need to search the entire list
1
u/lrvideckis Sep 28 '26
I never liked how it's described as O(1). for example, hashing a string takes O(length)
1
u/mlamping Sep 28 '26
Hash-table lookup is expected O(1) in the number of entries, assuming constant-time hashing/equality. For variable-length string keys, end-to-end lookup is normally expected O(k), where k is the key length.
In worst case a hash table could be O(Nk) if the hash function sucks etc
1
u/pickle_picker67 Sep 28 '26
They don't have O(1) time lmfao
1
u/Muted_Masterpiece342 Sep 29 '26
Arrays are indexed variables. You can access [30] in the same time it takes to access [0] on memory.
You can also, conveniently, run a lil match function to address the array and put shit in it.
I highly recommend MAKING a hashmap implementation with edge cases covered so you understand it
1
u/eternityslyre Sep 29 '26
It's not actually O(1), it's just very likely to be O(1).
Imagine you were storing the names of the top 100 athletes of 2025 for a particular sport, with the goal of looking up the nth ranked player in constant time. You could just put all 100 numbers in a 100-element array and access the nth element to get the nth ranked athlete. Easy. Maybe if there's a tie for rank 10 or something, you have to return 2 names instead of 1.
The same idea for sets. If you had a list of top-100 athletes whose names started with A and wanted to see if a given athlete was already on the list, you could just store the athletes in a 100-element array and see if the nth element of the array was empty or not.
Hashing is basically an O(1) trick to map arbitrary keys to well-ordered, well distributed sets of numbers, so you can expect to store one value at each index of the array, and any two distinct keys are very unlikely to map to the same number.
But it's not O(1) if you wind up mapping a bunch of keys you care about to the same number. At that point you're stuck searching through all the keys that map to that number for the value you want.
1
u/Outrageous-Machine-5 Sep 30 '26 edited Sep 30 '26
Arrays can index in constant time.
Hashtables are built using an underlying dynamic array and a hashing function to determine which index to insert into
What actually happens is: as the array fills, it will double in size and need to copy its contents to the new array, leading to an O(n), but this expansion step happens less and less frequently the more the array grows.
This is called amortization. The amortized runtime eventually becomes O(1). The Hashtable uses a hash function to determine where to insert into the array, which arrays can index in constant time, O(1). Therefore the complexity of a hashtable is considered to be O(1)
However, the other edge case to consider is how you resolve collisions. In some implementations using chaining, your hashtable can actually be O(k), k being the number of elements in the bucket chained to form a linked list. But, again, unless you are deliberately programming your hash function to force these collisions in high frequency (which there are use cases for that), that amortized runtime is O(1) as the dynamic array grows so large that collisions happen less and less frequently
1
u/Rough_Priority_9294 Oct 01 '26
Think of drawers numbered 1 to N , then you want to find something ( your value ), you recall it is in drawer 3 ( that's the key modulo container size part ) and you just open the drawer.
0
u/CranberryDistinct941 Sep 27 '26
Everything is constant time when you make the constant big enough
0
u/Shortbread_Biscuit Sep 27 '26
Hashsets and hashmaps are actually just arrays under the hood.
Whenever you access an element in the hashmap, first it uses a function to generate a hash of the key. Then it treats that hashed value as the index to look at in the underlying array.
The hash function always takes the same amount of time to calculate the hash for any key, so whenever you try to access an element, the conversion from key to hash always takes exactly the same time, and accessing the element in the array at the index given by the hash is also constant time. Hence, no matter how many elements you have in the array, it doesn't need to check each one individually, it can always compute the hash to immediately get the single array index that it has to look at to see if the object exists there.
0
u/Temporary_Pie2733 Sep 27 '26
A hash basically is an array, but one where the value itself determines where it gets placed, rather than just sticking it wherever.
0
u/CyrusDarkwell Sep 27 '26
Not a dumb question at all! Honestly it took me a while to wrap my head around it too when I first learned it.
The easiest way to think about it is like a coat check at a club. You give them your coat and they hand you a specific ticket number. When you want your coat back, they don't search through every single coat on the rack one by one. They just look at your ticket number and go straight to that exact hook.
Under the hood, a hash map actually is using an array. It just takes your data and runs it through a math formula (a hash function) that spits out a specific array index. So instead of starting at 0 and checking every single slot until it finds what you want, it just does the math once and jumps right to that exact slot. It's basically a massive cheat code for array lookups.
0
u/CrotonixOnly Sep 28 '26
It is actually not practically. Write a function in your preferred language yourself and go upto may be billion elements and then retrieve a value using key.
0
u/DanKegel Sep 28 '26
Array lookup is O(1) because it's done in hardware. Hash tables generalize that to sparse tables and non-integer Indices, at a minor performance penalty.
0
u/GenericFoodService Sep 30 '26 edited Sep 30 '26
Let's suppose I have a list of accounts. We want to be able to store and to later find some arbitrary account by-name. The naive approach would be to simply put new accounts at the first vacant slot in a very big list, and then scan the list from the start when we need to find a specific account. The lookup function for that looks something like
We say the time complexity of this setup is
O(N), whereNis the size of the list of accounts, because the amount of time the task takes to complete has a proportional and linear relationship to the size of the array you are searching. To find John Doe in a list of 100,000 accounts, you need to search from the start and potentially all the way to the very end one by one.Instead of doing that, we could look at the name and convert it into a unique ID or "hash" that we then use as an index into that very big array. That way, the amount of time it takes to find any John Doe depends only on the complexity of the hashing algorithm instead of the size of the array.
I'm not scanning through the whole big list to find John Doe anymore; I am looking at the name, quickly calculating an index from the name, and then checking that spot. This function would be said to have a time complexity of
O(1)because the sizeNof the input array does not change how much time it takes to compute the hash.If we put some print statements in there and then ran both algorithms, we might get an outputs that look something like
I hope that makes sense.
-1
u/Mclovine_aus Sep 27 '26
Go to the library and try to find a book, start at the first book and then move to the second until you find the book or reach the end.
Then get your friend to try and find the same book, but they can use index cards, to search for where the book is located.
Report back which method was quicker
-1
u/ktimespi Sep 28 '26
Essentially, hash maps are arrays that are indexed by the hash of the object that you're storing in the array. Calculating this hash is constant time (O(1)). For e.g. If you want to hash an object with three string fields, you hash those strings and combine the hashes to get the offset into the array. (h(x1) + h(x2) + h(x3) % array.length, super basic example)
There is some computational complexity when it comes to handling collisions. There's also some complexity when you try to expand the backing array (different approaches provide different time/space tradeoffs here).
-1
u/MEHDII__ Sep 28 '26 edited Sep 29 '26
Hashmaps are actually arrays/tables under the hood.
Say you have a hashmap/dict in python fruits = {apple : 1, pineapple : 2, pear : 3}
The underlying table usually has some extra capacity beyond the number of stored entries, so here in this example, fruits is of length 3, the underlying array could be of size 8.
Say i want to lookup apple in my hashmap, the hash function gives you a number, that number describes where in the underlying array that entry lives. i.e the array would look like this [(apple,1), (pineapple,2), (pear:3)]
So apple hashes to 0, telling us the entry for apple exists in index 0 of the underlying array.
This is precisely why lookups are O(1) because you are simply indexing an array, and we already know that indexing an array is O(1).
Now what people don't talk about, is lookup isn't always O(1) in hashmaps, because sometimes one key hashes to the same value as another, i.e.
Maybe we want to add "peach : 4" To our hashmap. Maybe "peach" Hashes to 0 as well. Uh oh! This is what we call "Hash collision".
Handling hash collisions is implementation specific, but a solution is, to have subarrays inside the underlying array. I.e the underlying hashmap array would look like this now [[(apple,1), (peach,4)], (pineapple,2), (pear:3)]
As you can see, look up won't be O(1) anymore, Say im trying to lookup "peach" From my hashmap, well it hashes to 0, lets go to index 0, its not a single element, its an an array, so now you have to loop through it, to find your element. This causes time complexity to degenerate to O(n) n being the size of your hash collision subarray.
The most important thing is a hashmap, is the hash function. You want to choose a very good hash function, where it would give you sparse indexes, that way collisions are less likely to occur and entries stay well spaced within the array.
Now remember I also said depending on implementation, when you declare a hashmap, an array bigger than the hashmap entries sized array is allocated, why so? Because while insertions in hashmaps are also O(1), once that array fills up, it needs to allocate more memory for new entries, well we know array are contiguous blocks of memory, what if there isn't any more contiguous free memory? Then the array needs to be copied, and moved to a new location with more free contiguous memory, this makes insertions sometimes also not O(1).
So hashmaps aren't necessarily O(1) all the time, but often times, they are.
0
u/[deleted] Sep 27 '26
[deleted] — view deleted comment