Java HashMap is a hash table (key-value pairs, dictionary) data structure implementation of the Map interface, a part of the Java Collections framework

HashMap has the following features

  • Default load factor and initial capacity are 0.75 and 16 respectively. Their values are important to the HashMap performance as they can optimize the iteration performance and the number of resize and rehash operations

  • No guarantees to the iteration order

    The iteration performance depends on the initial capacity (the number of buckets) plus the number of entries. Thus, it's very important not to set the initial capacity too high (or the load factor too low)

  • No duplicate keys. Permits one null key and multiple null values

  • Hash collision problem is resolved by using a red-black tree data structure, since Java 8, to provide a separate chaining

  • Offers constant-time O(1) in average and linear-time O(n) in worst case performance for basic operations such as get, put, and remove

    The less duplicate hash codes, the better performance gain for the above operations

  • Key objects are compared based on theirs equals and hashCode implementation

    Value objects are compared based on theirs equals method implementation

  • Unsynchronized implementation. In multi-threading environment with at least one thread modifies the list, it must be synchronized externally

Lets walk through this tutorial to explore them in more details

The class hierarchy

HashMap implements the Map interface and inherits AbstractMap which also implements the Map interface

Declare a HashMap

As the result from the class hierarchy, you can declare a HashMap with the following ways

@Test
public void declare() {  
    Map<String, Integer> map1 = new HashMap<>();
    assertThat(map1).isInstanceOf(HashMap.class);

    HashMap<String, Integer> map2 = new HashMap<>();
}

Create and Initialize

  • Provide either Map.of or Map.ofEntries factory method, since Java 9, to the HashMap(Map) constructor to create and init a HashMap in one line at the creation time
@Test
public void initInOneLineWithFactoryMethods() {  
    // create and initialize a HashMap from Java 9+ Map.of
    Map<String, Integer> map1 = new HashMap<>((Map.of("k1", 1, "k3", 2, "k2", 3)));
    assertThat(map1).hasSize(3);

    // create and initialize a HashMap from Java 9+ Map.ofEntries
    Map<String, Integer> map2 = new HashMap<>(Map.ofEntries(Map.entry("k4", 4), Map.entry("k5", 5)));
    assertThat(map2).hasSize(2);
}
  • You can also initialize a HashMap after the creation time by using put, Java 8+ putIfAbsent, putAll
@Test
public void initializeWithPutIfAbsent() {  
    // Create a new HashMap
    Map<String, Integer> map = new HashMap<>();

    // Add elements to HashMap
    map.putIfAbsent("k1", 1);
    map.putIfAbsent("k2", 2);
    map.putIfAbsent("k3", 3);

    // Can add null key and value
    map.putIfAbsent(null, 4);
    map.putIfAbsent("k4", null);

    // Duplicate key will be ignored
    map.putIfAbsent("k1", 10);
    assertThat(map).hasSize(5);

    // The output ordering will be vary as HashMap is not reserved the insertion order
    System.out.println(map);
}

Learn more

Iterate a HashMap

  • You can iterate over HashMap key-value pairs by using either Java 8+ forEach(BiConsumer)
@Test
public void iterateOverKeyValuePairs() {  
    Map<String, Integer> map = new HashMap<>(Map.of("k1", 1, "k2", 2));
    map.forEach((k, v) -> System.out.printf("%s=%d ", k, v));
}
  • Iterate over HashMap keySet() or values() with Java 8+ forEach(Consumer)
@Test
public void iterateOverKeySet() {  
    Map<String, Integer> map = new HashMap<>(Map.of("k1", 1, "k2", 2));
    map.keySet().forEach(k -> System.out.printf("%s ", k));
}

Learn more

Retrieve and Filter

  • Use entrySet(), keySet(), values() to get the set of key-value mapping entries, set of keys and collection of values respectively
@Test
public void retrieve() {  
    Map<String, Integer> hashMap = new HashMap<>(Map.of("k1", 1, "k2", 2));

    Set<Map.Entry<String, Integer>> entrySet = hashMap.entrySet();
    assertThat(entrySet).contains(Map.entry("k1", 1), Map.entry("k2", 2));

    Set<String> keySet = hashMap.keySet();
    assertThat(keySet).contains("k1", "k2");

    Collection<Integer> values = hashMap.values();
    assertThat(values).contains(1, 2);
}
  • Get value by the specified key with get(key)
@Test
public void getValueByKey() {  
    Map<String, Integer> map = new HashMap<>(Map.of("k1", 1, "k2", 2));
    int value = map.get("k1");

    assertThat(value).isEqualTo(1);
}
  • Filter HashMap keys or values by using Java 8+ Stream API
@Test
public void filter() {  
    Map<String, Integer> map = new HashMap<>(Map.of("k1", 1, "k2", 2));
    Integer[] arr = map.values().stream().filter(v -> v > 1).toArray(Integer[]::new);

    assertThat(arr).contains(2);
}

Learn more

Examine, Add, Update and Remove

