HashMap

一个数组，每个存储了链表的头节点，put时候根据key得到hashcode ,然后计算在散列表中的位置，插入到数组对应的链表头下一个元素，get时候根据key查找，若hash code 相同，存在冲突，遍历链表，否则直接返回

static class Node<K,V> implements Map.Entry<K,V> {
     final int hash;
     final K key;
     V value;
     Node<K,V> next;

transient Node<K,V>[] table;

Object hashcode 其值就是对象的内存地址,String hashcode 计算：
String.java

    public int hashCode() {
        int h = hash;
        final int len = length();
        if (h == 0 && len > 0) {
            for (int i = 0; i < len; i++) {
                h = 31 * h + charAt(i);
            }
            hash = h;
        }
        return h;
    }

HashMap特性

hashcode & equals

hashcode 和 equals 同时复写保持一致
比如hashcode 相同，但是equals为false,那么会产生大量冲突，
如果hashcode 不同，equals 为true,相同key存在了不同的index中，不能保证key值唯一性，如果是hashset 那么无法保证数据不重复

冲突查找

冲突时候默认是链表存储，当链表长度大于8 ，则使用红黑树TreeNode查找，速度从O(n)提升为O(lgn)；当红黑树中个数小于6时候，再恢复成链表查找

保证key值唯一

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //注释1：如果key 的hashcode 相同并且key.equals为true 那么覆盖原来的值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //需要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

线程不安全

HashMap 线程不安全会出现哪些问题？

（1） 如果一个线程put ,刚好赶上扩容，这时候另外一个线程需要get可能使用的还是老的index 这样就不能得到正确的值

（2）如果两个线程同时put,并且key值产生冲突，可能会导致只有一个线程写进去了，另外一个值丢失

（3）最糟糕的还可能引起死循环,两个线程同时put,并引发resize 时候，因为resize需要把老的数据考到新的数组里面，在线程1执行到注释一处，线程二完成数据拷贝，形成环路，可以参考 https://coolshell.cn/articles/9606.html

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        ... ...

        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                          //注释1
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        
                    }
                }
            }
        }
        return newTab;
    }

扩容机制

默认长度16，个数超过16*0.75时候会扩大2倍，所以如果知道个数提前定义N/0.75 大小的hashmap 可以避免扩容，提高性能

参考文档

http://coding-geek.com/how-does-a-hashmap-work-in-java/

• HashTable

HashTable源码中是使用synchronized来保证线程安全的

public synchronized V get(Object key) {
       // 省略实现
    }
public synchronized V put(K key, V value) {
    // 省略实现
    }

• ConcurrentHashMap

jdk 1.7

使用了一个包含16个锁的数组，每个锁保护散列表的1/16，轻重第N个散列桶由N mod 16 个锁来保护，如果hashcode 均匀分布，大约能把对锁的请求减少到原来的1/16

缺点：

与单个锁实现独占访问相比，如果再需要获得所有锁的操作，如resize或者clear 时，开销变大。但一般情况只需要获取一个锁，如get获取数据

jdk17.png

jdk 1.8

采用CAS和synchronized来保证并发安全,给每个hash 桶的头结点加锁，put的时候如果：

（1）不存在改key对应的头结点：

则通过CAS方法加入头结点，如果当前节点是空则加入，如果不为空说明其他线程此刻已经加入，则进入下一次循环

（2） 存在头结点，对表头加锁，插入链表或者红黑树中

get 的时候没有加锁，直接查

jdk18.png

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        ...


    /**
     * The array of bins. Lazily initialized upon first insertion.
     * Size is always a power of two. Accessed directly by iterators.
     */
     //使得对table的任何更新对其它线程也都是立即可见的
    transient volatile Node<K,V>[] table;

        /**
     * Stripped-down version of helper class used in previous version,
     * declared for the sake of serialization compatibility.
     */
    static class Segment<K,V> extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        final float loadFactor;
        Segment(float lf) { this.loadFactor = lf; }
    }

CAS (Compare And Set)解决加锁造成性能损耗的一种机制，如果内存中的值与期望的值相同则设置新值

下面例子中如果工作线程值与内存中一致，才执行++ 操作。

    private AtomicInteger ai = new AtomicInteger();  
    private int i = 0;  
   /** 使用CAS实现线程安全计数器 */  
    private void safeCount() {  
        for (;;) {  
            int i = ai.get();  
            // 如果当前值 == 预期值，则以原子方式将该值设置为给定的更新值  
            boolean suc = ai.compareAndSet(i, ++i);  
            if (suc) {  
                break;  
            }  
        }  
    }  
  
    /** 非线程安全计数器 */  
    private void count() {  
        i++;  
    }  
} 

• Collections.synchronizedMap

HashSet

如何保证数据唯一？

内部维护了一个HashMap，add 时候以元素的值作为key，因为hashmap的key是唯一的，所以HashSet的值唯一

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }
    ...
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}