• 抽象的一種資料類型

  • 可以用任何方式來做出 Stack 或是 Queue

    • 可以用 array 或是 linked list 做出來

  • undo / redo button 會使用到 Stack 的資料結構

  • 想像 Stack → 洋芋片罐

    • 移除的話從最上面移除

  • 想像 Queue → 排隊

  • Hash Function

    • 密碼做加密

    • javascript 的 objectsa and arrays 已經被 hashed 過

    • 理解： 把一個值換成另外一個值

  • Hash Function I ：Division Method

    • m= hashtable size

    • n= # of elements to store into hashtable

    • 公式 Index = Key mod m

    • 衝突叫做 collison(有可能會發生)

    • 優點是速度很快，跟 Multiplication Method 比起來

    • 缺點 m 一定要 >= n

      • 大小不能是 2 的 p 次方

  • Collision and Load Factor

    • Collison：兩個或更多的 objects 被 hashed 成相同的 index

    • Load Factor：n/m

      • 通常介於 0 ~ 1

      • m 太小就容易出現 Collison

      • 如過這個值小的話： many empty spots

      • 如果這個值大的話：not too many collisions

  • Hash Function II： Multiplication Method

    • m= hashtable size

    • n= # of elements to store into hashtable

    • 公式 Index = [m(keyA % 1)}

    • A 是 根號 5 - 1 /2 ( 黃金比例? )

  • Handling Collisions

    • 處理 Collisions 的方法 → Chaining

    • 首先要知道不管用什麼 hash function 的方法都還是會有 collisions

    • 遇到其實就有所有 element 都放進 array 就好

      • hashtable → array of arrays

Stack

  • LIFO

    • Last in first out

  • 沒有 index number

  • 移除跟新增都只能從最上面

Queue

  • 加進去從後面，移除從前面

    • 想像排隊，後面來的人排隊伍後面

  • FIFO

    • Frist in first out

  • 沒有 index number

  • 新增 → Enqueue

  • 移除 → Dequeue

Hashtable

  • Key → 經過 Hash Function 轉成索引

  • Value → 存在對應位置

  • 沒有 index number（用 Key 取值）

  • 插入、查詢、刪除 → 平均 O(1)

  • 可能發生 Collision（碰撞）

    • Chaining：用 Linked List 存同一格

    • Open Addressing：往下一個空位找

  • 不保證順序

小結

Stack 跟 Queue 概念比較想像中單純，需要注意的地方是如何用程式語言去實作出來，意外困難的是 Hashtable 的部分，比我想像的還要複雜，之前對它的概念僅僅只有 key value 的資料結構，可以拿 key 取出 value 這樣，但其實背後還有很多原理再運行著，這塊還得多研究。