Hashing in Java vs. C++

👁 Image

Java and C++ are somewhat syntactically similar languages that have diverged over time. Java was loosely inspired by C++, but initially didn't adopt C++'s template structures, nor did it require C++'s header/content file separation, and of course, it used the JVM and compiled to bytecode rather than machine code.

Since then, the two languages have converged somewhat — they follow similar coding guidelines, support Lamda constructs, Generics/Templates, multiple identicals for loop syntaxes, and so on. There are certainly differences in modern use, however. C++ templates support specialization, while Java generics support type restrictions. They have similar base collection types as well.

You may also like: How HashMap Works in Java

Hash tables, hash maps, and similar types of data structures that allow indexing by a unique key, but that indexing is implemented in a very specific way. Now, any associative container type can give you access to data by a particular key. You can use a linked list as your storage structure, or a doubly-linked list, or a binary tree, for example. Hash tables use, essentially, an array, but that array is indexed by a hash value. Java has, as it's base associative container type, the  java.util.HashMap class. C++ has  std::unordered_map.

Hash-based containers have significant advantages for data storage. Both containers (HashMap and  unordered_map) have O(1) lookup performance when using hash generators that have a low probability of collision. The more likely collisions, the closer the performance of the container to O(n), where n is the number of elements stored in the container. Both containers use a standard hashing function as well — Java requires keys to implement Comparable, and via Map.Entry implement the hashCode() method. For common use, they are very similar as well.

For a C++ program, you'll include something like this:

#include <unordered_map>

std::unordered_map<std::string, unsigned int> empty_map;

empty_map["zero"] = 0;

Doing something similar in Java:

xxxxxxxxxx

import java.util.HashMap;

var emptyMap = new HashMap<String, Integer>();

emptyMap.put("zero", 0);

Accessing variables is similar too:

xxxxxxxxxx

auto v_0 = string_map["zero"];

std::cout << "zero value: " << v_0 << std::endl;

And in Java:

xxxxxxxxxx

var zero = map.get("zero");

System.out.println("empty map zero: " + zero);

There are other common uses for hash structures other than putting/getting though. Another typical use involves storing string keys and specific values associated with those keys, where the key has some kind of semantic value (like a name, for example). When you do this kind of thing, you usually want to grab a collection of keys that you can then process to find a specific value. This kind of operation looks like this:

xxxxxxxxxx

for (const auto& pair : string_map) {

    std::cout << "key is: " << pair.first << std::endl;

}

And again in Java:

xxxxxxxxxx

for (final var k : emptyMap.keySet()) {

    System.out.println("key is: " + k);

}

We do have some C++-isms creeping in — specifically the use of a reference object in the loop. Still, things are very similar between the two languages.

The final case I'm going to take a look at is how you can apply an algorithm over all the elements of a map. First, C++:

xxxxxxxxxx

std::for_each(

    string_map.begin(),

    string_map.end(),

    [&](auto& p){

        ++p.second;

        std::cout << p.second << std::endl;

    }

);

Then Java:

xxxxxxxxxx

emptyMap.forEach((k, v) -> {

  ++v;

  System.out.println(v);

});

The Java version is certainly a bit terser. These two approaches also show a distinct difference in design philosophy.

The C++ version uses an external algorithm from the standard library in order to apply the lambda expression to the pairs in the map. In modern C++, classes are designed with a strict type-centric perspective. Here, the for_each(.) algorithm can be applied to any number of containers and is designed in that way. Furthermore, as it isn't intrinsic to the  unordered_map type, it is actually defined as an external function. The Java HashMap class, on the other hand, includes the forEach() method.

Anyway, that's a brief overview of common operations over Java and C++ hash map types, highlighting some of the similarities and differences between the two.

Happy coding!

Further Reading

How HashMap Works in Java

Optimizing a Hashing Strategy

Java Hashing: From Overriding HashCode to Mutable Objects