Ways To Sort A Hash Map

1. HashMap + Heap
   • Add: $O(logn)$
   • Get: $O(1)$
   • Trade off:
     • When removing element on a map would be a problem, reshifting the whole heap would be $O(nlogn)$
     • Concurrency would be a problem because need to maintain 2 datastructures
2. TreeMap — Red Black Tree for implementing
   • Add $O(logn)$
   • Get $O(logn)$
   • Trade off
     • Not $O(1)$ retrieval
     • Concurrency would be a problem as well because hard to control the locks on tree branches
3. ConcurrentSkipListMap — Skip List implementing of a map — use linkedlist with multiple level for fast accessing
   • Add $O(logn)$
   • Get $O(logn)$
   • Trade off
     • Not $O(1)$ retrieval
     • Concurrency would be easier and support out of the box by java