HashMap浅析

HashMap

HashMap是Java中最常用的数据集合，支持泛型K,V采用键值对的存储方式，主要的属性如下

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,                  Cloneable,Serializable{
    //默认的初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //链表最大的长度，如果超过就会转换成树结构
    static final int TREEIFY_THRESHOLD = 8;
    //存放k，v的数据对象
    transient Node<K,V>[] table;
    //元素个数
    transient int size;
    //修改次数
    transient int modCount;
    //集合容量
    int threshold;
    //负载因子
    final float loadFactor;
    //内部链表类
    static class Node<K,V> implements Map.Entry<K,V>{
        final int hash;//key的hash值
        final K key;//key
        V value;
        Node<K,V> next;//下一个对象
    }
}

Map最的基本操作是put(k,v)和get(k)了

Map集合put

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

put函数会先调用hash函数获取到key的hash值，然后再调用putVal函数，hash(k)的核心是hash算法

static final int hash(Object key){
    int h;
    //取出高16位和hashCodeXORs操作
    return (key == null) ? 0:(h = key.hashCode()) ^ (h >>>16);
}

获取到hash值后调用putVal存放k，v键值对

putVal

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;//初始化tab ，n
    if((p = tab[i = (n-1) & hash]) == NULL) //对hash桶长度求余计算hash对应的下标，然后
        tab[i] = newNode(hash,key,value,null);//此位置位null直接创建
    else{
        Node<K,V> e; K k;
        if(p.hash == hash &&
          ((k = p.key) == key) || (key != null && key.equals(k)))
            e=p;//hash值相等，key为null或者key相等就替换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);
                    //如果链表结构大于8对hash桶进行扩容，如果容量不小于64就会转换为tree结构
                    if(binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab,hash);
                    break;
                }
                if(e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k))))
                    //找到hash相同，key相同的位置返回，此时e的值就是需要存入Node结构体
                    break;
                p = e;//指向下一个位置
            }//end for
            if(e != null){
                //如果e不为null需要更新value的值
                V oldValue = e.value;
                if(!onlyIfAbsent|| oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if(++size > threshold)
            resize();//添加后的大小大于容量就扩容
        return null;
    }
}

HashMap的resize()扩容

threshold属性记录着hashmap的容量大小，每次添加都会进行容量检查，如果实际大小超过了负载因子容量所能容纳的大小(容量*负载因子)就会以原来的2倍大小进行扩容

final Node<K,V> resize(){
    Node<K,V> oldTab = table;
    int oldCap = (oldTab == null) ? 0 = oldTab.length;//哈希桶数组大小
    int oldThr = threshold;
    int newCap , newThr = 0;
    if(oldCap > 0){
        if(oldCap >= MAXMUM_CAPACITY){
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }else if((newCap =  oldCap << 1) < MAX_MUM_CAPCITY && 
                oldCap >= DEFAULT_INITIAL_CAPCITY)
            newThr = oldThr << 1; //双倍容量扩容
    }else if(oldThr > 0)
        newCap = oldThr; //默认初始化oldThr为16
    else{
        newCap = DEFAULT_INITAL_CAPCITY;   
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPCITY);
    }
    if(newThr == 0){
        float ft = (float)newCap *loadFactor;
        newThr = (newCap < MAXIMUM_CAPCITY && ft < (float)MAXIMUM_CAPCITY ?
                 (int) ft: Integer.MAX_VALUE);
    }
    //后续代码是复制数据到扩容后的对象中
}

存放链表的hash桶

根据前面的分析结果可以知道，hash桶是一个数组，计算对象存放的位置是通过key.hashcode() & (n -1)，n是hash桶的容量，也就是HashMap构造函数的参数initialCapacity，并且后续更改是以原值的两倍，hash值按位与(length -1)是对length求余来计算下标。尽可能的利用所有hash桶，要使hash桶内的数据是以链表形式存在，就必须要满足所有的key.hash对hash桶的length求余的余数相同，并且同时要满足同一个位置的hash桶存放的链表大小不超过8个，如果超过8个就会进行扩容转换，下面是验证代码

public class Test{
    public static void main(String []args){
        //初始的hash桶容量
        int capacity = 16;
        HashMap<Integer,String> hashMap = new HashMap<>(capacity);
        for(int i = 0; i < 8; i++){
            /*
                int数据的hashcode为int本身，默认的capaity为16，
                存放的hash值为16的整数倍，所以都会放入一个hash桶里面，也就是数组的下标为0的位置
            */
            hashMap.put(i*capacity,"a" + i);
        }
    }
}

debug查看存储信息

可以看到默认的debug信息是显示key，value的，不会显示内部的真实结构，需要在debug窗口右键->mute Renderers，把这个选项勾选就能看到实际的对象结构信息了

根据debug的结构信息可以看到所有的对象都存放在hash桶table的下标为0的位置，后插入的会放在最后一个Node的next对象中，最后一个Node的next为null表示到达链表结尾了

treeifyBin

前面putVal的时候会检查链表结构的大小，如果链表结构大于8并且hash桶length小于64就会执行treeifyBin进行扩容，否则就把当前的hahs桶从链表转换成树结构

