【Java】20211019_Java集合_HashMap（JDK1.7）

一、链表

链表是不连续的内存空间，单向链表之间通过持有下一节点的内存地址来指向。

二、HashMap的底层结构

JDK1.7的HashMap底层结构（见代码块2-1）：数组+链表；

[^_代码块2-1]

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 * 根据需要对数组table扩容，但需要保证数组的长度始终是2的幂次。
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

数组的标志——"[]"有了,再看作为链表结构的Entry<K,V>（见代码块2-2）：

[^_代码块2-2]

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;    // 持有下一Entry节点的地址
    int hash;
}        

每个Entry节点中都持有下一节点的地址，一个接一个形成链表结构。

三、为什么是【数组+链表】

个人猜想：数组查询快，链表增删强，强强来联手，两者得益彰。

四、从构造方法开始，看看码

在JDK1.7，HashMap提供了四种构造，这里只贴其中三种的代码（见代码块4-1）分析。

[^_代码块4-1]

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 * 构造一个还没有放入任何元素的HashMap，其初始化容量为16，默认的加载因子0.75
 */
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

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

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;
    threshold = initialCapacity;
    init();
}   

如果在创建HashMap时，没有指定初始化容量，就会默认初始化一个容量为16的HashMap。指定了容量，那就按指定的来，不过在put方法时还是会根据这个容量做调整。

在看put方法前，先看一下别的方法，省得一会儿跳来跳去看代码晕乎了。

inflateTable方法（见代码块4-2）：

[^_代码块4-2]

/**
 * Inflates the table.
 */
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
(1)    int capacity = roundUpToPowerOf2(toSize);

(2)    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
(3)    table = new HashMap.Entry[capacity];
(4)    initHashSeedAsNeeded(capacity);
}

static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824->不用数了,10个亿多

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

(1)roundUpToPowerOf2方法整体看下来，【较大概率】只会发生一件事：将传入的任意值，通过运算，返回一个【大于等于】传入值又在数值上最接近传入值的2次幂数。

(2)这行代码【较大概率】会将上一步的返回值与0.75做乘法，将得到的值赋给threashold——中文翻译：阈值。

(3)构造一个容量为roundUpToPowerOf2方法返回值的新数组替换掉HashMap中原有数组。

(4)略。

put方法（见下图：）

努力让自己不那么菜

明天就1024了，本来今天网络冲浪的时候微信群里发现了个GIF，想分享出来。

但因为我不知道微信咋保存，所以去B站扒了个相同的视频下来想视频转GIF，但是喵了个咪的现在的工具就想着收钱，干活的时候网速飞慢，要钱的时候伸手贼快，我又比较穷，就面向搜索引擎找了个代码跑了下把GIF给生成了。

欲速则不达，每天进步一点点。