深入浅出源码探究HashMap

HashMap

HashMap的底层数据结构

Jdk1.7及以前是采用数组+链表
Jdk1.8之后
采用数组+链表或者数组+红黑树方式进行元素的存储
存储在hashMap集合中的元素都将是一个Map.Entry的内部接口的实现

当数组的下标位是链表时,此时存储在该下标位置的内容将是Map.Entry的一个实现Node内部类对象
当数组的下标位是红黑树时,此时存储在该下标位置的内容将是Map.Entry的一个实现TreeNode内部类对象

比较重要的属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


static final int MAXIMUM_CAPACITY = 1 << 30;


static final float DEFAULT_LOAD_FACTOR = 0.75f;


static final int TREEIFY_THRESHOLD = 8;


static final int UNTREEIFY_THRESHOLD = 6;


static final int MIN_TREEIFY_CAPACITY = 64;



transient Node[] table;


transient Set> entrySet;


transient int size;


transient int modCount;


// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;


final float loadFactor;

put方法分析

HashMap mapl = new HashMap();
mapl.put("wm","666");

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

hash(key) :获取key对应的hash值

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

为什么要右移16位，大概是为了一下原因
首先，假设有一种情况，对象 A 的 hashCode 为 1000010001110001000001111000000，对象 B 的 hashCode 为 0111011100111000101000010100000。
如果数组长度是16，也就是 15 与运算这两个数，你会发现结果都是0。这样的散列结果太让人失望了。很明显不是一个好的散列算法。
但是如果我们将 hashCode 值右移 16 位，也就是取 int 类型的一半，刚好将该二进制数对半切开。并且使用位异或运算（如果两个数对应的位置相反，则结果为1，反之为0），这样的话，就能避免我们上面的情况的发生。
总的来说，使用位移 16 位和异或就是防止这种极端情况。但是，该方法在一些极端情况下还是有问题，比如：10000000000000000000000000 和 1000000000100000000000000 这两个数，如果数组长度是16，那么即使右移16位，在异或，hash 值还是会重复。但是为了性能，对这种极端情况，JDK 的作者选择了性能。毕竟这是少数情况，为了这种情况去增加 hash 时间，性价比不高

第一次插入

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)
		// 初始的情况下  进入resize方法查看
		// resize() 初始数组 扩容 初始的时候 获取了一个容量为16的数组
        n = (tab = resize()).length;//n 数组长度
	// 确定新添加的key在数组中的位置[下标] n = 16
	//例如 100001000111000
	//                1111
	//                1000 = 8
    if ((p = tab[i = (n - 1) & hash]) == null)
    	//通过hash值找到的数组下标 里面没有内容就直接赋值
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        if (p.hash == hash &&//p.hash == hash hash值相同
        	//key也相同
            ((k = p.key) == key || (key != null && key.equals(k))))
            //插入的值key 和 数组当前位置的 key是同一个 那么直接修改里面的内容 
            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;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

resize方法第一次执行时创建了一个 Node[16] 扩容的临界值(12)

final Node[] resize() {
	// 记录table table=null
    Node[] oldTab = table;
	// 记录原来 数组的长度 初始为0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
	// 扩容临界值 默认值为0
    int oldThr = threshold;
	// 新的数组容量 和扩容临界值
    int newCap, newThr = 0;
    if (oldCap > 0) { // 初始不满足 不执行
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
		// 初始执行此处 
        newCap = DEFAULT_INITIAL_CAPACITY; // 16
		// 16 * 0.75 = 12 扩容的临界值 12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }//更新了 扩容的临界值12
    threshold = newThr;
	// 实例化了一个容量为16的数组
    @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
    table = newTab;//更新了table
    if (oldTab != null) { // 第一次不执行
        for (int j = 0; j < oldCap; ++j) {
            Node 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)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        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);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

确定put进来的key在数组中的位置

if ((p = tab[i = (n - 1) & hash]) == null)

HashMap的容量为什么是2的幂次方

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)
		// 初始的情况下  进入resize方法查看
        n = (tab = resize()).length;
	// 确定新添加的key在数组中的位置 n = 16
    if ((p = tab[i = (n - 1) & hash]) == null)
		// 如果数组的这个位置是null的就直接插入进去
        tab[i] = newNode(hash, key, value, null);
    else {
		// 如果这个数组的位置不为null
        Node e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
			// 插入的信息和这个位置的数据是同一个key 那么久替换
            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;
    if (++size > threshold) // 添加一条信息后数组长度如果大于扩容临界值的话就扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

treeifyBin(tab, hash);

final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
	// 如果数组的长度没有达到64 那么就尝试扩容 并不会转换为红黑树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();//扩容
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode hd = null, tl = null;
        do {
			// 开始替换为红黑树
            TreeNode 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);
    }
}

动态扩容

final Node[] resize() {
	// 记录table eg[1,2,3,4,5,6,7,8,9,10,11,,,,]
    Node[] oldTab = table;
	// 记录原来 数组的长度 16
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
	// 扩容临界值12
    int oldThr = threshold;
	// 新的数组容量 和扩容临界值
    int newCap, newThr = 0;
    if (oldCap > 0) { // 16
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
		// 原来的容量扩大一倍 扩容临界值也扩大一倍24
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
		// 初始执行此处 
        newCap = DEFAULT_INITIAL_CAPACITY; // 16
		// 16 * 0.75 = 12 扩容的临界值 12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
	// 实例化了一个容量为16的数组
    @SuppressWarnings({"rawtypes","unchecked"})
    	创建的数组长度是32
        Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) { // 扩容执行 从原来的数组中将数据迁移到新的数组中
        for (int j = 0; j < oldCap; ++j) {
			// 循环数组
            Node 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)e).split(this, newTab, j, oldCap);
                else { // preserve order
					// 双向链表 普通链表的移动
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        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);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

之后看HashSet和TreeSet的源码

HashSet

往Set中添加数据，本质上就是往Map集合中添加数据

TreeSet

深入浅出源码探究HashMap

Java相关栏目本月热门文章