CODEWITHSUNDEEP
javasortingoptimizationhashmaptreemap
TA-25
TA-25

Reputation: 11

Add to hashmap in sorted fashion (Java)

Hashmaps take O(1) to get stuff or remove it. If I want to sort it it will take nlogn time with Collections.sort(). If I use a treemap instead it sorts them while adding them so I don't have to spend nlogn sorting but it takes nlogn finding stuff. Hence the question is can I manually control the hashmap put method so that it doesn't use the hashcode way but instead sorts them with comparable? I am seeking O(1) for a program that uses hashmaps to do many insertions and removals and also much sorting.

Upvotes: 0

Views: 70

Answers (1)

Diasiare
Diasiare

Reputation: 755

Sorting n items will (in almost every case) take O(n log n) time. This is a provable fact. See Wikipedia on Sorting for a lot of information on the bounds on sorting algorithms.

Upvotes: 2

Related Questions