Storing Keys with Associated Values in Hash Maps

Hash Maps, also known as Dictionaries in some languages or Associative Arrays, are fundamental data structures used to store collections of key-value pairs. Each unique key in a Hash Map is associated with exactly one value. The primary advantage of Hash Maps is their efficiency in retrieving, inserting, and deleting data, typically achieving an average time complexity of O(1) for these operations.

How Hash Maps Work:
At its core, a Hash Map uses a hash function to compute an index (or "hash code") for each key. This index points to a specific location in an underlying array where the value (or a reference to it) is stored. When you want to retrieve a value, the Hash Map hashes the key, finds the corresponding index, and directly accesses the stored value. Collisions (when two different keys produce the same hash code) are managed through various techniques like chaining or open addressing, ensuring that each key can still be uniquely identified.

Why Use Hash Maps?
* Fast Lookups: Extremely efficient for quickly finding a value associated with a known key.
* Flexible Data Association: Allows associating arbitrary data (values) with unique identifiers (keys).
* Dynamic Size: Can grow or shrink as elements are added or removed.

Hash Maps in Rust (`std::collections::HashMap`):
Rust provides `HashMap` in its standard library (`std::collections`). To use a `HashMap`, both the keys and values must satisfy certain conditions:
* Keys: Must implement the `Eq` and `Hash` traits. `Eq` allows the Hash Map to compare two keys for equality (essential for distinguishing keys even if their hash values collide), and `Hash` provides the method to compute the hash code. Common types like `String`, `i32`, `bool`, and tuples of such types already implement these traits.
* Values: Typically need to be owned or implement `Clone` if you intend to take owned copies out of the map, or you can work with borrowed references. Values themselves don't need `Hash` or `Eq`.

Common Operations with `HashMap`:

1. Creation:
You create an empty `HashMap` using `HashMap::new()`.

2. Insertion (`insert`):
The `insert(key, value)` method adds a new key-value pair. If the key already exists, the old value is replaced with the new one, and the old value is returned as `Some(old_value)`. Otherwise, `None` is returned.

3. Retrieval (`get`):
The `get(&key)` method retrieves a reference to the value associated with the given key. It returns an `Option<&Value>`, which will be `Some(&value)` if the key exists, or `None` if the key is not found. This requires handling the `Option` enum.

4. Updating Values:
* Overwriting: Simply call `insert()` with an existing key to replace its value.
* Conditional Insertion (`entry().or_insert()`): The `entry()` method returns an `Entry` enum, which can be `Occupied` or `Vacant`. You can then use `or_insert()` to insert a value only if the key doesn't already exist, or `or_insert_with()` for more complex default value generation. This is very efficient for operations like counting occurrences.

5. Iteration:
You can iterate over all key-value pairs in a `HashMap` using a `for` loop. The order of iteration is not guaranteed to be stable or in insertion order, as it depends on the internal hashing and storage.

6. Removal (`remove`):
The `remove(&key)` method deletes a key-value pair and returns `Some(value)` if the key was present, or `None` otherwise.

Ownership and Borrowing:
When you insert keys and values into a `HashMap`, they are moved into the map, meaning the `HashMap` takes ownership. When you retrieve values using `get()`, you get a borrowed reference (`&Value`), not the owned value itself, unless you clone it or use methods that consume the map.

```rust
use std::collections::HashMap;

fn main() {
    // 1. Create a new HashMap
    // Here, keys are String (city names) and values are i32 (population estimates).
    let mut city_populations: HashMap<String, i32> = HashMap::new();

    // 2. Insert key-value pairs
    println!("--- Inserting Values ---");
    city_populations.insert(String::from("New York"), 8_400_000);
    city_populations.insert(String::from("London"), 9_000_000);
    city_populations.insert(String::from("Tokyo"), 13_900_000);
    city_populations.insert(String::from("Paris"), 2_100_000);

    println!("Current HashMap: {:?}", city_populations); // Debug print

    // 3. Retrieve values by key
    println!("\n--- Retrieving Values ---");
    let city_to_find = String::from("London");
    match city_populations.get(&city_to_find) {
        Some(population) => println!("The population of {} is: {}", city_to_find, population),
        None => println!("{} not found in the map.", city_to_find),
    }

    let non_existent_city = String::from("Berlin");
    match city_populations.get(&non_existent_city) {
        Some(population) => println!("The population of {} is: {}", non_existent_city, population),
        None => println!("{} not found in the map.", non_existent_city),
    }

    // 4. Update an existing value
    println!("\n--- Updating Values ---");
    let old_population = city_populations.insert(String::from("New York"), 8_500_000); // Overwrites
    println!("Updated New York's population. Old population was: {:?}", old_population);
    println!("New York's current population: {:?}", city_populations.get(&String::from("New York")));

    // 5. Conditionally insert/update using entry().or_insert()
    // If 'Beijing' isn't there, insert it. If it is, do nothing.
    println!("\n--- Conditional Insert/Update ---");
    let beijing_population = city_populations.entry(String::from("Beijing")).or_insert(21_500_000);
    println!("Beijing's population (possibly inserted): {}", beijing_population);

    // If 'Paris' is there, its value will be updated if we used `or_insert`
    // but `or_insert` returns a mutable reference, so we can modify it directly.
    let paris_population_entry = city_populations.entry(String::from("Paris")).or_insert(0); // If Paris existed, it gets its current value, else 0
    *paris_population_entry += 100_000; // Increment Paris population
    println!("Paris's updated population: {}", city_populations.get(&String::from("Paris")).unwrap());


    // 6. Iterate over the HashMap
    println!("\n--- Iterating Over HashMap ---");
    for (city, population) in &city_populations {
        println!("{}: {}", city, population);
    }

    // 7. Remove a key-value pair
    println!("\n--- Removing Values ---");
    let removed_london = city_populations.remove(&String::from("London"));
    println!("Removed London: {:?}", removed_london); // Should be Some(9_000_000)

    let removed_london_again = city_populations.remove(&String::from("London"));
    println!("Removed London again: {:?}", removed_london_again); // Should be None

    println!("Current HashMap after removal: {:?}", city_populations);
}
```