Skip to main content

Hash Map

Basic Concept​

  • Hash table is not the same as Maps
  • In Java，有一個Map的interface，裡面定義了一堆的key-value operations，而data structure如HashMap implement了這個interface
  • HashMap的get，put and remove都是O(1)，但不能反推Map的這些method都是O(1)。如TreeMap，這是Binary Tree Structure，它們是O(logN)

Basic Principles of Hash Tables​

  • 只是一個enhanced version的array
  • 可以在O(1)下用index來查找element
  • 由於Hash Table類似array，但需要用hash function把key轉變成index，再做insertion，deletion等操作

Hash Function​

  • Addition，Deletion，Search和Update等operation都需要用hash function來計算index
  • 如果hash function的complexity是O(N)，以上operation就會degrade到O(N)，因此它的performance是很重要
  • 另一樣很重要的是，hash function需要在相同input下產出相同output
  • 如何將key轉為integer？
    • 以Java為例，每一個Java object都有default的int hashCode()，default return value是object的memory address，globally unique integer

Hash Collision​

  • Inevitable，因為要map infinite space into finite index space
  • Solution1: Chaining
    • Underlying array of hash table: linked list
    • 當有多個不同的key map到同一個index時，這些key -> value就會存儲在這個linked list
  • Solution2: Linear Probing(Open Addressing)
    • 如一個key算出來的index值已經被別的key佔了，那麼就去index+1的位置看看，如果還是被佔了，就繼續往後找，直到找到一個空位置為止