这是一个面试经常会问到的问题。
底层原理是数组和链表，JDK 8以后添加了红黑树。
了解原理前，需要先了解以下概念：

hashCode, equals, 取模运算, 数组, 链表, 还有一些位运算

工具

分析原理最好使用能查看堆栈信息的工具，我这里用了idea的debug功能。如果你直接使用idea的debug是无法直接查看真实的map，因为idea为了更加直观的展示map中的数据，做了专门的优化，一开始你看的是这样的：

我们需要修改一下设置，在settings中搜索debug，找到data views->java, 然后可以看到这个，我们需要把那个Enable alternative view for Collections classes 关掉，这样就可以看到map的真是结构了。

hashMap分析

我们最常用的就是put方法，向hashMap中put数据。

HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("语文", 1);
map.put("数学", 2);
map.put("英语", 3);
map.put("历史", 4);
map.put("政治", 5);
map.put("地理", 6);
map.put("生物", 7);
map.put("化学", 8);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

我们来看一下内存的情况：

Node

我们发现数据都存在了一个table的数组里，table的声明为：transient Node[] table;, 它是一个数组，数组的类型为Node。我们来看一下：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;  // 是指Key的hash值，算法是key的hashCode高16位与低16位相与，为了降低hash冲突、碰撞
    final K key;
    V value;
    Node<K,V> next;  // next，为链表的特性
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) { // 会比较k v的equals
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

resize()

上边看到table的大小为16，这里是为什么呢？通过查找赋值过程，我找到了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倍
        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; // 默认16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  // 0.75*16 = 12 触发扩容的临界值
    }
    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
    table = newTab;
    if (oldTab != null) {  // 迁移旧table数据
        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;  // 与table大小-1相与，得到新的index
                else if (e instanceof TreeNode) // 拆分树形的node
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order   // 拆分链表形的node
                    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) { // 这种情况下，node还在原来的index下
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {     // 这种情况下，node还在原来的index+j下
                            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;
}

以上就是table的创建以及扩容的过程，我们可以看到默认大小是16，扩容是以二倍的方式去扩容的，而开始扩容的时机为达到容量的0.75。
扩容过程中，会把就数据复制到新的table中，这里分为三种情况:node无next、next为树形、next为链式。

put()

我们在看一下put的实现：

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

/**
 * 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  如果为true，这不会改变现有值
 * @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;  // n为table大小
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;  // 创建新的table
    if ((p = tab[i = (n - 1) & hash]) == null)  // 获取index，并将index位置的node赋给p， (n - 1) & hash  会得到一个0~(n-1的数)，其实可以理解成hash%(n-1)
        tab[i] = newNode(hash, key, value, null);  // 该index下 无数据，直接赋值
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))  // 存在相同的key，接下来会进行替换
            e = p;
        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) {
                    p.next = newNode(hash, key, value, null);  // 新建node 插入尾部
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);  // >=7时，转换为树 
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))  // key相同，更新value
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);  // linkedHashmap利用这个排序
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();  //  是否需要扩容
    afterNodeInsertion(evict);  // linkedHashmap利用这个排序
    return null;
}

get()

当我们从hashMap中获取key对应的对象时，需要用的get方法

public V get(Object key) {
    Node<K,V> e;
    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;
    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))))
            return first;
        // 未命中
        if ((e = first.next) != null) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

总结

  1. 如何确定存进来的对象的位置
    首先，会对key的hashCode方法进行运算，生成一个新的hash，这个运算方法为：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 即使用hashCode的高16与低16位相与。我们知道hashCode为int类型，int占4个字节，也就是4 * 8 = 32位。得到新的hash后，通过(n - 1) & hash得到在数组中的位置。
    如果这个位置上没有东西，则直接赋值过去，
    如果有东西：

    • 会先判断是不是相同的key，如果key相同则替换value
    • 是否为红黑树，进行红黑树的操作，新增或者替换
    • 是否为链表，进行链表的操作，新增或者替换

  2. 链表转为红黑树的条件
    如果一个链表的长度超过了TREEIFY_THRESHOLD = 8;, 那么就会将这个链表转成红黑树

  3. table的扩容过程
    默认情况下，table的初始大小为DEFAULT_INITIAL_CAPACITY = 16, 扩容因子为DEFAULT_LOAD_FACTOR = 0.75f, 当map的size达到了table.length * 扩容因子时，就会触发扩容。扩容时，table会变成原来的2倍，table中的数据也会重新计算位置。

参考

https://www.bilibili.com/video/BV1Pp411d7kB
https://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
https://zhuanlan.zhihu.com/p/31610616

HashMap在多线程下的问题

  1. 使用HashMap真的发生线程安全问题，会造成什么后果？

    1. 可能造成死循环，多线程同时对线程进行put时，如果正好触发了扩容机制，这时可能会在扩容时产生一个环形链表，这时在get时会造成无限循环。
    2. 多线程进行put，如果正好发生了Hash碰撞，可能导致元素覆盖丢失的情况。

  2. 替换方案
    使用HashTable或者ConcurrentHashMap进行替换。HashTable的安全的原理是对读写方法加了Synchronized关键字，保证只有一个线程可以对HashTable进行读写操作，从而实现了线程安全。这种方式效率较低，是不推荐使用的。ConcurrentHashMap是通过Synchronized代码块实现的线程安全，Synchronized锁的对象为HashMap中的Hash数组的Key值，也就是说对于Hash碰撞这种情况下，会通过锁将这个链表或者红黑树锁住，防止多线程同时读写该结构，但是在Hash没有发生碰撞的情况下，多个线程对不同的链表或者红黑树读写是不会受锁的限制，这样既保证了一定的效率，又保证了线程安全。

Java

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

Android监控Java层联网动作 上一篇
CopyOnWriteArrayList的优点及原理 下一篇