For key lookup,. depending on the hashing algorithm for exactness, all hashmap lookups are evaluated as O(1).
You keep working off this assumption. This assumes a perfect hash function that has been optimized for the exact size of the table and key entries. I don’t see how JS could possibly do this for objects constructed and modified on the fly. Just saying something is “really simple” is not a cogent argument.
Your example requires you to perfectly fit the hashing function to the data being used. Even the example you give is not O(1). The fact that you mention recursion through a two dimensional data structure is a further nail in the coffin.
Yes, if you have a hash function perfectly matched to a predetermined set of data (an impossible assumption letting JS do it for you, on the fly, at runtime), your best time would be O(1). But the worst case is still O(n), which is what time complexity is supposed to measure. I’ll grant you that it will probably on average perform better than many O(n), but that is not usually what we concern ourselves with when we talk about algorithm analysis - we talk about worst cases. At least that was how I was taught. Yes, finding the bucket is O(1) and you seem to think it stops there. To quote Cornell University:
Hash tables and amortized analysis
We’ve seen various implementations of functional sets. First we had simple lists, which had O ( n ) access time. Then we saw how to implement sets as balanced binary search trees with O (lg n ) access time. Our current best results are this:
|
linked list, no duplicates |
balanced binary trees |
add (insert) |
O ( n ) |
O (lg n ) |
delete (remove) |
O ( n ) |
O (lg n ) |
member (contains) |
O ( n ) |
O (lg n ) |
What if we could do even better? It turns out that we can implement mutable sets and maps more efficiently than the immutable (functional) sets and maps we’ve been looking at so far. In fact, we can turn an O ( n ) functional set implementation into an O (1) mutable set implementation, using hash tables . The idea is to exploit the power of arrays to update a random element in O (1) time.
We store each element of the mutable set in a simple functional set whose expected size is a small constant. Because the functional sets are small, linked lists without duplicates work fine. Instead of having just one functional set, we’ll use a lot of them. In fact, for a mutable set containing n elements, we’ll spread out its elements among O ( n ) smaller functional sets. If we spread the elements around evenly, each of the functional sets will contain O (1) elements and accesses to it will have O (1) performance!
|
hash table |
add (insert) |
O (1) |
delete (remove) |
O (1) |
member (contains) |
O (1) |
This data structure (the hash table) is a big array of O ( n ) elements, called buckets . Each bucket is a functional (immutable) set containing O (1) elements, and the elements of the set as a whole are partitioned among all the buckets. (Properly speaking, what we are talking about here is open hashing , in which a single array element can store any number of elements.)
There is one key piece missing: in which bucket should a set element be stored? We provide a hash function h ( e ) that given a set element e returns the index of a bucket that element should be stored into. The hash table works well if each element is equally and independently likely to be hashed into any particular bucket; this condition is the simple uniform hashing assumption . Suppose we have n elements in the set and the bucket array is length m . Then we expect α = n / m elements per bucket. The quantity α is called the load factor of the hash table. If the set implementation used for the buckets has linear performance, then we expect to take O(1+α) time to do add , remove , and member . To make hash tables work well, we ensure that the load factor α never exceeds some constant αmax, so all operations are O(1) on average .
The worst-case performance of a hash table is the same as the underlying bucket data structure, (O( n ) in the case of a linked list), because in the worst case all of the elements hash to the same bucket. If the hash function is chosen well, this will be extremely unlikely, so it’s not worth using a more efficient bucket data structure. But if we want O(lg n ) worst-case performance from our hash tables, we can use a balanced binary tree for each bucket. [emphasis original]
Be sure to get to the last paragraph where it is saying exactly what I’ve been saying. You are glossing over your assumption of a balanced hash table with a perfect hashing function.
Even if I forgot what I was taught and assumed that complexity analysis is about best case, I still would have to make big unfounded assumptions about the efficiency of JS. JS is not an efficient language. It wasn’t designed for that. It has many strengths, but fast, efficient computation and data access is not one of them. All complexity analysis assumes the language being used is optimized for mathematical and data structure efficiency. JS is not. And the implementation of these things is not standardized across engines/browsers so the only way I could make a best case argument would be to pull a bunch of assumptions out of my butt.
Yes, I agree that if you personally pick the hashing function that is perfectly matched to your predefined data, you can pretty dependably get pretty close to O(1). Good luck finding those conditions in the real world. And if it is that important, then JS is possibly one of the worst languages to choose.
But again, it is asinine to imply that it matters at all in this specific case. This is a function that will run a few times with pauses, in a language that is so slow and inefficient anyway.
Do you have a more concrete argument than contradicting yourself, misrepresenting computer science concepts, and “because I say so”?
