[資料結構] Hash Table
在 JavaScript 中,可以用物件(object)來代表 Hash Table 的資料結構。
在 JavaScript 中還有 Map
,Map 和 Object 有一個很大的差別在於,物件的 key 只能是 string(若是其他的型別也會被轉成 string),但 Map 的 key 則可以是其他的型別;另外 Map 會抱持資料輸入時的順序,但物件是沒有順序性的。
在 JavaScript 中還有 Set
,它只會用來保存 key 而沒有 value。
觀念
- Hash Table 本身是一個陣列,裡面的每一個元素都是帶有 key-value 的物件,稱作 Buckets。
- 透過自訂的
hash
函式,可以決定新增的資料要放在 Hash Table 中的哪個位置。 - 當有不同的內容放到相同編號的 Buckets 時,會發生所謂的 collision,這時候相同 Bucket 內的資料,會透過 Linked List 的方式串接在一起。
- 當 insert 了相同 key 的資料時,會有更新的效果。
- 其中會包含的方法有:
hash
insert
get
,retrieveAll