Toro的murmur花園

在一個有序或無序的線性串列中，要尋找一筆資料通常要透過特定的搜尋資料與比對方式 ，如果資料量很大，花費在搜尋上的時間成本也就隨之增大。

hashing是一種鍵值與陣列索引的對應，我們透過特定的hashing函式，將指定的鍵值經過運算而得到一個hashing code，這個hashing code就當作是陣列的索引，資料就儲存在這個索引的位置中。

要得到hashing code的運算方式有很多種，像是中間平方法、除法、摺疊法等等，無論是哪種方式，都有可能在兩種不同鍵值，卻得到相同hashing code的情況，這個時候稱之為碰
撞（collision），解決碰撞的方式也有許多種，最簡單的就是直接往hashing code所指向的位置之下一格作線性探測，直到找到空間為止，另外還有就是使用鏈結串列，當碰撞發生時，就將新的元素以鏈結的方式加在同一個位置的後面（這也是Java中的Hashtable類別所採取的方式），影響hashing效能的因性之後稱之為load factor，它的計算方式是hash table中的元素除以可容納的空間大小，load factor越接近1，表示hash table中的元素越多，發生碰撞的機率也就越大。

無論如何，製作一個hash table是相當麻煩的，然而Java的Hashtable類別可以讓您無需注 意這些細節，在不發生碰撞的狀況下，使用hash table可以一次運算就找到所要的資料， 然而這並不是沒有代價，因為使用hash table就是一種以空間換取時間的方式，使用Hashtab le會耗用較多的記憶體，因為要預先空出一個夠大的空間來當作hashing code的對應空間 。