Landy Blog
0%

資料結構-HashTable-Intro

發表於 更新於 分類於 ，
紀錄 Hash Table 的是由什麼構成的，與 Hash Table 裡的 node 有什麼屬性

Hash Table 的組成

本身是一個陣列，而每一個陣列元素都是一個 bucket。
每一個 bucket 儲存的資料型態會是 Linked List ，
而 Linked List 的每一個 node 所具有的屬性分別是 key,value, next。
Imgur

HashNode 的屬性功能分別為:

key: 代表這個 node 要儲存在 HashTable 裡面的哪一個 bucket
value: 這個 node 代表的值
next: 指向接在這個 node 的下一個 node 的位址，若這個 node 已經是 LinkedList 的最後一個 node，那這個 next 的值為 null

Hash Table 怎麼儲存 node

我們把 Hash Table 儲存 node 的過程，用圖片具象化
Imgur

以下是上圖 Hash Table 儲存新的 node 的過程:

  1. 這一個 Hash Table 是一個具有 10 個元素的陣列，也就有 10 個 bucket。
  2. 若我們要儲存上圖所示 key 為 Becka 的這個資料，
    會先判斷它應該要被放在 Hash Table 的哪一個 bucket 裡，上圖是把它編列為 8 ，所以，它會被放在 Hash Table 這個陣列的第八個的 bucket 裡。
  3. 若這個 bucket 裡面已經存有其他元素的話，就會以類似 Linked List 的方式，將資料串連在一起，並將新的資料加入至這個 Linked List 裡。

RunTime of Hash Table

Lookup: O(1)
Insertion: O(1)
如果今天要查找 key 值為 Jim 的資料，
第一，會先依照這個 key 值，來解析出其所位在的 Bucket 位置，以上面的範例為例，會解析出 8。
第二，我們就會去訪問第八個 bucket，接著，取得這個 Bucket 裡 key 值為 Jim 的資料。
以上這兩個步驟都是直接訪問目標元素，沒有經過遍歷整個儲存空間的操作，所以， Lookup 和 Insertion 的 Big O 才會都是 O(1) 。