Get this book -> Problems on Array: For Interviews and Competitive Programming
In our previous Rust Article, we explored wether Rust is an OOP language or not. In this article, we will dive into some of the Rust language's Standard Library, or std for short namely HashMap and BTreeMap along with basic operations like insert and delete.
Table of contents:
- What is a Map?
- Tree, Binary Tree and BST
- What is a Hash?
- BTreeMap in Rust
- HashMap in Rust
Let us get started with Rust Collections: HashMap and BTreeMap.
What is a Map?
Let's start by defining what a 'Map' is. In a very broad and general sense, mapping means taking a group of items and associating them somehow to another group. If you're familiar with some basic calculus, it's exactly what a function is.
For example:
F(x) = x + 1
This function 'maps' or links the X values with what is typically referred to as Y values. Every value of X goes to a value of Y.
In programming, a Dictionary is a good example of a map. You're linking or associating keys to values.
Tree, Binary Tree and BST
Tree
A tree is a data structure as seen in the image above. Each Node contains data and a key. The first node is called the Root node. From there, the rest of the nodes branch out. Nodes that are children to the same parent node are siblings. Nodes that have no children are called leaf nodes, located at the end of a particular branch. As you can see, the reasons why it's called a tree are obvious.
Binary Tree
A binary tree is another data structure based off of the Tree data structure. The main and only difference is that it only allows 2 children per node. In the above example, the nodes E, F and G all belong to the L node. That's 3 children, meaning it's not a Binary Tree. The following is a representation of a Binary tree:
Binary Search tree (BST)
A Binary search tree is a special kind of Binary Tree, in which after the root node, every node that's added is ordered. Lower values to the left, higher values to the right. And the pattern repeats for every node until the value is inserted in the right place. Take a moment to look at the following image and find the pattern.
BTree
A BTree has all the perks of the Binary Search Tree, but without the restriction of allowing only 2 children per node. For example..
What is a Hash?
This article does not cover the ins and outs of cryptography and hashing but we need to talk a bit about what a Hash is and what it does in order to then apply this basic knowledge in HashMaps.
A Hash is, essentially, a form of cryptography. In cryptography there are two ways of encrypting something. The one way encryption, or the two way encryption. What does this mean? Simple! One way encryption means data can be encrypted, but cannot be decrypted. Two way means you can encrypt and decrypt the data back and forth.
So.. Encrypting and decrypting is simple to understand. You encode a message to send it to someone and avoid anyone snooping being able to read it. Then the receiver decrypts it and gets the message. So you may ask, why would I ever encrypt something in a way that is really hard to decrypt? Valid question! The answer is simple. Sometimes we don't need to know what the message is. We only need to know that it is correct. The best example is password storing.
Back in the day, passwords were stored in simple text. Meaning, you registered to a website, and your password as-is went to a database. How can you know this happened or if this is still happening? (Let's hope not). If you try to recover your password from the website, and they are able to send you your password in plain text.. most likey they have it stored as is in a database.
Hashes come to solve this issue. A Hash is a one way function, that takes an input (with some optional added 'salt' or randomness added to it depending on the hash function) and returns an encrypted text. This has a few interesting characteristics (If the hash function is well crafted)
-
It's very very hard to reverse or guess a Hash. Meaning, you'd need to guess thousands upon thousands of inputs, get them through the hash function if you know which one it is, and then compare the resulting Hash.. This is extremely slow, and if the hash is good enough, it's simply not viable. (Some hashes would take longer than the time until the universe dies.. that's a long calculation!)
-
Changing a single character in the original password produces an entirely different hash. Meaning. "Hello" and "hello" produce entirely different hashes, not just a change in a portion of it.
-
Same input will always output the same Hash. So after registering, the website stores your hash, not your password. When you try to log in again, all the website needs to do is run your input text through the hash function and compare the hash, with the stored one. This way they can verify that the text is the same, without knowing the text! Nifty huh?
-
If the hash function is well crafted, it's really really hard to find two different inputs that produce the same hash. Is it possible? Yes, yes it is
-
You generally cannot predict what the hash will be before you run your hashing function. Meaning you cannot manually figure out the hash just from reading the input.
All of these benefits are dependent on the hashing function. If the function that processes the input into the hash is too simple, it can be easily figured out, broken and then you're at the mercy of your attackers.
PHEW that took a while. I hope you're still with me because the theory bit is over! So..
With that out of the way...
Rust Time!
Thankfully, Rust has already implemented some of these data structures and functionality into modules that are readily available in the std library!
BTreeMap in Rust
To bring the BTreeMap Data structure into the scope for your program, all you need to do is add the following at the top of your file.
use std::collections::BTreeMap;
Once we've brought the BTreeMap into scope... All done! We can start using it freely.
BTreeMap is defined as:
let mut rpg_party = BTreeMap::new();
mut is used to make the BTreeMap mutable and new() is used to defined a new object.
Element is inserted as:
rpg_party.insert("mage", "healthy");
We can check if an element exists or not as:
rpg_party.contains_key("druid")
An element is deleted as:
rpg_party.remove("bard");
The complete implementation in Rust involving BTreeMap is:
// type inference lets us omit an explicit type signature (which
// would be `BTreeMap<&str, &str>` in this example).
let mut rpg_party = BTreeMap::new();
// First we insert some keys and values...
rpg_party.insert("mage", "healthy");
rpg_party.insert("warrior", "healthy");
rpg_party.insert("rogue", "healthy");
rpg_party.insert("bard", "healthy");
// Do we have a Druid? Let's ask our BTree!
if !rpg_party.contains_key("druid") {
println!("You're missing a druid! You might want to look for one in the next tavern.");
}
// How big is our party?
println!("Your party size right now is: {}.", rpg_party.len());
// Let's remove one of our party members...
println!("Oh no! Your bard got drunk and is now incapable of coming with you any longer.");
rpg_party.remove("bard");
// How big is our Party now?
println!("Now your party size is: {}.", rpg_party.len());
println!("--------------------"); // Just for formatting reasons!
// Let's modify one of our values, we got ambushed!
println!("You've been Ambushed! Your warrior tanks some damage!");
for (key, value) in &mut rpg_party {
if *key == "warrior" {
*value = "wounded";
println!("{} is now {}", key, value);
}
}
println!("--------------------"); // Just for formatting reasons!
// Let's display our current Party status
for (key, value) in &rpg_party {
println!("{}'s status is currently: {}", key, value);
}
HashMap in Rust
Following the same vein, to bring the HashMap structure and functionality, you add the following to the top of your file!
use std::collections::HashMap;
A HashMap object is defined as:
let mut rpg_party = HashMap::new();
An element is inserted as:
rpg_party.insert("mage", "healthy");
An element is deleted as:
rpg_party.remove("bard");
Go through this complete Rust implementation to know about all operations:
// Type inference lets us omit an explicit type signature (which
// would be `HashMap<String, String>` in this example).
let mut rpg_party = HashMap::new();
// First we insert some keys and values...
rpg_party.insert("mage", "healthy");
rpg_party.insert("warrior", "healthy");
rpg_party.insert("rogue", "healthy");
rpg_party.insert("bard", "healthy");
// Do we have a Druid? Let's ask our BTree!
if !rpg_party.contains_key("druid") {
println!("You're missing a druid! You might want to look for one in the next tavern.");
}
// How big is our party?
println!("Your party size right now is: {}.", rpg_party.len());
// Let's remove one of our party members...
println!("Oh no! Your bard got drunk and is now incapable of coming with you any longer.");
rpg_party.remove("bard");
// How big is our Party now?
println!("Now your party size is: {}.", rpg_party.len());
println!("--------------------"); // Just for formatting reasons!
// Let's modify one of our values, we got ambushed!
println!("You've been Ambushed! Your warrior tanks some damage!");
for (key, value) in &mut rpg_party {
if *key == "warrior" {
*value = "wounded";
println!("{} is now {}", key, value);
}
}
println!("--------------------"); // Just for formatting reasons!
// Let's display our current Party status
for (key, value) in &rpg_party {
println!("{}'s status is currently: {}", key, value);
}
Here's the output for both code snippets.
As you can see, both code snippets are basically the same, only the structure is different.. So you may wonder, why would I choose one over the other?
Extremely simplified... If your keys have some sort of order, use BTreeMap. If not, and you just want a map.. Use a HashMap!
If you've made it this far...
Congratulations! We've made quite a journey since we've started. There are many uses for these Data structures but always keep in mind. No size fits all. Always be mindful of your data structure tool belt and choose the appropiate one for the issue at hand.
References:
For a direct link to the BTreeMap documentation, go through this guide on Rust documentation
For a direct link to the HashMap documentation, go through this guide on Rust documentation
Thank you for reading, and I'll see hopefully see you in our next destination in our Rusty journey!
