# java容器相关面试
# Map
我们通过 HashMap 来存储 Key-Value 这种键值对形式的数据，其内部通过哈希表，让存取效率最好时可以达到 O(1)，而又因为可能存在的 Hash 冲突，引入了链表和红黑树的结构，让效率最差也差不过 O(logn)。
整体来说，HashMap 作为一款工业级的哈希表结构，效率还是有保障的。
# 用HashMap存1w条数据，构造时传10000会触发扩容吗
# HashMap的初始化
在 HashMap 中，提供了一个指定初始容量的构造方法 HashMap(int initialCapacity)，这个方法最终会调用到 HashMap 另一个构造方法，其中的参数 loadFactor 就是默认值 0.75f。
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);
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
其中的成员变量 threshold 就是用来存储，触发 HashMap 扩容的阀值，也就是说，当 HashMap 存储的数据量达到 threshold 时，就会触发扩容。
HashMap 并不是直接使用外部传递进来的 initialCapacity，而是经过了 tableSizeFor() 方法(转换成2的次幂)的处理，再赋值到 threshole 上。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
那么当我们从外部传递进来 1w 时，实际上经过 tableSizeFor() 方法处理之后，就会变成 2 的 14 次幂 16384，再算上负载因子 0.75f，实际在不触发扩容的前提下，可存储的数据容量是 12288（16384 * 0.75f）
如果改为1k呢？
虽然 HashMap 初始容量指定为 1000，但是它只是表示 table 数组为 1000，扩容的重要依据扩容阀值会在 resize() 中调整为 768（1024 * 0.75）