文章目录

• 一、哈希表
• • 1.什么是哈希表
  • 2.什么是哈希冲突
  • 3.如何处理哈希冲突
  • 4.链地址法的缺点
• 二、equals 与 hashCode 函数的关系
• 三、HashMap
• • 1. 负载因子
  • 2. 计算 key 应存储在数组中的位置
  • 3. 容量是 2 的幂的作用
  • 4. put
  • 5. resize
  • 6. get
  • 7. remove
• 四. 其他
• 参考

一、哈希表

1.什么是哈希表

哈希表又叫散列表，是一种根据设定的映射函数f(key)将一组关键字映射到一个有限且连续的地址区间上，并以关键字在地址区间中的“像”作为元素在表中的存储位置的一种数据结构。这个映射过程称为哈希造表或者散列，这个映射函数f(key)即为哈希函数也叫散列函数，通过哈希函数得到的存储位置称为哈希地址或散列地址

简单来说哈希表就是通过一个函数 f(key) 将一组元素散列存储到一个数组中的数据结构

2.什么是哈希冲突

对于不同的关键字，可能得到同一个哈希地址，即key1≠key2,而 f(key1)=f(key2)，对于这种现象我们称之为哈希冲突，也叫哈希碰撞

当要散列存储的元素大于数组的长度时必然会出现哈希冲突 鸽笼

3.如何处理哈希冲突

• 开放定址法，当发生哈希冲突时继续以某种方式再次寻找哈希表中的其他位置直到找到一个空的位置，如线程探测再散列和二次探测再散列
• 再哈希法，选择多个哈希函数，当发生哈希冲突时计算另一个哈希函数直到没有冲突为止
• 建立公共溢出区，维护一个溢出表当发生哈希冲突时把元素放入溢出表
• 链地址法，当发生哈希冲突时将冲突的元素以链表的方式存储 HashMap 就是使用的这种方式

4.链地址法的缺点

极端情况下搜索元素都在一个位置上，哈希表退化成了链表，这种情况可以把链表转话为红黑树（Java 1.8 HashMap 的优化点）

二、equals 与 hashCode 函数的关系

equals 与 hashCode 都是用来比较对象相等，但是重写 equals 的逻辑一般比较复杂效率比较低，而 hashCode 只需要比较一个 hash 值就可以，但是 hashCode 函数并不完全可靠，有时候不同对象的 hash 值也会相同。总结一下就是当两个对象 equals 相等时 hashCode 一定相等 equasl 绝对可靠，当两个对象 hashCode 相等时 equals 不一定相等 hashCode 不一定可靠。所以在一些哈希容器中会先用 hashCode 去对比，如果 hashCode 不相等则两个对象肯定不相等，如果 hashCode 相等再去比较 equals 是否相等 equals 也相等的话才认为是同一个对象，这样既提高了效率又保证了正确性。

三、HashMap

对于 HashMap 源码的分析基于 Java 1.8

1. 负载因子

HashMap 和 HashSet 都具有允许直接传入负载因子的构造器，表示当负载情况达到负载因子的水平时容器将自动增加其容量，实现方式是使容量大致加倍，并重新将现有对象分布到新的数组中（这也称为再散列）。HashMap 的默认负载因子时 0.75 这在时间和空间上达到了平衡，更高的负载因子可以节省空间但是增加了查询时间（查找是我们在大多数时间里所做的动作，包括 get 和 put），如果知道将要在 HashMap 中存储多少元素可以创建一个合适容量的 HashMap 避免再散列的开销

2. 计算 key 应存储在数组中的位置

1. 首先调用 key 的 hashCode 函数
2. 将第一步计算的值右移 16 位再与自己进行异或运算，结果就是高 16 结果不变低 16 位与高 16 位进行异或运算，其实就是对低 16 位进行再次处理，这一步称为扰动处理（扰动函数）。因为通常情况下一步与运算的时候都只有后面的低位参与运算，扰动处理是为了高位也参与运算。
3. 用第二步计算的值与数组长度 -1 进行与运算得到的结果就是 key 在数组中应该存储的位置

所有的处理都是为了尽量保证均匀分布

3. 容量是 2 的幂的作用

    static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

HashMap 传入容量的构造函数里会调用上面的函数保证容器的容量是 2 的幂次方，作用有两个

