iT邦幫忙

2

【小馬的資結演算法秘笈】(15)Hash Table 簡介,平均O(1)時間查找的工具

哈囉~ 大家好,
跟大家介紹一種很有用的資料結構- Hash Table

想像我們現在要解這樣一個問題,
有一個集合S裡面有n個元素,
每個元素的範圍來自[1,u]
那麼要怎麼查詢一個元素x是否在S裡面?

看看學過的工具可以做的多快?
第一種方式是用BST:

  • 空間: O(n)
  • 查詢時間: O(log n)
  • 更新時間(插入新的元素): O(log n)

另外可以用一個大小為u個bit的vector,
第i個bit若為1,表示元素i在我們的集合S裡,則:

  • 空間: O(u) (在u大n小的時候很浪費空間)
  • 查詢時間: O(1)
  • 更新時間(插入新的元素): O(1)

Hash Table則可以截取上述兩種資料結構好處,做到:

  • 空間: O(n)
  • 查詢時間: 期望值O(1) (在糟糕的情況下,可能需O(n)的時間)
  • 更新時間(插入新的元素): 期望值O(1)

原理簡介

由於Hash Table使用現有的程式庫可以達到還不錯的效果,
我有些懶的研究Hash的細節,
只簡略記錄簡單的原理(Hash Table 大致相當於c++語言的map, unordered_map,python語言的dict)

  1. 建立一個大小為m的Hash Table,m的大小為θ(n)
  2. 構造一個Hash Function h: [1,u] -> [1,m]
  3. 對於每個在S裡面的元素s,把它放進Hash Table的格子h(s)裡面

未來要查找s是否在集合S裡面,
就去看s有沒有放在格子h(s)裡面就可以啦,
如果hash的效果要好,
就是儘可能不會有多個元素放在同一格

本文只概念性的介紹hash的概念,
細節相信大家可在網上查詢學習,
附上參考資料

參考資料

  1. geeksforgeeks- Hashing | Set 1 (Introduction)

尚未有邦友留言

立即登入留言