Hash Table

Intro

從別人的gist借來的重點整理:

Definition:

• Stores data with key value pairs.
• Hash functions accept a key and return an output unique only to that specific key.
  • This is known as hashing, which is the concept that an input and an output have a one-to-one correspondence to map information.
  • Hash functions return a unique address in memory for that data.

What you need to know:

• Designed to optimize searching, insertion, and deletion.
• Hash collisions are when a hash function returns the same output for two distinct inputs.
  • All hash functions have this problem.
  • This is often accommodated for by having the hash tables be very large.
• Hashes are important for associative arrays and database indexing.

Complexity

Hash Table的時間複雜度有夠讚，從下表最後一列可以看到他一片綠油油的O(1)，空間複雜度也沒特別高，感覺很好~

Question:

1. 為什麼Worst case的時間複雜度是O(n)?
2. Hash Table有沒有什麼不好用的地方?
3. 要怎麼Handle有collision的情況?
4. 為什麼在Java中，拿Object來做Hashing會有錯誤(舉例，同一個class、不同的instance - A & B，A 跟 B 的 data member一樣，但A跟B對應到的key不一樣)?

Answer:

1. 因為如果有collision，而且桶子又不能再增加，那就得在linked list裡面搜尋。
2. 這其實是個滿複雜的問題。最簡單的回答是，不該使用Hash Table的時候，例如想要handle一些有時間順序的data，queue顯然就是一個更好的選擇。再深一點的話可以說，如果希望儲存的data可以被排序，那Hash Table就會不太好用。有個不錯的討論串在討論這個問題。
3. 每個key後面接的value變成一個linked list，或是增加hash table的bucket數，讓collision不會發生。(可以看一下這個連結)
4. 本質的原因還不知道，不過已經知道解法是要實作class的equals()跟hashCode()，讓HashTable可以確保我們認為一樣的instance在Hash Table中也一樣。(Stack Overflow上的簡單說明，另一篇有詳細說明的文章)

Implementation:

public class HashEntry {
      private int key;
      private int value;

      HashEntry(int key, int value) {
            this.key = key;
            this.value = value;
      }     

      public int getKey() {
            return key;
      }

      public int getValue() {
            return value;
      }
}

public class HashMap {
      private final static int TABLE_SIZE = 128;

      HashEntry[] table;

      HashMap() {
            table = new HashEntry[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = null;
      }

      public int get(int key) {
            int hash = (key % TABLE_SIZE);
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            if (table[hash] == null)
                  return -1;
            else
                  return table[hash].getValue();
      }

      public void put(int key, int value) {
            int hash = (key % TABLE_SIZE);
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            table[hash] = new HashEntry(key, value);
      }
}