• 当 x = 2 ^ n（n 为自然数）时，a % x = a & (x - 1) 为了使用位运算代替取模运算提高效率
• 如果容量是奇数那么 - 1 就是偶数转为二进制则最后一位为 0 与其他值进行与运算最后一个也肯定是 0 则所有 key 都会映射到数组的偶数下标上则丢失了一半的存储空间，容量为偶数 -1 为奇数转化为二进制最后一位为 1 则与其他值与运算的结果取决于其他值，尽量保证了均匀分布

与运算说的就是 ‘计算 key 应存储在数组中的位置’ 中的第三步

4. put

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 首先判断如果数组为空则初始化，调用 HashMap 的构造方法的时候并没有初始化数组，所以数组的初始化时机是第一次 put 元素的时候
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果最后计算的指定下标位置为 null 说明没有哈希冲突，则直接在该位置创建节点    
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        	// 否则说明有哈希冲突
            Node<K,V> e; K k;
            // case1 判断存在的元素的 key 与要插入的 key 是否相等，先判断 hash 再判断 equals 如果相等则使用新元素替换旧元素
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
            // case2 当前节点是红黑树，插入或更新红黑树的节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            // case3 链表，在这里做了两件事，第一，遍历链表找到第一个空位置也就是链表尾创建一个节点插入，第二，判断是否超出数化阈值超出则数化（数化阈值 TREEIFY_THRESHOLD = 8）
                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;
                }
            }
            // 这里是真正新元素替换旧元素的操作，上面只是在需要的时候对 e 赋值，不影响流程
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 这里是 LinkedHashMap 重写了的几个方法用于实现 LRU 算法
                afterNodeAccess(e);
                // 如果是使用新元素替换旧元素则 put 流程结束，否则判断是否需要扩容
                return oldValue;
            }
        }
        ++modCount;
        // 超出扩容阈值则扩容，扩容阈值 = 数组长度 * 负载因子
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

5. resize

    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 >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 如果扩容为当前数组容量的 2 倍后也不会超出最大值则扩容为当前数组容量的 2 倍
            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;
            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;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
        // 扩容非初始化操作则把老数组的元素异动到新数组中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> 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;
    }

由于数组扩容是扩充到原数组的 2 倍所以再次计算元素的位置时相当于数组长度的部分高位多一个 1 相应的 hash 值的部分也要在高位多出一位参与计算，因为数组长度部分是 1 所以计算结果取决于 hash 值的即将参与计算的高位，所以如果 hash 值即将参与计算的高位是 0 则计算结果与扩容之前的计算结果相同还在原来的位置，如果 hash 值即将参与计算的高位是 1 则计算结果是扩容之前的计算结果加上扩容前的数组的长度

6. get

    public V get(Object key) {
        Node<K,V> e;
        // Node 是 HashMap 中对应的链表的实现类
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 计算 key 在数组中的位置然后去对应的位置去找
        // 如果为空则返回 null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                // 如果第一个节点 hash 和 equals 都相等则返回此节点
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                // 如果当前节点是红黑树
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                // 否则说明是链表则遍历查找 hash 值和 equals 都相等的元素
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

7. remove

    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;
        // 计算 key 在数组中的位置然后去对应的位置去找
        // 如果为空则返回 null
        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)
                // 红黑树找出 key 相等的元素赋值
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                    // 遍历链表找出 key 相等的元素赋值
                        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;
    }

四. 其他

扩容的时机：put
链表转化为红黑树的时机：put
红黑树转化为链表的时机：remove 和扩容再散列
链表转为红黑树的阈值：8
红黑树转为链表的阈值：6
最小树化的容量阈值：32 超出此值才允许链表转化为红黑树否则直接扩容
HashMap 的迭代器是 fail-fast 的，fail-fast 是 Java 集合中的一种机制，在用迭代器遍历一个集合时，如果遍历过程中对集合进行了修改则抛出 ConcurrentModificationException 异常。原理就是在创建迭代器对象的时候记录 HashMap 修改的次数（modCount）并且在遍历的时候比较记录的 modCount 与 HashMap 的 modCount 是否相等，不相等则抛出异常
HashMap 是线程不安全的，多线程场景有三种选择：

• 使用 java.util.Collections#synchronizedMap 创建线程安全的 map
• java.util.Hashtable
• java.util.concurrent.ConcurrentHashMap

参考

这些文章都比本文写得好：
面试官：哈希表都不知道，你是怎么看懂HashMap的？
Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？
《我们一起进大厂》系列-ConcurrentHashMap & Hashtable