HashMap源码解析

HashMap 的底层数据结构是： 数组 + 链表（或红黑树）

源码：

transient Node[] table;

而 Node 其实是个链表，在 Node中除了存有 k，v外还有 next（类似指针，指向下一个元素）

static class Node implements Map.Entry {
        // 若 key == null,则 hash值是0，否则 hash = (h = key.hashCode()) ^ (h >>> 16)
        final int hash;     
        final K key;   // 键
        V value;       // 值
        Node next;  // 下一个元素的引用
}

当链表的长度大于 8 时，链表转换为红黑树。

默认加载因子是 ：0.75

默认初始化大小：16 （第一次 put 的时候完成初始化）

当 HashMap 中元素的实际数量 大于 容器大小 * 加载因子 （最初的是 16 * 0.75 = 12）时，HashMap 将实现扩容。

用于往 Map 从存 k,v 键值对，若在 Map中存在 k，则将老的 v 返回。

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

先使用 hash 方法，对key进行hash运行

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

putVal 方法：用于将我们 k,v键值对插入到 HashMap中，具体如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
// 第一次 put，初始化容器大小16
        if ((tab = table) == null || (n = tab.length) == 0) 
            n = (tab = resize()).length;      // n = 16
        
 // 没有 hash 冲突的情况，直接将数据插入到 table数组中
        if ((p = tab[i = (n - 1) & hash]) == null) 
            tab[i] = newNode(hash, key, value, null);
        else {
 // 发生 hash 冲突的情况
            Node e; K k;
            // 如果插入的 key，在 table中已经存在了，这将用新的 v 替换掉老的 v，
            // 并将 老的 v 返回
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 将数据插入到红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
    // 发生hash冲突，将数据插入到链表
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
     // 链表长度大于8的情况，则转换为红黑树
                        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;
                }
            }
            // 将老的 v 返回
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
// 添加完元素后，如果实际大小达到可用大小的 0.75时，则实现扩容存在
        if (++size > threshold)  
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    public static void main(String[] args) {

        HashMap maps = new HashMap<>();
        maps.put("k1", "v1");
        maps.put("jj", "v3");
        maps.put("ss", "v8");

 源码配图：

该方法用于获取 Map 中 key对应的值。

    public V get(Object key) {
        Node e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

使用 hash 算出 key 的 hash值，然后调用 getNode 方法查找数据

    final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
// 1、现在数组中查找，使用 hash值进行运算得到一个角标，获取角标中的元素
// 如果该元素为空，那不用找了，在 map中没有 key对应的值
// 如果该元素不为空，则先判断一下该元素是不是我们要找的key
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 2、该元素就是我们找到 key，则将 k,v 键值对返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 3、数组中没找到，就到链表中查到
            if ((e = first.next) != null) {
                // 4、如果此时链表变成红黑树的话，就到红黑树上找
                if (first instanceof TreeNode)
                    return ((TreeNode)first).getTreeNode(hash, key);
                do {
                // 5.在链表中查到到
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }