That's why I said "good hash table". Even a simple open-addressing hash table with quadratic probing can easily go to load factor 0.8 with reasonable performance. With cuckoo-hashing you can get much higher and still guarantee worst-case constant-time lookups and amortized constant-time insertions.
