Map源码解析

电玩女神 2024-04-06 15:58 131阅读 0赞

## 基本介绍 ##

其实HashMap底层是个什么东西我们之前也讲过, 就是一个哈希桶(差不多可以看成一个数组), 然后每一个节点又连接着链表/红黑树之类的, 下面让我们看一看具体在源码上是怎样实现的:

## ![5e894569f49d4e67a9f0720a50490eaf.png][] ##

## 常量及其它 ##

> \-> static final int DEFAULT\_INITIAL\_CAPACITY = 1 << 4;
> 
> //这个指代的是**哈希桶的大小**, 默认为16
> 
> \-> static final float DEFAULT\_LOAD\_FACTOR = 0.75f;
> 
> //**默认的负载因子** \-> 0.75
> 
> \-> static final int TREEIFY\_THRESHOLD = 8;
> 
> //**树化的条件之一**, 就是指当一个节点上的链表长度大于8时(也不一定是8, 但跟8是有关的, 后面讲put的时候再说),就会从链表转换为红黑树
> 
> \-> static final int MIN\_TREEIFY\_CAPACITY = 64;
> 
> //**树化的条件之一**, 就是指当哈希桶的大小如果大于64(数组的长度), 就会将链表转换成红黑树
> 
> \-> static final int UNTREEIFY\_THRESHOLD = 6;
> 
> //解树化的条件, 当红黑树的大小小于8时, 就会从红黑树转换回链表.
> 
> \-> static class Node<K, V> implements Map.Entry<K, V> \{...
> 
> **这段代码定义了一个静态内部类'Node', 该类实现了'Map.Entry<K, V>'接口, 表示哈希表中的一个节点, 用于存储键值对**.

## 构造方法 ##

### 含指定容量, 负载因子的 ###

public HashMap(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }

> 这个是提供了指定容量, 负载因子的, 玩家可以自行设置这两个参数. 需要注意的是在:
> 
> if(initialCapacity > MAXIMUM\_CAPACITY) \{\}
> 
> 这个中, MAXIMUM\_CAPACITY是指1>>30, 也就是说当玩家设置的值大于这个值之后, 就会被设置为这个值(显而易见, 为了防止移除)

### 含指定容量的 ###

public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

> 这个很好理解, 就是当不给负载因子时, 就是默认的0.75, 然后通过this()调用上面的构造方法.

### 俺一无所有 ###

public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

> 这个就比较令人匪夷所思了, 它只有默认的负载因子(当然,还是0.75). 然后奇怪的是**它居然没有给设置容量**! **没事, 让子弹飞一会**.

## put方法 ##

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

让我们先来看一下里面的hash()方法.

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

> 这里采用了将key的hashCode()值与h右移 16位取异或得到哈希值.
> 
> 这种位操作目的是将hashCode()返回的高位和低位进行混合, 增加哈希值的随机性和分布性, 从而减少哈希冲突的概率.

再来看一下putVal()方法.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    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);
                            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;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

> 不难发现在4, 5行中,
> 
>     if ((tab = table) == null || (n = tab.length) == 0)
>         n = (tab = resize()).length;
> 
> 我们发现当这个传来的哈希标为空/或者大小为0时, 会让表调用resize().

这里是resize()中的部分内容:

>     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
> 
>     table = newTab;
> 
> 通过这个, 我们就可以得出结论, 在第一次put的时候, 哈希桶大小分配为了默认的newCap(其实是16).

> 继续分析putVal()方法中的剩余部分.
> 
>     if ((p = tab[i = (n - 1) & hash]) == null)
>         tab[i] = newNode(hash, key, value, null);
> 
> 在这里, 就是哈希表中插入新键值对的逻辑(就是哈希桶这个位置为空), 通过(n - 1) & hash的方式映射到数组索引i上, 这是因为 'n'应该是2的幂次方(即哈希表长度应该是2的幂次方), 才能保证哈希值均匀分布. 然后调用newNode完成了插入操作.

>     p.next = newNode(hash, key, value, null);
>     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
>         treeifyBin(tab, hash);
>     break;
> 
> 当需要插到链表/红黑树上时, 就需要通过尾插法插入, 在这里, 我们发现, 当链表长度大于 8 - 1时, 就会通过treeifyBin方法进行树化.

那么到这里就讲完了(我讲的是比较爱考的), 其它部分如果感兴趣的话希望你们自己看看源码推理推理.

下了...

[5e894569f49d4e67a9f0720a50490eaf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/e2e2cf1e714249649f59aa657964fec8.png