Hash Table

Hash Table（哈希表），是透過 Hash Function 計算出一個 key 與 value 所對應的位置，進而建立雜湊表格，而後也能夠過雜湊函式來搜尋找出鍵值存放在表格的位置。

使用 Hash Table 有許多優點：

• 快速查找：能夠實現O(1)時間複雜度的查找操作。這是因為它使用哈希函數將鍵映射到數組的索引位置，使我們能夠迅速找到存儲的數據。
• 高效的插入和刪除：它同樣能夠實現O(1)時間複雜度的插入和刪除操作，只需經過哈希函數計算索引位置即可完成。
• 靈活的鍵值對存儲：可以存儲各種鍵值對，使它非常適合用於存儲和檢索數據。
• 空間效率高：空間利用率通常很高，因為它不需要像其他數據結構（如數組或列表）那樣預留大量的內存空間。

在 Kotlin 中 $ 符號讓我們可以透過字串使用變數

val name = "Alice"
val age = 30
val message = "My name is $name and I am $age years old."
println(message)

例如上述程式碼會輸出 My name is Alice and I am 30 years old.

class HashTable<K, V> {
    private val table: HashMap<K, V> = HashMap()

    // 將鍵值對添加到哈希表
    fun put(key: K, value: V) {
        table[key] = value
    }

    // 根據鍵獲取值
    fun get(key: K): V? {
        return table[key]
    }

    // 刪除特定鍵的值
    fun remove(key: K) {
        table.remove(key)
    }

    // 檢查哈希表是否包含特定鍵
    fun containsKey(key: K): Boolean {
        return table.containsKey(key)
    }

    // 返回哈希表中所有鍵的集合
    fun keys(): Set<K> {
        return table.keys
    }

    // 返回哈希表中所有值的集合
    fun values(): Collection<V> {
        return table.values
    }

    // 返回哈希表的大小（存儲的鍵值對數量）
    fun size(): Int {
        return table.size
    }

    // 檢查哈希表是否為空
    fun isEmpty(): Boolean {
        return table.isEmpty()
    }
}

fun main() {
    val hashTable = HashTable<String, Int>()

    hashTable.put("Alice", 25)
    hashTable.put("Bob", 30)
    hashTable.put("Charlie", 35)

    println("Alice's age: ${hashTable.get("Alice")}")
    println("Bob's age: ${hashTable.get("Bob")}")

    hashTable.remove("Charlie")
    println("Is Charlie in the hash table? ${hashTable.containsKey("Charlie")}")

    println("Keys in the hash table: ${hashTable.keys()}")
    println("Values in the hash table: ${hashTable.values()}")
    println("Size of the hash table: ${hashTable.size()}")
    println("Is the hash table empty? ${hashTable.isEmpty()}")
}

上面 Hash Table 所實現的函式包括：

• put(key: K, value: V)：將鍵值對添加到 Hash Table 中。
• get(key: K): V?：根據鍵獲取對應的值，如果鍵不存在則返回null。
• remove(key: K)：刪除特定鍵的值。
• containsKey(key: K): Boolean：檢查 Hash Table 是否包含特定鍵，返回布林值表示是否存在。
• keys(): Set<K>：返回 Hash Table 中所有鍵的集合。
• values(): Collection<V>：返回 Hash Table 中所有值的集合。
• size(): Int：返回 Hash Table 的大小，即存儲的鍵值對數量。
• isEmpty(): Boolean：檢查 Hash Table 是否為空，返回布林值表示是否為空。

Heap

Heap 是一種特殊的數據結構，通常用於儲存和管理具有特定順序的元素集合。堆通常用於以下兩個主要目的：

• PriorityQueue：Heap 常用於實現優先級佇列（Priority Queue），其中元素具有優先級，並且可以按照優先級的順序進行插入和取出操作。最小堆（Min Heap）和最大堆（Max Heap）是兩種常見的 Heap，它們分別按照升序和降序的方式組織元素。
• Heap 排序：Heap 排序是一種高效的排序算法，它通過首先將元素構建成一個Heap，然後依次將 Max Heap 或 Min Heap 的元素取出，實現排序。

使用 Heap 有許多優點：

• Heap 是一種樹狀結構，通常實現為二叉樹，稱為二叉堆。
• Min Heap 的根節點包含最小元素，Max Heap 的根節點包含最大元素。
• 在 Heap 中，父節點的值始終小於或等於（最小堆）或大於或等於（最大堆）其子節點的值。
• Heap 的插入和刪除操作的時間複雜度通常為 ，其中 是堆中元素的數量。
• Heap 的應用範圍廣泛，包括優先級佇列、圖算法（如Dijkstra和Prim算法）、堆排序等。

import java.util.PriorityQueue

fun main() {
    // 創建一個最小堆
    val minHeap = PriorityQueue<Int>()

    // 添加元素到堆中
    minHeap.add(5)
    minHeap.add(2)
    minHeap.add(9)
    minHeap.add(1)
    minHeap.add(6)

    // 獲取最小元素（堆頂元素）
    val minElement = minHeap.poll()
    println("最小元素：$minElement")

    // 輸出剩餘的元素，它們將按照最小堆的順序出列
    println("剩餘元素：")
    while (!minHeap.isEmpty()) {
        val element = minHeap.poll()
        println(element)
    }
}

所有 Code 可以在 Github 找到 ～

Reference

• 【Day9】[資料結構]-雜湊表Hash Table
• [資料結構] 堆積 (Heap)
• [DS-For Dummies] hash function implementation
• Heap Data Structures