四、「雜湊對映」（Hash Mapping） 為一種資料儲存與搜尋的技術。若要存取某筆資料x，則先將 x 經過 hashing function 計算，得出 hashing address，再到 hash table 對應的 bucket 中進行存取 x 的動作。但是此方法利用 hashing function 將較大的鍵值空間對應到較小的實際記憶體空間，所以有可能會發生碰撞（collision），亦即不同的鍵值有可能對應到相同實際記憶體位置。故為了解決此問題，有的人會使用開啟位址法（open addressing），在碰撞時，另外找一個空的 bucket 來放置新的資料。尋找到空的 bucket 的次數將和此 hash table 的負載比率（load factor）α有關。舉例而言，若α=90%，則第一次找到的 bucket 是空的機率為 10%。試證明尋找到空的1bucket 的次數大約為  。（15 分）