O(1) is completely missing the point of hidden constant factors. For many applications, like the one used in javascript, ruby or perl - map as objects with 3-7 short keys - hash tables are totally overblown.
For compile-time known keys you better create a perfect hash table, where the fastest could be a switch of pre-compiled word-aligned memcmp statements. http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an... Haven't done that yet with SIMD instructions, which should be much faster.
For mostly read maps (like e.g. for mysql applications) it's mostly faster to run-time compile a shared lib with a perfect hash table. Compilers are very fast with data-only.
For many other use cases a judy tree, compressed patricia tree, ctrie, HAMT, CHAMP or even a btree may be faster than a typical hash table. Esp. considering cache oblivious architectures. The modern swiss table doesn't look like an old-style hash table anymore, more like a patricia tree.
E.g. almost everything is faster than the default C++ hash table.
Also, there are Map implementations that don't have these performance characteristics, e.g. a TreeMap in Java which internally uses a red/black tree and thus provides logarithmic lookup and insertion. If I'm writing something that needs to do a lot of efficient lookups but only write "Map" in the spec, there's danger that the wrong thing will be used, and performance will suffer. It really does need a hashtable, not just a generic lookup interface.
In practice, the performance of a hash table definitely does depend on the number of entries because of the cache hierarchy and stuff like that.
I could easily be wrong about the theory: there are, of course, lots of different kinds of hash table and different ways you might formalise the meaning of "O(1)".
And logarithmic growth in the key size is definitely not as bad as logarithmic growth in the number of nodes in a tree to traverse, because going from calculating e.g. a key size of 28 to 29 bits is not a big deal at all, but going from 28 to 29 levels in your tree means an entirely new memory lookup to grab that one node. The hash calculation is always cheap, whereas traversing a tree thrashes caches -- you only need one memory lookup in a hashtable, whereas you need logN in a tree. Those lookups are orders of magnitude more expensive time-wise than the simple integer math involved in calculating the hash.
You actually get O(1) with perfect hash functions, but doing so requires choosing a hash function by the data set. This is normally only feasible for precalculated hash tables, not those that are being filled dynamically.
The modal number of buckets you have to look into (or the modal size of the linked list) is 1. If it's more than 1, then your hash table is too full, and you need to enlarge it. This is admittedly an expensive operation, but it still amortizes out to O(1). And if you know in advance how many elements will be in a hashtable (this is common), then you never even need to resize.
Another way of putting it: if you modify your practical program so that it runs on a theoretical machine that handles any size of input then you will probably find that another term appears in the execution time, one with a "log" in it, and that term eventually dominates when n gets big enough.
Yes, I am being a bit pedantic. But "O(1)" is mathematical notation and you have to be pedantic to do maths properly.
This doesn't follow at all. If the average number of lookups is 2 instead of 1, then it's O(2), which is O(1) because it's just a constant factor. The number of collisions needs to grow proportionally to the total number of elements being stored, which does not happen because the hashtable itself is also grown to keep the average number of collisions constant and low.
A hashtable that is 80% full has the same small number of collisions regardless of whether the hashtable has a thousand elements in it or a billion. Meanwhile, a BST would have to make 10 lookups in the first case and 30 in the second case -- that's logarithmic for you.
Your link shows lots of real performance figures which are dominated by CPU cache misses and other non-intrinsic factors. That's what's responsible for the reduction in performance on larger data sets, not anything intrinsic to hashtables themselves. If you look at the aforementioned first graph, the best hashmap performs at around at worst around 10ns up through ~200K elements, whereupon it blows out the fastest CPU cache and then takes around a max of 25 ns for the max size tested (~700M?). Factoring out the cache issue, it definitely does not look super-logarithmic to me. It might not even be logarithmic; I'd need to see raw data to know for sure (it's hard to tell by estimating from the graph).
Yes, the "hash" part is an implementation detail. The performance is also an implementation detail by the way. Often, tables will optimize for a different criterion such as memory efficiency. Lookup will be less efficient then. And, as another person noted, you cannot really expect O(1) from a hash table anyway.
Hashes are completely different things, the use of them is an implementation detail and not necessary.