HashMap
截屏2020-02-15下午12.18.29.png
HashMap
1.数据要存储
// table就是HashMap实际存储数组的地方
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
2.数组的插入和查找
public V put(K key, V value) {
// 当插入第一个元素的时候，需要先初始化数组大小
if (table == EMPTY_TABLE) {
// 数组初始化
inflateTable(threshold);
}
// 如果 key 为 null，感兴趣的可以往里看，最终会将这个 entry 放到 table[0] 中
if (key == null)
return putForNullKey(value);
// 1. 求 key 的 hash 值
int hash = hash(key);
// 2. 找到对应的数组下标
int i = indexFor(hash, table.length);
// 3. 遍历一下对应下标处的链表，看是否有重复的 key 已经存在，如果有，直接覆盖，put 方法返回旧值就结束了
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // key -> value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 4. 不存在重复的 key，将此 entry 添加到链表中
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果当前 HashMap 大小已经达到了阈值，并且新值要插入的数组位置已经有元素了，那么要扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容，容量 * 2
resize(2 * table.length);
// 扩容以后，重新计算 hash 值
hash = (null != key) ? hash(key) : 0;
// 重新计算扩容后的新的下标
bucketIndex = indexFor(hash, table.length);
}
// 创建元素
createEntry(hash, key, value, bucketIndex);
}
// 将新值放到链表的表头，然后 size++
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize 保证数组大小一定是 2 的 n 次方。
// new HashMap(519)，大小是1024
int capacity = roundUpToPowerOf2(toSize);
// 计算扩容阈值：capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 初始化数组
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
// 确定key对应的数组位置,遍历查找比对链表内容
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}//但在1.8中若链表中节点过多会转化为红黑树。
虽然Hashtable是一个线程安全的类，但性能不高，在高并发的场景下使用ConcurrentHashMap
ConcuttentHashMap
1. 数据存储
/**
* The segments, each of which is a specialized hash table. 每一段都是一个hash表
*/
final Segment<K,V>[] segments;
static final class Segment<K,V> extends ReentrantLock implements Serializable {...
transient volatile HashEntry<K,V>[] table;
...}
2.数组的插入和查找
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key); // 根据key找segment
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments; // return ss[i];
long u = (k << SSHIFT) + SBASE; // raw offset // 数组内存地址定位
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {// 如果不存在,就创建一个
Segment<K,V> proto = ss[0]; // use segment 0 as prototype 第一个segment作为原型
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // recheck
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
关于HashMap和ConcurrentHashMap建议看这篇文章：
JDK源码学习方法更重要。
逻辑思维能力是梳理学习方法的基础。养成线性思维：两个或者多个概念，像一条线串起来。
- 演绎推导法
示例：因果推理。因为Java中网络编程只提供了BIO和NIO两种方法，所以一切框架中，涉及到网络处理的，都可以用这两个知识点区纠结原理。
- 归纳总结法
示例：可能正确的猜想。线上10台服务器，有三台总是每天会自动重启，收集相关信息后，发现是运维再修改监控系统配置的时候，漏掉了提高这三台机器的重启阀值。
- 类比法
集群概念就好像是马在拉车，一匹马拉不动的时候，就使用多匹马区拉。
分布式的概念，就像是理发的过程中，洗头发和剪头发是不同的人负责的。