HashMap provides containsKey(key), containsValue(value), put(key, value), replace(key, value), and remove(key) methods to examine if a HashMap contains the specified key or value, to add a new key-value pair, update value by key, remove an entry by key respectively

@Test
public void containsPutReplaceRemove() {  
    Map<String, Integer> map = new HashMap<>(Map.of("k1", 1, "k2", 2));

    boolean containedKey = map.containsKey("k1");
    assertThat(containedKey).isTrue();

    boolean containedValue = map.containsValue(2);
    assertThat(containedValue).isTrue();

    map.put("k3", 3);
    assertThat(map).hasSize(3);

    map.replace("k1", 10);
    assertThat(map).contains(Map.entry("k1", 10), Map.entry("k2", 2), Map.entry("k3", 3));

    map.remove("k3");
    assertThat(map).contains(Map.entry("k1", 10), Map.entry("k2", 2));
}

Learn more

Objects comparing in HashMap

  • Internally, HashMap basic operations such as containsKey, containsValue, put, putIfAbsent, replace and remove work based on comparing element objects which depend on their equals and hashCode implementation

    In the following example, the expected results don't happen due to lack of equals and hashCode implementation on the user defined objects

    • hashMap.containsKey(new Category(1, "c1")) and hashMap.containsValue(new Book(1, "a")) should return true but false

    • hashMap.put(new Category(1, "c1"), new Book(1, "a")) should not but success

    • hashMap.replace(new Category(1, "c1"), new Book(2, "a")) and hashMap.remove(new Category(1, "c1")) should success but not

@Test
public void objectsComparingProblem(){  
    Map<Category, Book> hashMap = new HashMap<>();

    hashMap.put(new Category(1, "c1"), new Book(1, "a"));

    boolean containedKey = hashMap.containsKey(new Category(1, "c1"));
    assertThat(containedKey).isFalse();

    boolean containedValue = hashMap.containsValue(new Book(1, "a"));
    assertThat(containedValue).isFalse();

    hashMap.put(new Category(1, "c1"), new Book(1, "a"));
    assertThat(hashMap).hasSize(2);

    hashMap.remove(new Category(1, "c1"));
    assertThat(hashMap).hasSize(2);
}

static class Category {  
    int id;
    String name;

    Category(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

static class Book {  
    int id;
    String title;

    Book(int id, String title) {
        this.id = id;
        this.title = title;
    }
}
  • You can fix the above problem by overriding equals and hashCode as the below example
@Test
public void objectsComparingFixed(){  
    Map<CategoryFixed, BookFixed> hashMap = new HashMap<>();

    hashMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));

    boolean containedKey = hashMap.containsKey(new CategoryFixed(1, "c1"));
    assertThat(containedKey).isTrue();

    boolean containedValue = hashMap.containsValue(new BookFixed(1, "b1"));
    assertThat(containedValue).isTrue();

    hashMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));
    assertThat(hashMap).hasSize(1);

    BookFixed previousValue = hashMap.replace(new CategoryFixed(1, "c1"), new BookFixed(2, "b1"));
    assertThat(previousValue).isNotNull();

    hashMap.remove(new CategoryFixed(1, "c1"));
    assertThat(hashMap).hasSize(0);
}

static class CategoryFixed {  
    int id;
    String name;

    CategoryFixed(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        CategoryFixed that = (CategoryFixed) o;
        return id == that.id &&
                Objects.equals(name, that.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

static class BookFixed {  
    int id;
    String title;

    BookFixed(int id, String title) {
        this.id = id;
        this.title = title;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        BookFixed bookFixed = (BookFixed) o;
        return id == bookFixed.id &&
                Objects.equals(title, bookFixed.title);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, title);
    }
}

Sort a HashMap

Java doesn't have a direct API to sort a HashMap. However, you can do it via TreeMap, TreeSet, and ArrayList in conjunction with Comparable and Comparator

The following example uses comparingByKey(Comparator) and comparingByValue(Comparator) static methods of Map.Entry to sort an ArrayList by keys and by values respectively. That ArrayList is created and initialized from entrySet() of a HashMap

@Test
public void sortByKeysAndByValues_WithArrayListAndComparator() {  
    Map.Entry<String, Integer> e1 = Map.entry("k1", 1);
    Map.Entry<String, Integer> e2 = Map.entry("k2", 20);
    Map.Entry<String, Integer> e3 = Map.entry("k3", 3);

    Map<String, Integer> map = new HashMap<>(Map.ofEntries(e3, e1, e2));

    List<Map.Entry<String, Integer>> arrayList1 = new ArrayList<>(map.entrySet());
    arrayList1.sort(comparingByKey(Comparator.naturalOrder()));
    assertThat(arrayList1).containsExactly(e1, e2, e3);

    List<Map.Entry<String, Integer>> arrayList2 = new ArrayList<>(map.entrySet());
    arrayList2.sort(comparingByValue(Comparator.reverseOrder()));
    assertThat(arrayList2).containsExactly(e2, e3, e1);
}

Learn more

Conclusion

In this tutorial, we had a quick overview of HashMap hierarchy, features and operations. You can find below the full example source code