前言

读完这一篇HashMap，吊打面试官

一、HashMap是什么？

相信阅读过HashMap源码的小伙们都知道,HashMap实现了Map接口,Map就是用于存储键值对(k,v)的集合类,
而HaspMap是针对k,v 来进行的一些列操作，并且HashMap 在1.8以后加入了红黑树数据结构来便于我们的
数据检索操作

在这里插入图片描述

二、HashMap五个参数：

1.初始容量

在java8的官方描述中说：容量是哈希表中的桶数，也就是在new一个HashMap的时候的初始容量

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

2.负载因子

负载因子，负载因子表示的是一个散列表空间的使用程度，负载因子越大链表也就越大，链表越大
索引效率也就会大大降低有一个公式 initailCapacity*loadFactor=HashMap的容量。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

3.最大容量

最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

4.树化阈值

该值定义了树化标准具体解释在下面的put中文提到

static final int TREEIFY_THRESHOLD = 8;

5. 拆树阈值

static final int UNTREEIFY_THRESHOLD = 6;

三.HashMap三个构造函数

此构造函数可以自定义构建 HashMap的初始容量和负载因子

 public HashMap(int initialCapacity, float loadFactor) {
 		// 如果 initialCapacity（初始容量）小于0 抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 如果 initialCapacity（初始容量）大于 最大容量 把最大容量赋值给初始容量
        // 在HashMap的官方文档中提到 初始容量不得大于 最大容量
        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() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

构造器放入一个HashMap直接初始化。

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

四.put方法源码解析

	public V put(K key, V value) {
		//  这里面 提供了一个hash()方法 这个方法的一个主要作用 就是计算出当前KEY的hash值
		
        return putVal(hash(key), key, value, false, true);
    }

	// hash 寻址 
	static final int hash(Object key) {
        int h;
        // 将我们的hash值右移16位 减少hash冲突
        // 即使高位为0，异或特性： 0 异或任何数 都为任何数它本身 ，那就是返回key.hashCode() ，不会影响它本身
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

put数据的幕后功臣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;
        // 判断我们当前table 是否为空 若为空 调用我们的resize()进行初始化
        // 当然resize()也是我们的扩容方法
        // 注 ： 频繁的resize() 势必会影响我们的HashMap的一个性能
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果通过hash算出来的数组节点为null 就new一个节点  把该值存放进去 
        // 如果不为空 就走下面的 else 放入链表
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        // 链表操作
            Node<K,V> e; K k;
            // 判断 hash 算出的节点不为空 
            // 判断该节点与我们的key 是否相同 如果相同 就获取该节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果不容 判断 该节点 是否 为 TreeNode  即 红黑树
            // 否则
            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) {
                       // 如果是链表的，以key-value插到链表尾
                       // 插入尾部避免hash冲突造成死循环
                        p.next = newNode(hash, key, value, null);
                        // 节点 到达 阈值 进行树化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        	//  树化方法  
                        	// 并不一定 到达 阈值 就会树化 具体在 树化方法中 会对节点大小进行判
                        	// 断
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 判断 节点key 与我们要 插入的key 是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // 相等 跳出循环 执行 替换操作
                        break;
                    p = e;
                }
            }
            // 如果 e 不等于 null 就证明 我们即将插入的key 与 我们节点中的key相等
            // 注： 这里也就是 hashMap 中 不管插入多少 都会 用新值 替换旧值得 关键代码
            if (e != null) { // existing mapping for key
            	// 记录我们旧的value 值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                	// 新的vale值 替换
                    e.value = value;
                   // 回调
                afterNodeAccess(e);
                // 返回旧的值
                return oldValue;
            }
        }
        ++modCount;
        //  实际大小 大于 阈值 就扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

treeifyBin 树化方法

   final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // 判断数组 是否为空 以及 容量 是否大于 我们的 阈值容量 MIN_TREEIFY_CAPACITY=64
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        	// 扩容方法
            resize();
            // 否则 就 树化
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
            //	 node 转为 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);
        }
    }

总结：

1. 常见HashMap 面试题

1.1. HashMap 是否为线程安全的？接下来我会用一张图结合上述源码为大家说明

在这里插入图片描述

1.2. 关于线程安全的Map 你都知道哪些，他是怎么保证线程安全的？

答 HashTable，ConcurrentHashMap，其实关于HashTable 的解释很接单，它里面的方法都是用synchronized来实现同步机制的，而ConcurrentHashMap内部是通过cas 和 synchronized 来实现线程安全的问题(cas和synchronized 的原理在后续章节中我会抽出一个章节为大家讲解)