大厂面试官：请你手写一个HashMap

HashMap本质是一个一定长度的数组，数组中存放的是链表。

它是一个Entry类型的数组，Entry的源码：

static class Entry<K,V> implements Map.Entry<K,V> { 

   final K key; 

   V value; 

   final int hash; 

   Entry<K,V> next; 

}

其中存放了Key，Value，hash值，还有指向下一个元素的引用。

当向HashMap中put(key,value)时，会首先通过hash算法计算出存放到数组中的位置，比如位置索引为i，将其放入到Entry[i]中，如果这个位置上面已经有元素了，那么就将新加入的元素放在链表的头上，最先加入的元素在链表尾。比如，第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起,也就是说数组中存储的是最后插入的元素。

扩容机制：

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容。

HashMap的容量由一下几个值决定：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   // HashMap初始容量大小(16) 

static final int MAXIMUM_CAPACITY = 1 << 30;        // HashMap最大容量

transient int size;                    // The number of key-value mappings contained in this map

static final float DEFAULT_LOAD_FACTOR = 0.75f;     // 负载因子

HashMap的容量size乘以负载因子[默认0.75] = threshold; // threshold即为开始扩容的临界值

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  // HashMap的基本构成Entry数组

当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置。

相信看到这里你也大致理解了HashMap的原理，但是真要手写一个还是要去看一遍源码的。

自己IDEA上手写了一个简单版的HashMap，给大家参考。

public class SaxHashMap<K, V> {

    Node[] table; //hashmap数组
    int size; //hashmap节点个数
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  //负载因子

    public void put(K key, V value) {
        if (table == null) table = new Node[16];
        // 大于负载因子开始扩容
        if (size / table.length >= DEFAULT_LOAD_FACTOR) rehash();

        // 计算插入位置索引
        int idx = hash(key) & (table.length - 1);
        Node<K, V> node = new Node(idx, key, value, null);

        if (table[idx] == null) {
            table[idx] = node;
            size++;
        } else {
            Node tNode = table[idx];
            // 看链表上是否有key相同节点
            while (tNode != null) {
                if (tNode.key.equals(key)) {
                    tNode.value = value;
                    return;
                }
                tNode = tNode.next;
            }
            // 将新的节点插入链表头
            tNode = table[idx];
            table[idx] = node;
            node.next = tNode;
            size++;
        }

    }

    public V get(K key) {
        if (table == null) return null;
        int idx = hash(key) & (table.length - 1);
        Node tNode = table[idx];
        while (tNode != null) {
            if (tNode.key.equals(key))
                return (V) tNode.value;

            tNode = tNode.next;
        }
        return null;
    }

    /**
     * 计算hash值
     */
    public int hash(Object key) {
        return key.hashCode() ^ (key.hashCode() >>> 16);
    }

    /**
     * 扩容
     */
    private void rehash() {
        // 创建新的hash表
        Node[] newtable = new Node[table.length << 1];
        Node tNode = null, pNode = null;
        int idx, len = newtable.length - 1;
        //将旧的hash表的数据移到新hash表
        for (int i = 0; i < table.length; i++) {
            tNode = table[i];
            while (tNode != null) {
                pNode = tNode.next;
                idx = tNode.hash & len;
                tNode.hash = idx;
                if (newtable[idx] == null) {
                    newtable[idx] = tNode;
                    tNode.next = null;
                } else {
                    tNode.next = newtable[idx];
                    newtable[idx] = tNode;
                }
                tNode = pNode;
            }
        }
       // 将新的hash表替换旧的hash表
        table = newtable;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < table.length; i++) {
            Node tNode = table[i];
            while (tNode != null) {
                sb.append(tNode.key.toString()).append("-").append(tNode.value.toString()).append(",");
                tNode = tNode.next;
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");

        return sb.toString();
    }

   static  class Node<K, V> {
        int hash;
        K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}