Why you can't use HashMap in no_std?

Little bit of no_std

#![no_std] is a crate-level attribute that indicates that the crate will link to the core-crate instead of the std-crate.

Why do we need no_std? Because your system may be not provided with a system interface like POSIX which essentially provides you with kernal space operations like fifle system access, networking, memory management, threads and so on. The environemnt that provides such interfaces are commonly called Hosted Environments.

In Bare Metal Environments on the other hand, no code is loaded for your program and when you write a program for such environment, you use no_std to prevent the program from using standard library that comes with some system integration.

So, what does that mean?

Simply put, of the many other implications, one notable thing is you cannot use heap allocation that you would normally do in hosted environment such as:

• Use of Vec without memory allocator
• Use of HashMap and HashSet

Okay, we can understand why heap allocation becomes a problem but then since - CS101, operating system is in charge of memory allocation and resource management.

But then why you cannot ever use HashMap and HashSet?

How HashMap works

HashMap we use relies on a secure hashing algorithm that involves "random number generator(RNG)" to protect collision attacks. And this randomeness comes from the operating system's RNG (e.g., /dev/urandom on Unix-like systems or the Cryptographic API on Windows).

All of this suggest that you cannot use HashMap in no_std as it doesn't assume there is a application-OS interaction.

Why OS creates randomness?

Well, OS collects entropy from various hardward and system events. The canonical examples are:

• Timing Variations
• Interrupt Timing
• User Input
• System Clocks

And again, it just happens that OS takes the responsibility of centralizing entropy pool, and applications depend on them.