Hash

支持 O(1) find, O(1) delete, O(1) insert

java 裡有 Hash Map, Hash Table, Hash Set

Hash Table 是線程安全的，多線程訪問時此資料結構不會混亂

注意：

insert 的複雜度有可能是 O(size(key))，取決於 Hash function 的設計

Hash function 作用是將任意的 key 輸入，得到固定且無規律，並介於 0~capacity-1的整數

EX:

int hashfunc(String key) {
    int sum = 0;
    for (int i=0; i<key.length(); i++) {
        sum = sum * 31 + (int)(key.charAt(i));
        sum = sum % HASH_TABLE_SIZE;
    }
    return sum;
}

上面的簡單 hash function 對於每一位字元都進行運算，

這樣可以保證輸入不同的字元時有不同結果，輸入同字元時是相同結果

取 31 則是一種經驗，選一個質數

在好的 hash function都會有 collision

解決方法有兩個

1. closed hashing: 佔別人的坑
2. open hashing: 列隊

當 collision 率太高(> 10%) 則要做 rehashing

rehashing是對 hash list裡的每一個key下面的鍊錶元素都做一次重新計算

因此速度會相當慢，如果沒有加上 LOCK 則有可能會讓結構混亂(hash map)

java 的 hash map hash function 取模數是用 (h & (capacity-1)) 來做的

因為用 & 可以快速獲得計算結果

參考： 這篇 ＆ 這篇