散清單原理，HashMap源碼解析

1.HashSet的實作原理

HashMap不會增加重複的元素（源碼命中後做return），又HashSet底層是基于HashMap實作，故Set的add方法不允許增加重複的元素。

總結：底層是基于HashMap實作，具體代碼如下

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }    
           

HashSet的add方法是用Map的put方法實作。put查找命中更新值并傳回舊值，舊值 != null，既添加已存在的元素add方法傳回false；put未命中直接插入并傳回null，因為null==null，故add傳回true。存入的是預設值present；

2.HashMap的實作原理

• HashMap put源碼-簡版

public V put(K key, V value) {
    for( Node x = first[ key.hashcode() % M ]; x!=null; x = x.next){
     if(x.key == key){
     	V oldValue = x.value;
     	x.value = value; 
     	return oldValue; //傳回舊值
     }
    }
    first[ key.hashcode() % M ] = new Node(key, value，first); //未命中
    return null;
           

散清單使用連結清單數組實作，每個清單被稱為桶。先計算hashCode()，再和桶的總數取餘，所得的結果就是數組的索引（既桶的索引）。有時候桶被占滿，就會出現散列沖突。解決哈希沖突可以是拉鍊法或線性探索法。桶其實拉鍊法。線性探索法又叫開放位址法，就是按位址在沖突的下一個空位插入。

3.List，Set和Map的不同

順便回憶一下List，Set和Map的不同:

• Collection是add，Map是put；
• List是一個有序集合，元素會增加到容器的特定位置，使用疊代器添加元素有實際意義，Set和Map是無序的；

4.ConcurrentHashMap如何保證線程安全

java 7之前通過分段鎖實作；分段鎖很好解釋，分段加鎖嘛；java 8後使用synchronized修飾，因為對synchronized做了優化；

5.leetcode第一題

• leetcode 兩數之和

HashMap<Integer, Integer> map = new HashMap();
int n = nums.length;
for(int i=0; i<n; i++){
   if(map.containsKey(target-nums[i])){
       int result[] = new int[2];
       result[0] = map.get(target-nums[i]);
       result[1] = i;
       return result;
   }
    else
        map.put(nums[i], i);
}
return null;