Java, ConcurrentSkipListMap

Why there is no ConcurrentTreeMap in java? Because trees are badly parallelized, but it is easy to implement lock-free skip list with the same cost O(log(n)).

If you have no memory but still want hash table

Ordinary hash table has practical limit on load factor below 75%. If you want more consider Cuckoo hashing, using just three hash functions increases the load to 91%.