It should be obvoius that hash table lookups are above O(1) as long as collisions exist. Tweaking the load factor can reduce the probability of collisions, but that's merely a constant factor to the lookup complexity. As to whether O(log(n)) is a good approximation for the average, we can certainly discuss that. It depends a lot on the algorithm, but https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... shows (first graph) that the reality is typically even above logarithmic for some reason.
> It should be obvoius that hash table lookups are above O(1) as long as collisions exist.
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).
