It's only O(1) until it gets full. Either you have hash buckets which take linear time to search through, or you do a linear probe like in the article. And if it outgrows hardware cashes, performance gets worse as O(log(n)), but that's not a feature of the algorithm itself.