HashMap的实现原理笔记

摘要：掌握的实现原理，已经是程序员的基础操作了。后记这次主要是理解了一下的实现原理，特别重点写了很多关于散列函数的理解，并没有按照源码一行行的去理解。之前看的时候对散列函数都是跳过去的，只知道是用来计算键的，不知道里面的原理。

HashMap是Java中常用的Map接口的实现类，因为在日常工作中非常频繁的出现，所以在大部分的Java面试中都会问几个关于HashMap的问题。掌握HashMap的实现原理，已经是Java程序员的基础操作了。

映射（Map）是一种用于存放键/值对的数据结构。如果提供了键，就能直接找到相对应的值。HashMap（哈希映射）是Map接口的一个实现类，主要使用哈希来实现键与值的映射。

定义。映射是一种用于存放键/值对的数据结构，主要支持两种操作：插入（put），即将一组新的键值对存入映射中；查找（get），即根据给定的键得到相应的值。

HashMap的底层是用散列表实现的，散列表是一种用数组来存储键值对的数据结构，它使用一个散列函数将键转换成数组的一个索引然后存储值。不过会有不同的键被散列成同个索引的情况出现，这叫做碰撞冲突。HashMap用拉链法来解决这个问题，即散列表数组中的每个元素都指向一条链表，链表中的每个节点都存储了被散列到这个索引的键值对。

根据散列表的定义我们知道，想要弄清楚HashMap的实现，我们首先需要知道HashMap的散列函数是怎么实现的，即HashMap是如何将一个键映射到数组的索引的。

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

上面就是HashMap的散列函数源码了，可以看到如果键为null的话它的索引固定为0，即HashMap是支持使用null作为键的。如果键不为null就用Java对象都有的hashCode方法获得一个哈希值，并将这个哈希值的低16位与高16位做异或处理，高16位不变。

这里有个问题就是为什么不直接用键的hashcode，而要将hashcode的低16位与高16位做异或处理？这里是因为有三个前提：

int有32位

HashMap的数组长度都是2的幂

获取数组索引需要将键的哈希值和数组长度-1做一个与操作（&）得到，即tab[(n - 1) & hash]

首先因为HashMap的数组长度都是2的幂，（n - 1）的高16位都是0，所以只有键的低16位参与索引运算。如果直接用键的hashcode的话，就会有很多碰撞冲突，所以用这种方法使得hashcoede的高16位也参与到索引的运算中来。下面是字符串“1234”在数组长度为16的索引运算过程：

public static void main(String[] args) {
    int hashcode = "1234".hashCode();
    System.out.println(Integer.toBinaryString(hashcode));
    // 输出为 10111 0000100001000010
    System.out.println(Integer.toBinaryString(hashcode >>> 16));
    // 输出为 10111
    System.out.println(Integer.toBinaryString(hashcode ^ (hashcode >>> 16)));
    // 输出为 10111 0000100001010101
    System.out.println(Integer.toBinaryString(16 - 1));
    // 输出为 1111
    System.out.println(Integer.toBinaryString((16 - 1) & (hashcode ^ (hashcode >>> 16))));
    // 输出为 101
}

虽然HashMap对散列函数做了很多优化，但是碰撞冲突还是不可避免的会出现。为了解决这个问题HashMap使用了拉链法，使用链表来存储碰撞冲突的键值对。并在JDK 8中进行了优化，当链表长度到达某个指定值时HashMap会自动将链表优化为红黑树。频繁碰撞冲突还可能是因为数组长度不够的原因，HashMap还会根据键值对的数量进行自动扩容。

在讲HashMap的自动扩容前，先来看看HashMap有哪些相关的属性：

Node[] table; 存放键值对的数组

int size; 已存放键值对的数量

int threshold; 当键值对的数量等于这个值的时候HashMap将进行扩容，值等于数组长度 * loadFactor

final float loadFactor; 负载因子，用于计算threshold的值，默认值为0.75

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 数组长度的默认值16

根据这些属性可以知道，HashMap的自动扩容会根据数组长度和负载因子的积得到一个threshold的值，当键值对的数量等于threshold时就会开始扩容，下面是扩容的源码。大概过程是新建一个长度为旧数组两倍的新数组，并将原有的键值对都重新映射到新数组上。

final Node[] resize() {
        Node[] 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;
            }
            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[] 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;
    }

这次主要是理解了一下HashMap的实现原理，特别重点写了很多关于散列函数的理解，并没有按照源码一行行的去理解。之所以这样是因为写这篇的动力主要来源于面试……而面试则只要讲下原理就可以了，并不需要把源码背下来。之前看HashMap的时候对散列函数都是跳过去的，只知道是用来计算键的hash，不知道里面的原理。其实还有链表转红黑树的地方没有弄清楚，主要是红黑树不怎么理解，基础的重要性体现了出来。

我的博客