HashMap采用Node 数组来存储key-value对，每一个键值对组成了一个Node实体，Node类实际上是一个单向的链表结 构，它具有Next指针，可以连接下一个Node实体。

HashMap在JDK1.8之前和之后的区别

JDK1.8 之前，数组 + 链表 存储结构

缺点就是哈希函数很难使元素百分百的均匀分布，这会产生一种极端的可能，就是大量的元素存在一个桶里

JDK1.8 之后：数组 + 链表 + 红黑树

1. 添加元素时：链表长度 大于8的时候，转换为红黑树
2. 删除元素、扩容时，同上，数量大于8时，也是采用红黑树形式存储，但是在数量较少时，即数量小于6时，会将红黑树转换回链表
3. 遍历、查找时，使用红黑树，他的时间复杂度O（log n），便于性能的提高。

数据结构

存储结构

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

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

// Node 数组 
transient Node[] table;

//加载因子
final float loadFactor;

//默认加载因子 ，容量达到这个比例时自动扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 数量大于8时，链表转换为红黑树形式存储 
static final int TREEIFY_THRESHOLD = 8;

//即数量小于6时，会将红黑树转换回链表，删除元素时remove
static final int UNTREEIFY_THRESHOLD = 6;

//PUT 时每次都做hash
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//put  函数核心算法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null) // 这里的n 表示数组的长度。 
            // hash 
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)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;   // modCount 是java集合中Fail-Fast的底层实现原理
        if (++size > threshold) //扩容
            resize();
        afterNodeInsertion(evict);// 空实现
        return null;
    }
    
    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node p) { }

思考

java集合中的快速失败：modCount

// 快速失败是Java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast。

//举个例子：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就可能会抛出 ConcurrentModificationException异常，从而产生fast-fail快速失败。

HashMap中遍历算法如下：

final class KeySet extends AbstractSet {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super K> action) {
        Node[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node e = tab[i]; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
              //抛出异常，Fail-Fast
                throw new ConcurrentModificationException(); 
        }
    }
}

优化hash 算法

JDK1.8中,是通过hashCode()的高16位异或低16位实现的:(h=k.hashCode())^(h>>>16),主要是从速度,功效和质量来考虑的,减少系统的开销,也不会造成因为高位没有参与下标的计算,从而引起的碰撞。

//扰动函数：促使元素位置分布均匀，减少碰撞几率
static final int hash(Object key) {
        int h;
  	    // 如果key == null  返回的值是 0 
        // 如果key !=null  
        // 首先计算 key 的 hashcode 值赋值给 h ,
        // 然后与h 无符号右移16位后的二进制按位异或预算得到最后hash值
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}	

hash具体实现过程如下图所示：

hash 计算过程与putval函数的应用

1. key.hashCode()；返回散列值也就是hashcode，假设随便生成的一个值。
2. n表示数组初始化的长度是16。
3. &（按位与运算）：运算规则：相同的二进制数位上，都是1的时候，结果为1，否则为零。
4. ^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为0，不同为1。

高16bit不变，低16bit和高16bit做了一个异或（得到的hashCode转化为32位二进制，前16位和后16位低16bit和高16bit做了一个异或）

为什么这样实现呢？

如果当n即数组长度很小，假设是16的话，那么n - 1即为1111 ，这样的值和hashCode直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。降低了Hash冲突的概率

为什么要用异或运算符

保证了对象的hashCode的32位值只要有一位发生改变,整个hash()返回值就会改变。尽可能的减少碰撞。

工作原理

存储对象时,将K/V键值传给put()方法:

1. 调用hash(K)方法计算K的hash值,然后结合数组长度,计算得数组下标;
2. 调整数组大小(当容器中的元素个数大于capacity*loadfactor时,容器会进行扩容resize为2n);
3. hash碰撞

i.如果K的hash值在HashMap中不存在,则执行插入,若存在,则发生碰撞;

ii.如果K的hash值在HashMap中存在,且它们两者equals返回true,则更新键值对;

iii.如果K的hash值在HashMap中存在,且它们两者equals返回false,则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。(JDK1.7之前使用头插法、JDK1.8使用尾插法)

//get 实现
public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

问题思考？

Q：默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？

A：hash运算的过程其实就是对目标元素的Key进行hashcode，再对Map的容量进行取模，而JDK 的工程师为了提升取模的效率，使用位运算代替了取模运算，这就要求Map的容量一定得是2的幂。HashMap的容量为什么是2的n次幂，和这个putval方法中（n - 1) & hash的计算方法有着千丝万缕的关系，符号&是按位与的计算，这是位运算，计算机能直接运算，特别高效，按位与&的计算方法是，只有当对应位置的数据都为1时，运算结果也为1，当HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够（充分的散列），使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。

Q:HashMap如何有效减少碰撞？

A: 扰动函数：促使元素位置分布均匀，减少碰撞几率 、使用final对象，并采用合适的equals()和hashCode()方法