ADT基礎（三）—— HashMap

• 2021 年 2 月 28 日
• 筆記
• 數據結構與演算法

ADT基礎（三）—— HashMap

1 哈希表

• 哈希表（hash table），也叫散列表，是一種非常重要的數據結構，應用場景及其豐富，許多快取技術（比如memcached）的核心其實就是在記憶體中維護一張大的哈希表。
• 在哈希表中進行添加，刪除，查找等操作，性能十分之高，不考慮哈希衝突的情況下（後面會探討下哈希衝突的情況），僅需一次定位即可完成，時間複雜度為O(1)。
• 存儲位置 = f(關鍵字) ，這個函數f一般稱為哈希函數，這個函數的設計好壞會直接影響到哈希表的優劣。好的哈希函數會儘可能地保證計算簡單和散列地址分布均勻。
  • 插入操作，利用哈希函數計算存儲位置存入。
  • 查找同理，通過哈希函數計算實際存儲地址，然後從數組對應地址取出即可。

2 哈希衝突

• 如果兩個不同的元素，通過哈希函數得出的實際存儲地址相同怎麼辦
  • 當我們對某個元素進行哈希運算，得到一個存儲地址，然後要進行插入的時候，發現已經被其他元素佔用了，其實這就是所謂的哈希衝突，也叫哈希碰撞。
• 哈希衝突的解決方案有多種:
  • 開放定址法（發生衝突，繼續尋找下一塊未被佔用的存儲地址）
  • 再散列函數法
  • 鏈地址法(HashMap採用)，也就是數組+鏈表的方式。

3 HashMap的實現原理

• HashMap的主幹是一個Entry數組。Entry是HashMap的基本組成單元，每一個Entry包含一個key-value鍵值對。

  static class Entry<K,V> implements Map.Entry<K,V> {
      final K key;
      V value;
      Entry<K,V> next;//存儲指向下一個Entry的引用，單鏈表結構
      int hash;//對key的hashcode值進行hash運算後得到的值，存儲在Entry，避免重複計算
  }
  

  

  • 簡單來說，HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希衝突而存在的。
    • 如果定位到的數組位置不含鏈表（當前entry的next指向null）,那麼查找，添加等操作很快，僅需一次定址即可
    • 如果定位到的數組包含鏈表。
      • 對於添加操作，其時間複雜度為O(n)，首先遍歷鏈表，存在即覆蓋，否則新增；
      • 對於查找操作來講，仍需遍歷鏈表，然後通過key對象的equals方法逐一比對查找。所以，性能考慮，HashMap中的鏈表出現越少，性能才會越好。
  • 其他內容，如put，get原理下次補充，參考博文

4 HashMap使用

Map< String, String> map = new HashMap<>();
map.put("aa", "@sohu.com");
map.put("bb","@163.com");  //map.put(k,v);
value = map.get("bb");  //map.get(key);

//通過Map.keySet遍歷
for (String key : map.keySet()) value = map.get(key);
//通過Map.entrySet遍歷
for(Map.Entry<String, String> entry : map.entrySet()){
    entry.getKey();
    entry.getValue());
}
//通過Map.values()遍歷所有的value
for(String v : map.values())  v；