ArrayList
ArrayList是用数组 + size属性来实现的，例如添加的时候，会保存以后给size + 1.
HashMap
结构
底层实现为数组 + 链表，如下：
原理
Put的原理
put(key, value);
- 将key做hash;
- 得到的hash值转化成数组下标，例如对16取余，在实际实现中是 h & (length - 1);
- 如果出现了相同的下标，用链表连接（头插法，插到头部而非插到尾部），对象都保存在堆中；
- 将对象的地址保存在数组中。
数组的大小？
默认是16，可以传值，例如10，就会去找到大于10的2的幂次方，也就是16。如果传的是17，那就取32。
为何必须是2的幂次方？
因为在取下标的过程中， h & (length - 1); 要保证：
- 小于我们的数组长度；
- 下标平均随机出现；
当length = 16时，即length - 1 = 15; 二进制表示为0000 1111
与h按位与，假设h为1010 0011, 得到0000 0011，即h的低4位。
1010 00110000 1111----------0000 0011
结果就保证了：
- 小于数组长度，因为得到的结果位0000 0000 ~ 0000 1111
- 随机出现，因为h代表的是hash值，hash随机，则结果随机。
如何找到大于某个值的最小的2的幂次方？
方法1：循环
方法2：参考Integer.highestOneBit() 方法，调用Integer.numberofLeadingZero方法。
highestOneBit方法可以找到小于等于value的最小的2的幂次方，如highestOneBit(17) 返回 16。
key可以为null嘛？
可以，会放在数组的第0个位置。
扩容
扩容需要两个条件：
- size >= threshold , size保存的是map中元素的数量，threshold = length * 0.75, length默认是16.
- null != table[bucketIndex] 即要放的那个位置上是有值的。
条件2在JDK8中被移除了。
扩成多少？
翻倍
resize(2 * table.length);
如何扩容？
先生成一个新的数组，新数组的长度为旧数组的两倍；
Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity));将新数组传入transfer中，进行数据的转移。
如何转移？
- 遍历老数组
- 一次将老数组每个下标对应的值逐个转移过去，转移的时候，下标要么不变，要么等于老下标 + 原数组长度，因为： ```
// 老下标 1010 0011 1010 0011 0000 1111 0001 1111
& &
0000 0011 0000 0011 -> 不变
// 或者 // 老下标 1011 0011 1011 0011 0000 1111 0001 1111
& &
0000 0011 0001 0011 -> 低4位不变，第5位参与进来了
```java
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 获取下标，要么不变，要么多取一位
int i = indexFor(e.hash, newCapacity);
// 逐个转移，将导致逆序
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
- 此外，转移的时候因为是从第一个开始转移的，所以链表的第一个会变成最后一个。即1->2->3会变成3->2->1。
- 而且，链表扩容的真正目的不仅仅是扩容，而是为了将链表剪短。如2中提到的，新的下标有两种结果，那么就可以将链表剪短，从而提高查找效率（链表越长，遍历时间越长）
多线程导致死循环
在多线程操作的时候，转移可能会导致循环链表出现，具体原因参考链表第二节课50分钟左右。而一旦出现循环列表，就会导致get或者set的时候死循环。因此线程不安全。
源码
Put方法
将key，value放入Map中
public V put(K key, V value) {
// 若数组为空，则初始化数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果key为null，则把其放到数组的第一个位置
if (key == null)
return putForNullKey(value);
// 得到key的哈希值
int hash = hash(key);
// 通过哈希值和数组大小获取下标
int i = indexFor(hash, table.length);
// 遍历链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果key存在，哈希值也相等，说明是同一个key，覆盖旧的值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 否则添加新的Entry,这里采用的是头插法
addEntry(hash, key, value, i);
return null;
}
InflateTable方法
初始化Table的方法
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// capacity设置为大于toSize的最小2的幂次方
// 例如，当toSize为15时，capacity为16,
// 当toSize为17时，capacity为32
int capacity = roundUpToPowerOf2(toSize);
// 阈值 = capacity * loadFactor， 只要小于最大容量
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// new这个数组
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
IndexFor方法
根据Hash值和表的长度获取要放的下标的方法。
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
见上面具体分析“为什么要为2的幂次方”
AddEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
// size表示所有的键值对的数量
// 如果size >= 阈值并且要放置的位置上不为空，进行扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容成两倍大小
resize(2 * table.length);
// 重新计算key的哈希值
hash = (null != key) ? hash(key) : 0;
// 重新计算新的下标
bucketIndex = indexFor(hash, table.length);
}
// 如果不需要扩容，直接新建一个Entry进行插入
createEntry(hash, key, value, bucketIndex);
}
虽然这里重新计算了Hash，但我认为其实Hash值没有变化，因为都是调用同一个Hash算法，只是下标会变而已。
Resize方法
对数组进行扩容
void resize(int newCapacity) {
// 旧的数组
Entry[] oldTable = table;
// 旧的数组的长度
int oldCapacity = oldTable.length;
// 如果旧的数组长度已经达到了最大值（1 << 30， 就是2的30次方）
// 不扩容而是设置成最大的整数
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// new一个新的数组，长度为旧数组的两倍
Entry[] newTable = new Entry[newCapacity];
// 将旧数组的数据转移到新数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 覆盖掉旧数组
table = newTable;
// 重新计算扩容阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Transfer方法
将旧数组中的所有值转移到新数组中去
// 参数为新数组和是否需要rehash
void transfer(Entry[] newTable, boolean rehash) {
// 新数组长度
int newCapacity = newTable.length;
// 遍历旧数组
for (Entry<K,V> e : table) {
// 遍历链表
while(null != e) {
Entry<K,V> next = e.next;
// 如果需要rehash，就重新reHash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 获取新的下标
int i = indexFor(e.hash, newCapacity);
//头插法进行插入
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
从int i = indexFor(e.hash, newCapacity);可以看出来，新的Index要么不变，要么是原来的index + oldLength；扩容的目的不单单是为了扩容，还有就是将链表剪短，从而提高查询效率。
createEntry方法
根据key和value来new一个新的Entry，采用头插法进行插入:
void createEntry(int hash, K key, V value, int bucketIndex) {
// 旧的头结点
Entry<K,V> e = table[bucketIndex];
// 新的头结点指向旧的头结点，头插法
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 数量 + 1
size++;
}
若有收获，就点个赞吧
0 人点赞
