Map和set是一種專門用來進行搜索的容器或者數(shù)據(jù)結(jié)構(gòu)，其搜索的效率與其具體的實例化子類有關(guān)。數(shù)據(jù)的一般查找方式有兩種：直接遍歷和二分查找。但這兩種查找方式都有很大的局限性，也不便于對數(shù)據(jù)進行增刪查改等操作。對于這一類數(shù)據(jù)的查找，Map和Set顯然是個好的選擇。

Map中存儲的是鍵值對（key和value），即每一個key都有一個對應(yīng)的value值，多個key可以有同一個value，但key只能有一個。Set中只存儲鍵（key）。

Set即數(shù)學(xué)上的集合，繼承于Collection接口；Map則屬于一個單獨的接口。

Java中實現(xiàn)Set接口的常用類有TreeSet和HashSet；實現(xiàn)Map接口的常用類有TreeMap和HashMap。

TreeMap底層是一顆紅黑樹（近似平衡的二叉搜索樹），搜索或修改數(shù)據(jù)的時間復(fù)雜度為O（log2N）。TreeMap存儲的數(shù)據(jù)為關(guān)于Key有序的，搜索或修改數(shù)據(jù)也通過比較實現(xiàn)。

HashMap底層是哈希桶，獲取或者操作數(shù)據(jù)的時間復(fù)雜度為O（1）。其存儲的數(shù)據(jù)無序。

TreeMap的key不可以為null，HashMap的key和value都有可以為null。

TreeSet和HashSet與上述相同，其底層通過TreeMap和HashMap實現(xiàn)。

由于TreeMap的時間復(fù)雜度高于HashMap，只要不要求有序，一般都使用HashMap。HashMap的存儲方式其實是通過某個函數(shù)得出的值直接存放在Hash表中相應(yīng)地址處。搜索時通過相同的函數(shù)拿到相應(yīng)數(shù)據(jù)。

哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希(散列)函數(shù)，構(gòu)造出來的結(jié)構(gòu)稱為哈希表(HashTable)(或者稱散列表)。

不管怎么設(shè)計哈希函數(shù)，總有可能有兩個不一樣的值計算得出相同的地址。這時就引起了哈希沖突。沖突是必然的，但應(yīng)盡可能地減少沖突。

沖突較多可能是由于hash函數(shù)的設(shè)計不合理造成的，因此設(shè)計哈希函數(shù)是應(yīng)該遵循一定的規(guī)則：

• 定義域必須包括所有需要存放的值
• 存放的地址空間應(yīng)該盡可能均勻
• 哈希函數(shù)應(yīng)該比較簡單

常見hash函數(shù)有：直接定制法、除留余數(shù)法、平方取中法、隨機數(shù)法、數(shù)學(xué)分析法等。其中直接定制法(Hash(key) = A * key + B)和除留余數(shù)法(Hash(key) = key % p(p < m)，m為分配的空間大小)比較常用。key可以通過hashCode()函數(shù)計算得出。

當(dāng)然，Hash函數(shù)設(shè)計的再巧妙，也無法避免沖突。當(dāng)沖突率很高時，需要降低負載因子，負載因子定義為：填入表中的元素 / 哈希表長度。

因此降低沖突的做法應(yīng)為增加數(shù)組的長度。

為了解決沖突問題，可以采用開放定址法。即當(dāng)發(fā)生沖突時，如果哈希表未滿，則放到下一個地址并存放。具體做法為線性探測法和二次探測法：

線性探測即當(dāng)發(fā)生沖突時，就存放在沖突位置的下一個地址（如果也沖突就繼續(xù)后放）。但這樣會造成數(shù)據(jù)集中在某一片區(qū)域。此時可以采用二次探測，當(dāng)發(fā)生沖突時，找下一個空位置的方法為：Hi = (H0 + i^2) % m。

除此之外可以采用鏈地址法，即哈希桶。把所有產(chǎn)生沖突的數(shù)據(jù)放在一個子集中，稱為一個桶，各個數(shù)據(jù)通過鏈表連接。當(dāng)沖突嚴(yán)重時，子集中數(shù)據(jù)較多，也可以把子集轉(zhuǎn)換為哈希表或搜索樹。

在Java中，當(dāng)沖突嚴(yán)重時，HashSet和HashMap中的鏈表會轉(zhuǎn)換成紅黑樹。

key雖然可以通過hashCode()計算得出，但不同的key有可能得到相同的hashCode，因此要確定key值是否相同還需要通過equals判斷。

如果要用自定義類作為 HashMap 的 key 或者 HashSet 的值，則必須覆寫 hashCode 和 equals 方

法，而且要做到 equals 相等的對象，hashCode 一定是一致的。即：