HashMap源码及面试知识点

淩亂°似流年 2023-07-02 03:16 3阅读 0赞

## （1）HashMap 的原理，内部数据结构？ ##

数组+ 链表（或1.8红黑树）

验证：数组+ 链表

以Node数组的形式存储
    transient Node<K,V>[] table;
    链表，内部类 有一个next节点，表示单向链表
     static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
            ...
          }

## （2） hash算法的作用 ##

为了Node节点 在 数组中的**落点**做了准备工作。

**hash算法**：key.hashCode() 的高16位 ^ 低16位 得到一个result

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

## （3）请你描述一下put 的过程？在源码中怎么体现的？ ##

`map.put(1,“arthur”)`  
a. 根据key的hashCode 值得到一个备用的result

b. 初始化数组的大小

判断当前 Node节点的数组是否为空，如果空，那么先初始化当前的数组

if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;

将数组的默认大小16 赋值给 newCap, newThr = 16 \* **DEFAULT\_LOAD\_FACTOR**

else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }

创建newCap大小的newTable 赋值给table

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;

c. 根据hash算法 & n-1 得到数组下标位置，判断该位置是否存在元素

if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);

根据key,value 值 组装成Node节点

hash值 & 15 等价于 hash%16\[0-15\] -–》 效率高

计算出下标的位置

d. 得到了数组下标的位置，并且不为空

//1.Node 节点中的 key.hash值相同，就覆盖value
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    //2.该节点为红黑树，采取红黑树的put方法
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    //3.循环遍历链表，若长度超过8，则对链表进行树化
    // 1.8采取红黑树对过长的链表进行树化，为了防止链表过长所导致的 查询速度太慢
    else {
        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 (++size > threshold)
                resize();

16 1 2 4 …

需要扩容

12 12/16 = 0.75

扩容因子 默认为0.75L
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

resize() 另一个功能 就是进行数组的**扩容**

将数组的大小变大，数组的大小是 2 ^ n

## (4) HaspMap扩容是怎样扩容? ##

a. 先判断当前的容量 ,比最大容量2^30小，并且大于默认容量

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold

b.将原先的数组 -–> 新的数组

遍历原始数组

for (int j = 0; j < oldCap; ++j) { ...}

（1） 数组有元素，下面为null

if (e.next == null)
    // 根据hash重新计算数组位置
                            newTab[e.hash & (newCap - 1)] = e;

（2）数组位置有元素，下面不null，红黑树

else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

（3）数组位置有元素，下面不null，链表

else { // preserve order
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;

下面算法直接省略了重新计算的过程

链表中的节点的位置只有可能在两个位置

*  原来的位置
 *  原来的位置+oldCap

next = e.next;
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }

## (5)容量为什么都是2的N次幂的大小? ##

**容量是2的n次幂，进行位运算时减少hash碰撞，可以使得添加的元素均匀分布在HashMap中的数组，避免形成链表的结构，使得查询效率降低！**

参考：[容量为什么是2的幂次方][2]

--------------------

You can‘t wait forever .Do something and make it happen.

[2]: https://blog.csdn.net/apeopl/article/details/88935422