Hi, and welcome! Today, we'll explore HashMaps, a data structure that organizes data as key-value pairs, much like a treasure box with unique labels for each compartment.

Imagine dozens of toys in a box. If each toy had a unique label (the key), you could directly select a toy (the value) using the label. No rummaging required — that's the power of HashMaps! Today, we'll understand HashMaps and learn how to implement them in Kotlin.

HashMaps are special types of data structures that utilize unique keys instead of indexes. When you know the key (toy's label), you can directly pick up the value (toy). That's how a HashMap works!

Consider an oversized library of books. With HashMaps (which act like the library catalog), you'll quickly locate any book using a unique number (key)!

Kotlin implements HashMaps through its standard library using both the mutableMapOf() and the hashMapOf() functions to hold data in key-value pairs. While both can create mutable maps, they have subtle differences:

• mutableMapOf() creates a mutable map with default settings, but it doesn't guarantee the use of a specific map implementation. In practice, it often uses a LinkedHashMap, which maintains the order of insertion.

• hashMapOf() specifically creates an instance of java.util.HashMap, which does not maintain any order of keys or insertion.

The choice between them depends on whether the order of insertion matters in your application. If order is crucial, opt for mutableMapOf(). Otherwise, you can use either as needed. Here's an example of creating a HashMap, functioning as a catalog for a library:

Kotlin
Copy to clipboard
1fun main() {
2    // Using hashMapOf
3    val libraryCatalog = hashMapOf(
4        "book1" to "A Tale of Two Cities",
5        "book2" to "To Kill a Mockingbird",
6        "book3" to "1984"
7    )
8}

In this HashMap, book1, book2, and book3 are keys, while the book titles serve as their respective values.

It's important to remember that the keys should be of a type that supports hashing and equality comparison. Examples include String, Short, Int, Long, Float, Double, Char, and Boolean. The values can be of any type.

HashMap allows you to access, update, or remove elements:

1. Accessing Elements: You can retrieve a book's title using its key directly: libraryCatalog["book1"] would return "A Tale of Two Cities." If the key isn't present, you'll get null.

   Kotlin
   Copy to clipboard
   1fun main() {
   2    val libraryCatalog = hashMapOf(
   3        "book1" to "A Tale of Two Cities",
   4        "book2" to "To Kill a Mockingbird",
   5        "book3" to "1984"
   6    )
   7
   8    // Accessing a book's title
   9    val title1 = libraryCatalog["book1"]
   10    println(title1 ?: "Key not found") // Output: "A Tale of Two Cities"
   11
   12    // Accessing a nonexistent key
   13    val titleNonexistent = libraryCatalog["book100"]
   14    println(titleNonexistent ?: "Key not found") // Output: "Key not found"
   15}

2. Adding or Updating Elements: Whether you're adding a new book to the catalog or updating an existing book's title, you'll assign a value directly using the key.

   For updating a title: libraryCatalog["book1"] = "The Tell-Tale Heart"

   For adding a new book: libraryCatalog["book4"] = "Pride and Prejudice"

   Kotlin
   Copy to clipboard
   1fun main() {
   2    val libraryCatalog = hashMapOf(
   3        "book1" to "A Tale of Two Cities",
   4        "book2" to "To Kill a Mockingbird",
   5        "book3" to "1984"
   6    )
   7
   8    // Updating an existing book's title
   9    libraryCatalog["book1"] = "The Tell-Tale Heart"
   10    println("Updated book1: ${libraryCatalog["book1"]}") // Output: "Updated book1: The Tell-Tale Heart"
   11
   12    // Adding a new book to the catalog
   13    libraryCatalog["book4"] = "Pride and Prejudice"
   14    println("Added book4: ${libraryCatalog["book4"]}") // Output: "Added book4: Pride and Prejudice"
   15}

3. Removing Elements: If book1 no longer exists, you can remove it using libraryCatalog.remove("book1").

   Kotlin
   Copy to clipboard
   1fun main() {
   2    val libraryCatalog = hashMapOf(
   3        "book1" to "A Tale of Two Cities",
   4        "book2" to "To Kill a Mockingbird",
   5        "book3" to "1984"
   6    )
   7
   8    // Removing an existing book from the catalog
   9    libraryCatalog.remove("book1")
   10    println("Removed book1: ${libraryCatalog["book1"]}") // Output: "Removed book1: null"
   11}

Kotlin provides several ways to interact with and manage your data in a HashMap:

Iterating over the HashMap: Loop through your HashMap to access each key-value pair in turn using Kotlin's idiomatic syntax.

Kotlin
Copy to clipboard
1fun main() {
2    val libraryCatalog = hashMapOf(
3        "book1" to "A Tale of Two Cities",
4        "book2" to "To Kill a Mockingbird",
5        "book3" to "1984"
6    )
7
8    // Looping over the HashMap
9    for ((key, value) in libraryCatalog) {
10        println("$key : $value")
11    }
12}

When run, this code may output:

Plain text
Copy to clipboard
1book1 : A Tale of Two Cities
2book2 : To Kill a Mockingbird
3book3 : 1984

Please note that the order of the output might differ because HashMap does not maintain any order of keys. It could be in any sequence, such as:

Plain text
Copy to clipboard
1book2 : To Kill a Mockingbird
2book3 : 1984
3book1 : A Tale of Two Cities

This unordered nature is a characteristic of the HashMap.

HashMaps are popular because they save time! Operations like adding, updating, and locating elements take average constant time, O(1), which means they require nearly the same amount of time regardless of the library size.

However, to fully understand this, let's delve into the concept of hash functions and the difference between average-case and worst-case scenarios.

A hash function takes an input (or "key") and returns a fixed-size numerical value (hashCode) that represents the original input. The idea is to distribute keys evenly across the array to minimize hash collisions, where two different keys produce the same hashCode.

For example, hash("book1") might return 123, and hash("book2") might return 456.

• Average-Case Scenario: In the average-case scenario, the hash function distributes keys uniformly across the HashMap. Thanks to this uniform distribution, the operations of adding, updating, or retrieving keys have a time complexity of O(1) because they involve a simple arithmetic operation and direct addressing.

• Worst-Case Scenario: In the worst-case scenario, a poor hash function could cause too many collisions, making the HashMap resemble a linked list. When this happens, operations degrade to O(n) time complexity because they involve traversing a list of n elements. Kotlin's HashMap handles collisions internally using a mechanism called separate chaining or, in some cases, a tree-based structure to mitigate performance degradation.

Understanding the balance between these scenarios helps in selecting or designing an effective hash function to maintain the desired performance of O(1) in average cases.

By leveraging well-designed hash functions and recognizing potential pitfalls, you can maximize efficiency and apply HashMaps effectively in your Kotlin programs.

Well done! You've mastered HashMaps, understood Kotlin's implementation of HashMaps through its standard library, learned their operations, and grasped the concept of time complexity. Now, gear up for some practice exercises to reinforce your learning using Kotlin's specific syntax and idioms. Happy coding!