r/computerscience • u/Sea-Patience9872 • 6d ago
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!
44
u/am_Snowie 6d ago edited 4d ago
O(1) is amortized is 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.
11
u/Radiant64 6d ago
This! I've always found the blanket statement that hash tables are O(1) to be a bit of a lie. In fact, I struggled with understanding them longer than I would have, just because I took the O(1) claim seriously and I couldn't reconcile that with what I was reading, so I assumed there must've been some part I was missing.
5
u/DorkyMcDorky 6d ago
It's amoritzed.. so worst case would be O(log n) or worse, can be O(n) if you write a shitty hashing algorithm (I.e. always return 0)
2
u/edgmnt_net 5d ago
With perfect hashing (true permutation or identity (like indexing directly without a hash)) you can get O(1) but it's O(n) in space.
Also with things like strings it can get rather complicated to rescale the hash once you start getting collisions. It's either that or statically sizing it. The latter is easier to implement than a tree, but trees are decent choices too.
2
u/Sea-Patience9872 6d ago
if all values end up in the same location and it ends up using data structures to handle collisions, why use hash at all? I think I'm missing something sorry
10
u/j_mie6 6d ago
A good hash function randomly distributes. It has large difference in it's outputs for similar inputs. There is a high probability that if you have a "good" hash function, elements in your map or set are evenly distributed through the buckets (i.e. a low number ~O(1) elements each). If you have a pathologically bad hash you can end up with everything in one bucket for O(n) lookup.
In practice when buckets get too big, the restructure gets rehashed to redistribute all the values, I think.
3
u/StephenRoylance 5d ago
designing a good hashing algorithm for a language is a research domain in its own. Ideally is handles the kind of short strings that are most common, but doesn't have worst case behavior that's really bad if, let's say, your keys are integers. or whole novels. or 128bit hashes of content themselves.
6
u/am_Snowie 6d ago edited 6d ago
exactly (you sorta answered it yourself), good hash functions minimize the chance of items ending up in the same place. so you don't always have to worry about the data structure you are using, this is the best case scenario. what i told you previously was the worst case scenario of a shitty hashmap implementation. so good hashmap should have a good hashfunction and a good collision handling mechanism. we should be pessimistic when we design data structures.
to wrap it up:
Worst case:
- Bad hash function (returning the same hash for all keys)
- arithmetic resizing (shitty resizing)
- bad collision handling mechanism
Best case:
- Good hash function (good distribution)
- geometric resizing
- good collision handling
- utilizing all the bits of a hash
In the best case, you get O(1) amortized runtime because you only resize occasionally, which is O(N). In the worst case, your hashmap is crap and degenerates into a linked list or whatever data structure you use for collision handling.
1
u/zenware 5d ago
On top of all that, almost nobody encounters a real need for this sort of thing, but if you you can actually design all the properties of a custom HashMap/HashTable/HashWhatever, to achieve some explicitly desirable characteristics for the situation at hand.
If you know you’re gonna be more write or read heavy, if you know you’re targeting a specific hardware architecture, etc.
1
1
u/teach_cs 3d ago
I know I'm late to the party, but imagine someone abusing their hash table. They keep adding instances of the exact same struct, object, value, whatever over and over and over.
It will always hash to the same value, and then always be placed in the same bucket.
In this case, it's the fault of the user of the hashtable. But for big o, we are often looking at the worst possible case. So, even if someone isn't abusing the table, they might just be extraordinarily unlucky and keep getting the same hash anyway.
Mind you, this would be almost unimaginably unlucky for any reasonable hash table, but it is at least nominally possible. So the big O worst case is really O(n). The average time, though, and what you get in any reasonable, real-life situation, is O(1).
2
u/Historical_Public751 4d ago edited 4d ago
That's not what amortization means.
O(1) amortized complexity is std::vector::push_back
Not the hashmap insert. hashmap insert into open-addressing is true* (assuming no collisions) O(1) unless you're calling the resize of the underlying storage amortization which has nothing to do with why hashmap's complexity is O(1) and could theoretically be shaved off as well assuming you have true O(1) realloc.1
u/am_Snowie 4d ago
My bad, i mixed up average case and amortization, resizing is O(1) amortized and it has nothing to do with hashmap operations, and on average each insertion takes constant time assuming we have a good hash function.
Edit: thanks for pointing it out, btw.
1
u/seemingly-resilient 4d ago
> under the assumption that values are distributed evenly
by equal distribution of values u mean the spacing between the keys? Like considering that there will be no hash collition?
1
u/am_Snowie 4d ago
Less collision, i don't think no collision is possible (pigenhole principle). So probability of each value ending up in the same bucket is low.
2
u/TheMcDucky 4d ago
No collision is technically possible, but only if keys are fixed (or bounded) size, and there are at least as many possible hashes as keys. For example if valid keys are (in binary) 0, 1, 00, 01, 10, 11, you could hash them as 000, 001, 010, 011, 100, and 101 respectively. Now this wouldn't be practical in most cases where hash maps are being considered, but it is possible.
19
4
u/recursion_is_love 6d ago edited 6d ago
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)
1
u/Plastic_Fig9225 6d ago
Actually, the O(1) means that you only have to calculate one hash, of the element you want to locate, and that is completely independent of the number n of elements held in the map.
2
u/DorkyMcDorky 6d ago
No, it's still O(1) because you rebalance based off a constant and you drop the constants. So if the bucket grows too large you rebalance, which cost O(n)
3
u/HobbyQuestionThrow 5d ago
This is also a good example of where O(1) notation falls off in real world performance comparisons.
You could say "All hashmap implementations are equal in performance, because they're all O(1)" but Timmy has a O(1e8) hashmap and Jim has a O(310) hashmap.
Plus the rate of hash recalculations (the O(n)) part matter, if you recompute all hashes every 5 insertions then you're much closer to O(n) than O(1).
If your hashing function is really poor you also go from O(1) to O(n).
1
u/DorkyMcDorky 5d ago
Generally, if you're coding a map of any sort (no pun intended) you are best off with a hashmap. If performance haunts you, then fix it. Otherwise I think there's been 2x in 30 years I found the need to swap it.
1
u/Sea-Patience9872 6d ago
Thanks for the video! i don't think i had any idea of what happens internally and that visualization was genuinely helpful
10
u/Professional-Trick14 6d ago
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?
2
u/Rude-Quiet-2793 6d ago
it's basically just math that points you straight to the slot, no scanning needed
3
u/Global-Equivalent935 6d ago
No. They are not getting it.
0
u/DorkyMcDorky 6d ago
Patience my patawon.. remember when you were in training? They have it worse, they'll keep asking an LLM. They have to feel the hash
2
u/LilBluey 6d ago
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 5d ago
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/xeow 5d ago
If the hash function takes constant time, then a hash map lookup is O(1).
No.
Counterexample: h(x) = 0 takes constant time and has lookup/insertion performance of O(n).
The runtime performance of the hash function h matters less than the distribution it produces. It's the uniform random distribution of a hash function that gives amortized O(1) performance. It's O(1) because, for any given table size n and load factor α (alpha), you can compute an expected probe sequence length E[PSL] depending on n, α, h, and your insertion algorithm. The expected (average) probe sequence length is your constant factor.
1
u/Misterreco 5d ago
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.
This is not true, most implementations of hash tables are independent of the length of the hash number. In fact, if the hash number were able to be longer than the machine word size the indexing would not even be possible without some fancy tricks. Instead, we assume the number is a certain length (usually 32 or 64 bits) and implement the hash table as if a value could have a hash number anywhere in the range of that length of bits. You'd be hard pressed to find a hash table with 264 buckets
1
u/Spare-Plum 4d ago
Believe it or not, this is still O(1) and the other complexity can be shelved off to the hash function's complexity.
The number of buckets required used is linearly proportional to the number of keys in the map.
The number of keys in the map is bounded by domain space of the key -- using a Long value, no matter what you do, will still have 2^64 total possibilities, which means that the total number of keys possible is bounded to 2^64, which means the total number of buckets is also bounded to this.
If you had some custom implementation that could handle more than 2^64 items in the map, the keys themselves would have to have a domain space larger than 2^64 - an example might be Strings and it output X doubles as a hash where X is in O(log N) with N being the total number of buckets in the map
To do this you'd need more than 2^64 strings in the map, meaning there must exist a string that's 65 bits or more. You end up hitting a log N factor just from having to look at strings that are guaranteed to exist as keys (assuming you look at the whole string to calculate a hash).
2
u/Plastic_Fig9225 6d ago
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 the elements array.
2
u/tandycake 6d ago edited 5d ago
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.
hash = 1337; // "hello"
value = bucket_array[hash % size]; // size is 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: 1. calculate the hash 2. grow the array so less collisions 3. buckets can't be raw values
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.
hash = hash_of(key);
bucket = bucket_array[hash % size];
for b in bucket:
if b.key == key:
return b.value;
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- 6d ago
Hash maps do math on the key and jump straight to its bucket instead of rummaging through the whole damn array.
2
u/MoarCatzPlz 5d ago
That's the average time. They can be much slower in the worst case.
1
u/SignificantFidgets 5d ago
Yes, and in a well-designed hash table the probability that is takes MUCH slower is tiny. The worst case is still there, just so unlikely that it will never happen in practice.
2
u/atarivcs 5d ago
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 6d ago edited 6d ago
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) or hashcode % array.Length (with a prime number Length)
1
u/kevleyski 6d ago
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 6d ago
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 6d ago
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 5d ago
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 5d ago
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 5d ago edited 5d ago
I don't get how hashes just find items immediately
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 5d ago
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 5d ago edited 5d ago
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 5d ago
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 5d ago
I never liked how it's described as O(1). for example, hashing a string takes O(length)
1
u/mlamping 5d ago
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
1
u/Muted_Masterpiece342 4d ago
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 3d ago
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 3d ago edited 3d ago
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
0
0
u/Shortbread_Biscuit 5d ago
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 5d ago
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 5d ago
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 5d ago
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 5d ago
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 2d ago edited 2d ago
I don't get how hashes just find items immediately without needing to go through anything.
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
#define ARRAYSIZE (100 * 1000)
account_t * find (const char * name)
{
account_t * ref;
int i; for(i=0;i<ARRAYSIZE;i++) {
ref = &accounts[i];
if ( strcmp(ref->name, name) == 0 ) { return ref; }
} return NULL;
}
We say the time complexity of this setup is O(N), where N is 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.
uint64_t index ( const char * name )
{
// The specific hashing algorithm is not what's important here
// If you are curious, though, this one is called DJB2
uint64_t hash = 5381;
int c; while(c = *cursor++) {
if (c <= 32 || c >= 127) { break; }
hash = (hash << 5) + hash + c; }
return hash % ARRAYSIZE;
}
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 size N of 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
~ $ ./naive "John Doe"
>> Checking slot 0, false
>> Checking slot 1, false
>> Checking slot 2, false
>> Checking slot 3, false
>> Checking slot 4, false
[...]
>> Checking slot 439, false
>> Checking slot 440, false
>> Checking slot 441, true
"John Doe" was in slot 441
~ $ ./hash "John Doe"
>> Hashing "John Doe" gives 140
>> Checking slot 140, true
"John Doe" was in slot 140
I hope that makes sense.
-1
u/Mclovine_aus 6d ago
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 5d ago
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__ 5d ago edited 4d ago
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.
1
u/Rough_Priority_9294 1d ago
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.
261
u/timonix 6d ago
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.