Graphs (and trees - their special case) are data structures used in modeling complex problems such as finding an optimal route, exploring possible moves in a game, caching engines, modeling relations and more . That’s why they are very often the fundament of software engineer interview tasks in big companies - FAANG. Let’s implement some basic graph algorithms in Rust.

Rust - single ownership and self reference

Rust is a great programming language that achieves memory safety by forcing a single ownership model and borrow-checker mechanism. That is actually problematic for data structures that require referencing Self type e.g. graphs, trees, and double-linked lists. So it is impossible in Rust to express this:

One of the features I love in Rust is very explicit copying. Every potentially expensive copy (clone) is clearly visible and can be easily caught during code review even though a small piece of code has been changed. That is probably one of the biggest advantages of Rust over C++. Nevertheless, more experienced Rust programmers know that it is not always easy to judge if some clone is expensive or not. In this article, I would like to present Facebook’s solution for that problem - Dupe trait from Gazeebo crate .

Carbon, a new programming language by Google that was announced at CppNorth 2022 conference as part of the presentation “Carbon Language: An experimental successor to C++” by Chandler Carruth on July 22nd 2022 (link ). The news spread quickly over the Internet and a few friends reach out to me to ask about my opinion about it and if Rust is going to die because of the appearance of a new baby of a big player in this industry. Well, Rust is doing fine and I will summarize my thoughts about Rust, Carbon, and modern C++ (C++20 standard as of today).

I’m a huge Rust enthusiast and you can read more about it in my previous article . Today, I’m gonna show you 2 examples of how Rust can be used together with some existing C and C++ codebases. Rust was designed with its FFI (Foreign Function Interface) in mind so it allows cheap (or even zero cost) interoperability with C and C++. For both solutions (plain C and C++), I’ll demonstrate that we can call C/C++ and Rust code back and forth (pass Rust callback to C++ code). I’ll focus on performance, flexibility, and limitations too.

Usually, I’m skeptical about new technologies and programming languages. I take every novelty with a pinch of salt. Not because of the steep learning curve and lack of time but because I saw too many examples where promises were not delivered. The majority of the new technologies provided only minor improvements which were not really worth migration time.

When I heard about Rust for the first time, my feelings were the same: if you need strongly typed high-performance native language without GC, why not just modern C++11 (or newer) instead of a new language? Is it really worth creating a new language instead of providing a C++ library that can be added to existing projects? A few months ago, I finally dived deeper into Rust and started writing some code in it. Rust extremely positively surprised me and become my choice for high-performance applications. In this article, I would like to present to you my take on why Rust.

I love compilers! I cannot code without them. They can prevent entire classes of errors and warns if I accidentally try to do something stupid in the code.

Warnings

Besides compiling code and checking for type and syntax errors, compilers can also print useful warnings. I’m a fan of turning on all warnings and writing a “paranoidly” safe code just to avoid potential correctness and performance problems. While coding in C/C++, I use to use gcc with flag -Wall. But did you know that it doesn’t enable all warning as the name suggests?

Hash code is the crucial thing in hash-based algorithms like those used in hash maps and all problems come from that simple fact. Its efficiency is as important as the efficiency of the hashing algorithm itself. Let’s talk about those problems and how to solve them.

Why hash code can cause a problem?

The main problems are:

1. Implementation determines the collision probability. This is an important factor and people tend to forget or underestimate it.
2. hashCode() should be implemented together with equals(Object) method as they are used jointly. The perfect implementation of those methods should correspond to each other e.g. use the same fields/methods and the same precedence.
3. You can easily forget to modify those two methods when you add a new field or modify it partially. This can sometimes break the correctness of the program. Of course, beside the case when you don’t want to use the new fields for objects comparison and hashing.

Simple hash collision examples

Here is my list of simple hash collisions (based on OpenJDK 11):

Welcome back to Hash Code miniserie where you can read how the hash codes (non-cryptographic hashing algorithms) and hash collections work in different programming languages. This time let’s take a look under the hood of Java’s collections and Strings. How hash codes are generated for them? Let’s check it out.

Arrays

Arrays in Java do not provide its own hashCode() implementation - it uses Object default which can cause a lot of error as hash depends on reference (an instance), not on its value. Java also provides better implemenation via Arrays helper class. Let’s take a look into the code:

Welcome to the first article of the Hash Code miniserie where you can read how the hash codes (non-cryptographic hashing algorithms) and hash collections work in different programming languages. Every software engineer uses hash collections like Python’s dictionary, Java’s hash map or C++’s unordered map. You get them to know pretty early in your learning path as they are key data structures to solve many problems effectively but are you sure that you know them well? In this miniserie, I will shed some light on this subject.

Lombok is a Java library that generates boilerplate code for you during the compilation. You probably use it or at least heard how it can clean the code with annotations like @Data or @Value. So I am not going to write yet another article on how to use the most popular annotations. I am going to show you one of the two most underrated features in Lombok - @Cleanup.

@Cleanup

It is just (or maybe even) an alternative to try-with-resource introduced in Java 7. Wait. What? In Java 7? When was that? On July 28, 2011. Why am I writing about alternative to feature introduced natively in Java almost eight years ago? We will get back to it soon. Let’s see a simple example first. Copy input stream into output stream with Lombok: