Java基础-HashMap解析

一. 概述

　Hasp可以看成一个桶装的哈希散列表。但是当桶变得太大的时候，就会变成一个树状的桶。每个结构类似于java.util.TreeMap。大多数情况下使用普通的桶，但是转换为TreeNode仅适用于通过坚持节点实例。TreeNode桶可能与其他的使用方法一样，但是支持更快的查找，当过剩的时候。然而，大多数情况下正常使用的桶不会过剩（指桶里面的数据元素过剩），所以在检查存在树形的桶会存在延迟性，在列表的方法中。

　树形的桶主要由哈希排序，但是在一些情况下，如果2个元素是相同的类，并且类实现了comparable接口，则用他们的compare方法来排序（我们通过反射去检查去验证这一点，详见方法ComparableClassFor）。

　当keys具有不同的哈希值或者可排序的，添加树的容器导致的复杂性是值得的，最坏的情况下检索的复杂度为O(logn)。如果hashcode的分布值不好的话，许多键共享一个hashcode，那么在意外或者恶意的条件下，性能就会下降，相同的情况出现从compare方法中。如果两者不适应，则不采取预防性措施相比，我们在时间和空间上可能浪费大约两倍的时间。但是，唯一已知的案例来自一个糟糕的用户编程实践，这些实践已经非常缓慢了，几乎没什么区别。

　因为treeNode大约是普通节点的二倍，我们只有当桶的元素大小足够才会使用（树化阈值，当桶中元素个数超过这个值时，需要使用树节点替换链表节点：8；链表还原阈值，6：当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构 ，这个值应该比上面那个小，至少为 6，避免频繁转换；最小树形化容量，64：当哈希表中的容量大于这个值时，表中的桶才能进行树形化）。当桶中的元素变少的时候，它们就会被转换为普通的桶。

   在分布良好的哈希列表中，很少使用TreeNode桶，理想情况下，在随机的哈希值中，桶中的节点频率遵从泊松分布，负载因子（空间的使用程度）默认阈值为0.75。

　所有适用的内部方法都接受哈希代码作为参数（通常由公共方法提供），允许它们相互调用，而无需重新计算用户哈希代码。大多数内部方法也接受“tab”参数，即大多数内部方法也接受“tab”参数，即调整大小或转换参数。

　当bin列表被树化、拆分或未查询时，我们将它们保持在相同的相对访问/遍历顺序（即字段节点.下一个)以更好地保留局部性，并稍微简化对调用的拆分和遍历的处理迭代器.remove. 当在插入时使用比较器时，为了保持整个重新平衡的顺序（或者与这里要求的一样接近），我们比较类并将hashcode标识为断开连接符。

　普通vs tree模式之间的使用和转换由于子类LinkedHashMap的存在而变得复杂。下面的钩子方法定义为在插入、删除和访问时调用，这些钩子方法允许LinkedHashMap内部保持独立于这些机制。（这也要求将一个map实例传递给一些可能创建新节点的实用程序方法。）基于SSA的并行编程风格有助于避免在所有扭曲的指针操作中出现混叠错误。

　　总结下：HashMap采用数组+链表/树（数组元素-桶存储的树或者链表引用地址），大多数情况下，桶存储的是链表结构，当然树形结构的大小是链表的两倍，只有在一定的条件下（以空间换时间），才会（桶中元素的个数>8并且集合的元素个数>64）转换为树形结构（转化后的节点也支持前后节点查询，即链表方式查询）。树形结构查找元素的时间复杂度为O(longN)，比链表的时间复杂度O（n）快。

二. 源码分析

　2.1 初始化容量为啥2的幂比较友好呢？

　　我们需要均匀分布，那么我们需要取模（取余hashcode%size）运算，将各个元素均匀分布。（位运算的效率比取模运算效果高？其他地方有解释引用它人分析，通过反汇编发现位运算操作只需要2次mov指令和1次and指令，即3个CPU周期；而取模的操作需要2mov+1cdp+1idiv，至少需要26个CPU周期。），那么有一个公式当size是2的幂时，hashcode%size = hashcode&(size - 1)（为啥这样，这里不做论证），这样位操作实现了取模操作的均匀分布（提高了效率？）。对此为啥使用位操作代替取模操作，源码中找不到相应的文档。

//索引算法
(n - 1) & hash

　　hashmap不能保证外部初始化的容量大小是2的幂，只能从内部做保证，提供了一个位移算法。如果元素超过容量*负载因子0.75，那么就会触发扩容，扩容的时候直接容量*2。

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    static final int tableSizeFor(int cap) {//算法，返回大于等于输入值的最小的2的N次方的值。
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

　　算法目标：要求获得的是大于等于cap的最小的2的N次方。算法分析：通过a（a = n右移1）并与n做或运算赋值给n，依次2，4，8，16，将最高位的1后面所有的设置为1，结果+1，得出了大于等于cap（n+1）最小的2的N次方的值。算法描述：将cap-1转换为二进制，讲二进制上所有的数字置为1（不包括补位的），然后+1 得出大于cap-1最近的2的n次方。

　　put源码：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

　　2.2 我们可以看到对元素的key的hash值做一轮运算，这是为啥呢？　　

　　因为通常情况下，Map的size一般小于2的16次方（低位，32位分为高位16和低位16），那么与key的hash值做取模运算的时候，key的高位会被丢失，给一个例子：

hashcode:  0110 0111 0001 1100 1100 1100 1100 1100
  &
size-1  :  0000 0000 0000 0000 0000 0000 1111 1111

结果     ： 0000 0000 0000 0000 0000 0000 1100 1100

　　这样就会导致高位无法对最后的结果产生影响，那么容易造成哈希碰撞（舍弃高位，低位重复的可能性会变高）。那么我们就要考虑，如何让高位也对最后的结果产生影响。这时候，引入了^操作。（为啥不用&：与、|：或操作呢，&只要有一个数为0，那么结果为0，只是依赖一个数；|只要有一个数为1，那么结果为1，只是依赖一个数；^操作，只有2个数才能决定最终结果。）具体实现：a = (h >>> 16)，向右移16位，高位补0；^运算，原值的低位与a做^运算。这样的话，原来的每一位hashcode的值都会对结果产生影响。

static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

　　继续分析put源码：

//节点的静态内部类
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
//....
｝

//放入方法
 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;//扩容操作，默认16
        if ((p = tab[i = (n - 1) & hash]) == null)//(n- 1)&hash是计算索引操作，查找索引所在的桶（节点）
            tab[i] = newNode(hash, key, value, null);//节点不存在，则新建一个普通的桶（节点），直接放入数据，退出。
        else {//存在节点
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//判断是否key是否一致
                e = p;//key一致，找到节点
            else if (p instanceof TreeNode)//存在节点，key不一致，hash碰撞，如果是树形桶，那么走树形桶的放入方法。
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//存在节点，key不一致，hash碰撞，走普通桶
                for (int binCount = 0; ; ++binCount) {//遍历p的下一个结点，匹配查找，
                    if ((e = p.next) == null) {//p的下一个节点为null，即没匹配到
                        p.next = newNode(hash, key, value, null);//那么新建节点，注意此时e的值为null
                        if (binCount >= TREEIFY_THRESHOLD - 1) // 判断当前元素是否大于等于7
                            treeifyBin(tab, hash);//内部有判断，如果size<64，则扩容，否则转换为treenode
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))//匹配到了key了，跳出循环
                        break;
                    p = e;//循环，将p-> p.next
                }
            }
　　　　　　　//如果e存在的话，那么就是找到了e了，做赋值操作，并且返回旧值。
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)//onlyIfAbsent if true don not change existing value
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//修改结构次数+1
        if (++size > threshold)//判断是否需要扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }