HashMap sorting by object (both key and value)

Hashmap is key-value pair data structure. HashMap is easy to use. After you initialize a HashMap, you can simply call put() and get() in Java to save and retrieve values. In JavaScript the methods are set() and get(); In Python, the map works as array using [k]. Instead of index, k is key. Both put and get methods have O(1) complexity. HashMap or Map is one of the most used data structures.

HashMap diagram

The key and value can be any data type. The most common used data types are String and Integer. You can also use custom defined object as key or value. In this post, Hashmap sorting with object shows how to sort HashMap by key or by value when either key or value is object .

Table of Content


1. Define the class

The first step is to define the class, which will be used as key or value in the HahsMap. In Java, in order to sort, you have to implement comparable interface. To use comparable, the class needs to add “implements Comparable” when define the class, and implement compareTo() method. This method takes one parameter of object and return the differences of the field you want to compare.

In this example, we define a class Fruit. It has three attributes, name, price and origin. To sort by the price, we can override the compareTo (Fruit obj), and return this.price – obj. price for ascending. Return obj.price – this.price for descending.

In JavaScript or Pyton, you don’t need to implements Comparable or compareTo() method. It will be done by using lambda when call sort().

Java

JavaScript

Python


2. Sort by key when object is the key

After we define the class, we can use it as the key in the Map. In Java, the easy way to sort by key is using TreeMap. HashMap has no order when we call put(). TreeMap is a special kind of HashMap. It implements SortedMap interface. So it is sorted in the ascending order of its keys. It has complexity of O(logn).

TreeMap diagram

In this example, in order to sort by Fruit , we can simply declare the Map as TreeMap. We use Fruit as the key, the ship name as value. We call put() to add Fruit and its ship into the map. After all data have been added, we can iterate through all keys. The output shows all entries are ordered by the fruits’ prices.

In JavaScript, we use following lambda syntax to sort map by key, k represents key
newMap = new Map([…mapObj].sort(([k1,v1], [k2,v2])=> { return k1.price – k2.price; }));

In Python, we use following lambda syntax to sort map by key, x[0] represents key
newMap = sorted(mapObj.items(), key = lambda x: (x[0].price))

Java

JavaScript

Python

Output:
Mango 15.7 Philippines – Black Pearl
Banana 20.13 Hawaii – Mayflower
Orange 30.7 Florida – victory
Apple 40.09 Japan – Queen Mary

O Notation:
Time complexity: O(nlogn), n is the number of elements in hash.
Space complexity: O(n)


3. Sort by value when object is the value

Sort by value is a little more complicated than sort by key in Java. After you have all the data in the HashMap, you save the HashMap’s entrySet() to a list. Then call List’s sort method with comparator Entry.comparingByValue(). This will call the object’s compareTo() method defined in the class to sort all by values.

LinkedHashMap diagram

Now the list is sorted, you can loop through the list and save each entry to a LinkedHashMap. LinkedHashMap is another kind of HashMap. It keeps the inserting order. The complexity is the same as HashMap O(1).

In JavaScript, we use following lambda syntax to sort map by value, v represents value. Note it is sorted by the map object’s entries, not mapObject when sort by value.
newMap = new Map([…mapObj.entries()].sort(([k1,v1], [k2,v2])=> { return v1.price – v2.price; }));

In Python, we use following lambda syntax to sort map by value, x[1] represents value
newMap = sorted(mapObj.items(), key = lambda x: (x[1].price))

Java

JavaScript

Python

Output:
Black Pearl – Mango 15.7 Philippines
Mayflower – Banana 20.13 Hawaii
victory – Orange 30.7 Florida
Queen Mary – Apple 40.09 Japan

O Notation:
Time complexity: O(nlogn), n is the number of elements in hash.
Space complexity: O(n)


Download HashMapSortingByObject.java
Download HashMapSortingByObject.js
Download HashMapSortingByObject.py
HashMap object as key and sort (YouTube)
Hash table implementation

Comments are closed