final void treeifyBin(Node<K,V>[] tab,int hash){
    int n,index;Node<K,V> e;
    if(tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //如果小于64就扩容
        resize();
    else if((e = tab[index = (n-1) & hash]) != null){
        TreeNode<K,V> hd = null,tl = null;
        do{
            //把每个对象转换成TreeNode
            TreeNode<K,V> p = replacementTreeNode(e,null);
            if(tl == null)
                hd = p;
            else{
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        }while((e = e.next) != null);
        if((tab[index] = hd) != null)
            hd.treeify(tab);//转换成tree结构
    }
}

TreeNode

//HashMap.java
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>{
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}
//LinkedHashMap.java
static class Entry<K,V> extends HashMap.Node<K,V>{
    Entry<K,V> before,after;
}

TreeNode既有双链表的特性prev和next对象，又有二叉树left和right对象，如果hash桶length不小与64，treeifyBin就会遍历Node单链表，把每个元素转换成TreeNode并关联next和prev两个前后节点变成双链表结构，然后再调用hd.treeify(tab)转换成树结构。上面的验证代码，把capacity改为64，插入元素变成9个就会变成tree结构，debug信息如下

可以看到最终的转换结果是一个平衡树，TreeNode结构中left和right属性构成了树结构，而，prev和next属性构成了双链表结构，TreeNode每个节点既是树节点，也是链表中的节点

treeify链表树化

上面分析到如果map的capacity容量不小于64，并且有一个hash桶中的Node链表长度超过了8就会将该链表转换成TreeNode树结构，前面代码提到在putVal中会去检查某条链表长度是否超过8，如果超过就会调用treeifyBin函数，此函数主要有两个功能，

扩容

如果map中的Node数组长度，也就是HashMap的capacity < 64就会调用resize函数将

树化

capacity不小于64后就会对超过8个元素的链表进行树化，其实现是treeify函数

Hashtable区别

Hashtable继承自Dictionary，实现了Map接口，主要属性如下

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>,Cloneable,Serializable{
    //存数据的集合
    private transient HashtableEntry<?,?>[] table;
    //集合元素数量
    private transient int count;
    //负载容量大小capacity*loadFacotr
    private int threshold;
    //负载因子
    private int loadFactor;
}

• hashtable中所有的修改操作都有synchronized关键字修饰，是线程安全的

• 散列函数不同，(key.hashcode() & 0x7fffffff) % tabl.length计算出需要存放在table中的index值

• hash冲突解决方案只有链表结构，不会和HashMap一样升级为平衡树结构

• 如果存储的数据超过了负载threshold，则调用rehash()函数进行扩容，扩容的大小是原来的2倍+1

ConcurrentHashMap区别

和HashMap一样，继承自AbstractMap，ConcurrentHashMap中的Key和Value不允许为null，HashMap中运行Value为null，且key为null的值只有一个，和HashMap有同样的默认capacity(16)和默认负载因子load_factor(0.75)

• volatile关键字，和数据存储有关的属性都有volatile关键字修饰

• 内部通过Unsafe对象来确保并发编程中数据的安全

• hash冲突链表解决方案的最大长度都是8，超过最大长度都会转换为红黑树结构

HashSet

HashSet集成在AbstractSet，是一个set集合，其他的数据结构都是有k，v键值对结构的数据。内部持有HashMap对象，实现方式是通过把数据作为key，把静态常量Object作为唯一数据放在内部持有的HashMap对象中。

//HashSet主要操作代码
//存放数据对象
private transient HashMap(E,Object) map;
//map中所有的key都会对应这个Object对象，通过map增删返回的对象是否是这个对象来判断操作是否成功
private static final Object PRESENT = new Object();
public boolean add(E e){
    return map.put(e,PRESENT) == null;
}
public boolean remove(Object o){
    return map.remove(o) == PRESENT;
}

重新认识HashMap

hash桶

通过阅读源码我们了解到HashMap是通过hashCode计算出存放在table数组中，table是一个数组，其中的元素是存有键值对和hash值的单链表结构，存放过程中会根据hash算法计算出存放在table数组中的位置，因此table也被称为hash桶

hash算法

public V put(K key,V value){
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key){
    int h;
    return (key == null)? 0:(h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash,K key, V value, boolean onlyIfAbsent,boolean evict){
    if((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize().length);
    if((p = tab[i = (n-1) & hash]) == null)//根据hash对数组长度求余算出index下标位置
     //...省略后面代码
}

三目表达式后半部分是连写方式，和IO流while((len = in.read(buf)) > 0)类似，连写的部分分为三步

• h=key.hashCode()

• temp = h >>> 16

• h ^ temp

从hash算法中我没看可以看到key为null的时候总是会被放在hash桶的第0个位置，拿到hash值后还需对数组长度求余得出的值才是存放在hash桶中的下标(A对B求余等价于A & (B -1))

hash值为什么右移16

java中hash值是int类型占内存是32bit，而日常工作上遇到的数组很少超过2^16大小的数据集合,如果直接使用hash值对数组长度进行求余操作很难利用到数据的高16位，这样很容易造成求余后计算的下标相等，进而导致数据堆积到hash桶中的同一个位置上，只有把数据尽可能的分散到不同的位置才能满足更好的性能要求。所以利用高16和hash值异或后的值来确定下标位置，这样就可以利用32位数据的每一个bit参与计算从而达到数据的尽可能的分散

而异或的结果刚好就是高16位和低16位异或的结果，利用计算器观察bit数据高16位和低16位刚好上下对应，方便观察hash值直接求余和上下异或后再求余的区别

hash冲突

上面的hash算法最后会利用到hash桶长度求余，求余后对于容量小的时候还是很容易造成求余后值一样，这种情况称为hash冲突；解决冲突会根据数据的多少来决定

链表化

hash冲突后会首先把数据转为单链表结构

树化

当hash冲突的单链表结构长度大于8的时候会转为红黑树结构

具体的代码可以查看putVal操作

负载因子

loadFactor负载因子是map中的数据超过了设定的容量*负载因子的数量后就会进行扩容操作

扩容

超过负载因子设置的阈值后就会进行resize扩容机制，每次扩容都是当前容量的2倍详情代码情况resize()扩容