參考：算法第四版
目錄
1.散清單
1.1什麼是散清單？
1.2 散列函數:
1.3 解決沖突：
2.HashMap解析
3.leetcode中的散清單
3.1 leetcode1 twosum，兩數之和
3.2 leetcode242 valid-anagram
3.3 leetcode49 group-anagrams
1.散清單
散清單：一種符号表，又叫哈希表，java中HashMap的底層資料結構。
符号表：一般存儲鍵值對(key-value)，一般用這種資料結構通過key來找到對應的value，可以将其看作字典,key和value一一對應。
1.1什麼是散清單？
想象我們要存儲一個11位電話号和其對應的人名，我們申請一個大小為1000的數組map，取電話号碼的後3位為數組索引，比如小明的電話号碼為12345678987，其後三位為987，則将小明(value)和其電話号碼(key)存入a[987]中。以後如果想要尋找12345678987的主人時，隻要先對12345678987取後三位,得到987，然後去a[987]的位置去尋找有沒有對應元素，有則取出value即可。
這就是散清單，将一個鍵值對的鍵映射成一個數組的索引(如果數組大小為M，則映射出的值在0-M-1之間)，然後存放到對應位置的一種資料結構，将鍵映射成索引的方法就叫散列函數，前面的電話号碼取後三位就是一種散列函數。但散列函數可能會将不同的key映射成相同的數組索引，将這兩個先後插入數組中時，因為數組中本來就有元素，就會發生沖突，這時候就需要解決沖突的方法。散列函數和解決沖突的方法組成了散清單。
1.2 散列函數:
對于java庫中的類，因為java中每個類都會從共同父類Object類中繼承一個hashcode函數，庫中的類都會重寫一遍，是以hashcode()函數會傳回一個32的int,可以在其基礎上進行散列，一般取餘即可，但需要注意hashcode()可能傳回負數以及可能溢出。可以像下面一樣實作：
private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % M; //M為散清單大小，直接key.hashCode()%M可能傳回負數
//直接加個絕對值可能會溢出，因為32位int的範圍為-2^31~2^31-1，如果正好為-2^31時，絕對值為2^31就溢出了。
}
以上代碼會将符号位屏蔽，達到了取絕對值和防止溢出的結果。
對于自己實作的類，如果沒有重寫hashcode函數，預設的hashcode函數是傳回類的記憶體位址，因為程式中的記憶體位址可能就那一塊，可能會導緻資料分布不均勻，沖突增加，是以一般都需要自己重新hashcode函數，hashcode函數一般采用31法來實作，如下是自定義的一個交意類的hashcode實作
public final class Transaction implements Comparable<Transaction>
{
private final String who;//交易人
private final Date when;//交易時間
private final double amount;//交易數量
public int hashCode()
{
int hash = 17;
hash = 31*hash + who.hashCode();
hash = 31*hash + when.hashCode();
hash = 31*hash + ((Double) amount).hashCode();
return hash;
}
}
java中的String類的hashcode也是采用的類似方法
public final class String
{
private int hash = 0;
private final char[] s;
...
public int hashCode()
{
int h = hash;
if (h != 0) return h;//不等于0，說明已經計算過了，緩存
for (int i = 0; i < length(); i++)
h = s[i] + (31 * h);
hash = h;
return h;
}
}
1.3 解決沖突：
一般常用的解決沖突的方法有連結清單法和開放尋址法。
連結清單法即數組每個位置存放的不再是一個鍵值對，而是一個鍵值對的連結清單，如果發生沖突時，隻要将鍵值對放到連結清單的末尾即可。
開放尋址法即發生沖突時，往後移一個位置放新的鍵值對，如果還是有元素，再往後移，直到位置為空。
下面是連結清單法和開放尋址法的java實作：
public class hashtable <Key extends Comparable<Key>,Value>//連結清單法實作散清單
{
Node<Key,Value>[] table;//散清單數組
private int capcity;//散清單大小
hashtable(int n)
{
table = new Node[n];
capcity = n;
}
private class Node<Key extends Comparable<Key>,Value>//連結清單節點
{
Node(Key key,Value value)
{
this.key = key;
this.value = value;
}
Key key;
Value value;
Node next;
}
void Put(Key key,Value value)
{
int index = (key.hashCode() & 0x7fffffff) % capcity;
if (table[index] == null)
{
table[index] = new Node(key,value);
return;
}
else
{
for (Node cur = table[index];; cur = cur.next)
{
if (cur.key.compareTo(key) == 0)
{
cur.value = value;
break;
}
if (cur.next == null)
{
cur.next = new Node(key,value);
break;
}
}
}
}
Value get(Key key)//取值
{
int index = key.hashCode() % capcity;
if (table[index] == null) return null;
else
{
for (Node cur = table[index];; cur = cur.next)
{
if (cur.key.compareTo(key) == 0)
{
return (Value) cur.value;
}
if (cur.next == null)
{
return null;
}
}
}
}
}
public class LinearProbingHashST<Key, Value>//開放尋址法實作
{
private int M = 30001;
private Value[] vals = (Value[]) new Object[M];
private Key[] keys = (Key[]) new Object[M];
private int hash(Key key) { /* as before */ }
public void put(Key key, Value val)
{
int i;
for (i = hash(key); keys[i] != null; i = (i+1) % M)
if (keys[i].equals(key))
break;
keys[i] = key;
vals[i] = val;
}
public Value get(Key key)
{
for (int i = hash(key); keys[i] != null; i = (i+1) % M)
if (key.equals(keys[i]))
return vals[i];
return null;
}
}
2.HashMap解析
java中的HashMap就是使用的連結清單法的散清單實作的
HashMap的散列函數
static final int hash(Object key)
{
int hash;
return key == null ? 0 : (hash = key.hashCode()) ^ hash >>> 16;
}
int index = hash(key) & (capacity - 1)
HashMap中的散列函數将key的hashCode()移位16位，然後和自己取與，最後取餘。
沖突：
雖然使用了連結清單法避免沖突，但仍然可能出現同一個位置放了太多鍵而導緻散清單退化為連結清單的可能，是以HashMap做了優化，當連結清單元素大于8時會将連結清單轉化為紅黑樹，紅黑樹插入和取元素的時間複雜度為o(logn)，雖然比不上散清單的O(1)，但最低性能也有了保證。
3.leetcode中的散清單
3.1 leetcode1 twosum，兩數之和
https://leetcode-cn.com/problems/two-sum/description/
這道題題目很簡單，就是讓你在一個數組中找出兩個和為target的數，還記得第一次做這題的時候，用的是兩個for循環，時間複雜度達到O(n^2)，雖然也過了，但現在有了散清單，就有了更加簡單的做法。利用java中的散清單HashMap,将數的值和索引分别作為鍵和值存入散清單，java實作如下
public int[] twoSum(int[] nums, int target)
{
HashMap<Integer,Integer> tracker = new HashMap<>();
for (int i = 0; i < nums.length; i++)
{
if (tracker.containsKey(target - nums[i]))
{
return new int[]{tracker.get(target - nums[i]) , i};
}
else
{
tracker.put(nums[i],i);
}
}
return new int[2];
}
3.2 leetcode242 valid-anagram
https://leetcode-cn.com/problems/valid-anagram/description/
思路和上面差不多，不再贅述。
public static boolean isAnagram(String s, String t)
{
if (s == null || t == null) return false;
if (s.equals(t)) return true;
if (s.length() != t.length()) return false;
int[] hashtable = new int[26];//26個英文字母
for (int i = 0; i <s.length(); i++)
{
hashtable[s.charAt(i) - 'a']++;
}
for (int i = 0; i <t.length(); i++)
{
if (hashtable[t.charAt(i) - 'a'] == 0) return false;
else hashtable[t.charAt(i) - 'a']--;
}
return true;
}
3.3 leetcode49 group-anagrams
public static List<List<String>> groupAnagrams(String[] strs)
{
Map<String,List<String>> map = new HashMap<String,List<String>>();
for (String s:strs)
{
char[] chars = s.toCharArray();
Arrays.sort(chars);
String value = String.valueOf(chars);
if (map.containsKey(value))
{
map.get(value).add(s);
}
else
{
map.put(value,new ArrayList<String>());
map.get(value).add(s);
}
}
return new ArrayList<>(map.values());
}
![【二叉樹（二）】：二叉搜尋樹[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)