[筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 26

重念一次早該補起來的「資料結構與演算法」。這篇筆記下 Hash Table (雜湊表)。

notes-theideaofalgorithm-javascript-1


課程相關資訊

[連結]:https://hiskio.com/courses/572/lectures/29850

本篇範圍:Chapter 8

請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。


內容

1. 若使用傳統的 array 儲存資料,由於資料連續的關係,你要找某一筆特定資料就會非常慢 O(n)
2. 若你使用 direct-addressed array 來儲存雖然可快速找到,但你得佔據大量的記憶體以確保 array 的連續性
3. Hashtable 的時間複雜度為 O(1)。
4. Hash Function 本質上就是把一個值,經由轉換而得到另外一個值。因此,若你將原始的 id 經由 hash function 變得小一些,那儲存的長度就可以變小,也不會佔用太多記憶體

Hash Function

Division Method

1. Index 為 Key mod m, m 為 hashtable size, n 為 # of elements into hashtable
2. 不免俗的,你會有機會得到衝突 collision
3. n/m 的值越大,越不容易發生衝突,這個比值稱為 load factor。因此這個值多半是會在 0 ~ 1 之間
4. m 一定要大於 n。這個值請記得要遠離 2^P (因為 10^P 可以被 2^P 整除)
5. 另外,你也要注意物件本身的名稱衝突


系列文章

  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 9
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 8
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 7
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 6
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 5
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 4
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 33
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 32
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 31
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 30
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 3
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 29
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 28
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 27
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 25
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 24
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 23
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 22
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 21
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 20
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 2
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 19
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 18
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 17
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 16
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 15
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 14
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 13
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 12
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 11
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 10
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 1
  • 按讚加入粉絲團

    延伸閱讀