JDK8源码阅读：HashMap

1.是什么

是通过K-V键值对来保存数据的数据结构，

K和V都可以为null

。

继承关系如下图所示：

JDK8源码阅读：HashMap

数据结构如下图所示：

JDK8源码阅读：HashMap

2.构造函数和主要属性

加载因子loadFactor非常重要，这个决定了什么时候进行数组的扩容操作
每次扩容时，都扩容为原来数组长度的2倍

// 存放数据的数组默认初始大小为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 默认的加载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表变形为红黑树时，链表的长度
static final int TREEIFY_THRESHOLD = 8;

// 红黑树变形为链表时，红黑树节点个数
static final int UNTREEIFY_THRESHOLD = 6;

// 当hashmap中元素达到64时，才会让链表变形为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;

// 存储元素的数组
transient Node<K,V>[] table;

// hashmap中元素的个数
transient int size;

// 加载因子
final float loadFactor;

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
int threshold;

static final int MAXIMUM_CAPACITY = 1 << 30;

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);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

2.1 这里着重讲一下带有初始容量时的代码

当在创建HashMap时，传入了初始容量后，会处理这个初始容量。

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);
}

但是这个时候还没有初始化存放数据的数组，而是在第一次 put 时，才会去初始化存放数据的数组。

如下图所示：

第一次执行resize()方法，oldTab 是 null，所以 oldCap = 0
然后就会执行图中红框的方法，初始化新的数组容量为 oldThr ，也就是 threhold

JDK8源码阅读：HashMap

下面这段代码是在JDK1.7以后的实现

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        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;
    }

第一行代码 int n = cap - 1; 是因为当cap的值为2x时，如果cap不减1的话n的值会为2x+1，所以我们需要先将cap的值减一。
然后再算出一个2的次方的值，这个值为最接近并大于cap的值。例如5最近的2的次方的值为23（8），29的最近的2的次方的值为25（32）。

int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;

为什么上面算法能实现找到大于n的最小的2的次方的值呢？

因为当我们把n无符号右移1位后做或操作，那么一个1就会变为两个1，再右移2位，两个1就变为4个，依次类推，到最后右移16位就会将n的二进制的最高位的1的后面位置全部变为1。

然后最后

return

返回的时候，再对n进行加1操作，使得返回值是一个大于n的最小的2的次方的一个值。也就是把n的二进制表示的值的最高位的1前面变为1，然后新的最高位后面的全部变为0。

例如：

17 ==> 0001 0001

n |= n >>> 1

：0001 0001 | 0000 1000 ==> 0001 1001

n |= n >>> 2

：0001 1001 | 0000 0110 ==> 0001 1111

因为最高位1后面已经全部是1了，所以后面的无符号右移4位、8位和16位后

或

的结果也为0001 1111。

然后末尾+1就等于0010 0000，也就是大于17的最小的2的次方的值

3.新增元素

在调用put()方法时，主要有2种情况：

该key不在hashmap中存在，则新增一个元素，并判断hashmap是否需要扩容，最后返回null
该key已经存在于hashmap中，则替换掉原来的value为新值，最后返回key对应的旧value值

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

// 当key为null时，hash值为0，否则hash值为key的hashcode与hashcode高16位进行异或，减少hash冲突。
// 在《码出高效：Java开发手册》一书中对这个算法进行了说明：“将高位与低位进行异或 有助于泊松分布。”
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1.当数组为null或者数组长度为0时，进行扩容操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2.当所在位置为null时，直接在该位置放入元素
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;

		// 判断key是已经存在
        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 {
        	// binCount是为了统计链表的长度
            for (int binCount = 0; ; ++binCount) {
            	// 找到了链表的末尾，说明key不存在
                if ((e = p.next) == null) {
                	// 将新增的元素添加到链表的末尾
                    p.next = newNode(hash, key, value, null);
                    // 判断是否需要将该链表转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    	// 在这个方法里，不会直接将链表转为红黑树，而是还会判断table数组的长度，
                    	// 如果大于64，才会将链表转为红黑树，否则会进行resize()扩容操作。
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果是在链表中间找到了，说明key已经存在
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
		
		// e不为空，说明是修改key所映射的value值，而不是新增的key-value键值对
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // put方法默认onlyIfAbsent为false，即如果旧值不为null，就返回旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 是LinkedHashMap实现的方法，在HashMap中为一个空方法
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
	// 元素新增成功后，判断元素个数（包括刚刚新增的元素）是否大于 数组长度 * 加载因子，大于则进行扩容操作
    if (++size > threshold)
        resize();
    // 是LinkedHashMap实现的方法，在HashMap中为一个空方法
    afterNodeInsertion(evict);
    return null;
}

4.移除元素

若key不存在，则返回null

若key存在，则移除key对应的元素，并返回key所对应的value值

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

JDK8源码阅读：HashMap

1.是什么

2.构造函数和主要属性

2.1 这里着重讲一下带有初始容量时的代码

3.新增元素

4.移除元素

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method