散列表原理，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;