- equals 和 == 的区别，hashCode 与它们之间的联系？
- HashMap 的长度为什么是 2 的幂次？
- 五个线程同时往 HashMap 中 put 数据会发生什么？
- ConcurrentHashMap 是怎么保证线程安全的？
上面是一些常见的面试题，本文旨在分析 HashMap 的源码实现思想，并不会去细讲这些问题，在我们看完源码之后不妨自己做一些思考。本文也不会细讲 JDK 1.8 的红黑树和分段锁，这部分内容等我们分析完二叉树之后，再来做一些巩固分析。
我们现在不妨思考一下，假设让我们自己来设计一个类似 HashMap 的类，我估计大部分能想到的是，用一个数组或者用一个 ArrayList 直接来存放一个 Entry 对象，Entry 对象存放 put 的 key 和 value 。因为 HashMap 是不允许键值重复的，如果我们直接用数组来作为存储结构，在不考虑数组扩容的情况下，其查询和插入的复杂度都是 O(n) 级别的。
HashMap 采用数组 + 链表的实现就很好的优化了我们上面所讲的问题，大致的原理是当我们 put 一个 key 和 value 时，我们首先会对 key 进行二次 hash 处理， 然后根据 hash 值找到其所在的数组的角标位置，再去遍历链表判断是否有 key 重复，如果有则覆盖没有则添加。这种实现方式在理想的情况下，查询和添加的时间复杂度是 O(1)，请看下面这张图（长度应该是 2 的幂次）：
图片来源于网络
上面有一步操作是获取 key 的 hashCode() , 然后进行二次 hash ，那么 hashCode() 到底返回的是什么呢？我们不妨来看看源码:
public int hashCode() {
return identityHashCode(this);
}
// Android-changed: add a local helper for identityHashCode.
// Package-private to be used by j.l.System. We do the implementation here
// to avoid Object.hashCode doing a clinit check on j.l.System, and also
// to avoid leaking shadow$_monitor_ outside of this class.
/* package-private */ static int identityHashCode(Object obj) {
int lockWord = obj.shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
return identityHashCodeNative(obj);
}
@FastNative
private static native int identityHashCodeNative(Object obj);
hashCode 最终调用的是 identityHashCodeNative 的 native 方法，之前学的 NDK 现在就可以派上用场了，我们不妨跟踪到 JNI 层去看看里面具体的实现，目录在 jdk\src\share\native\java\lang\Object.c 我们挑一些关键代码：
markOop mark = ReadStableMark (obj);
// 如果当前对象没有锁
if (mark->is_neutral()) {
hash = mark->hash(); // this is a normal header
if (hash) { // if it has hash, just return it
return hash;
}
hash = get_next_hash(Self, obj); // allocate a new hash code
temp = mark->copy_set_hash(hash); // merge the hash code into header
// use (machine word version) atomic operation to install the hash
test = (markOop) Atomic::cmpxchg_ptr(temp, obj->mark_addr(), mark);
if (test == mark) {
return hash;
}
// If atomic operation failed, we must inflate the header
// into heavy weight monitor. We could add more code here
// for fast path, but it does not worth the complexity.
} else if (mark->has_monitor()) {
monitor = mark->monitor();
temp = monitor->header();
assert (temp->is_neutral(), "invariant") ;
hash = temp->hash();
if (hash) {
return hash;
}
// Skip to the following code to reduce code size
} else if (Self->is_lock_owned((address)mark->locker())) {
//如果重入
temp = mark->displaced_mark_helper(); // this is a lightweight monitor owned
assert (temp->is_neutral(), "invariant") ;
hash = temp->hash(); // by current thread, check if the displaced
if (hash) { // header contains hash code
return hash;
}
// WARNING:
// The displaced header is strictly immutable.
// It can NOT be changed in ANY cases. So we have
// to inflate the header into heavyweight monitor
// even the current thread owns the lock. The reason
// is the BasicLock (stack slot) will be asynchronously
// read by other threads during the inflate() function.
// Any change to stack may not propagate to other threads
// correctly.
}
// Inflate the monitor to set hash code
monitor = ObjectSynchronizer::inflate(Self, obj);
// Load displaced header and check it has hash code
mark = monitor->header();
assert (mark->is_neutral(), "invariant") ;
hash = mark->hash();
if (hash == 0) {
hash = get_next_hash(Self, obj);
temp = mark->copy_set_hash(hash); // merge hash code into header
assert (temp->is_neutral(), "invariant") ;
test = (markOop) Atomic::cmpxchg_ptr(temp, monitor, mark);
if (test != mark) {
// The only update to the header in the monitor (outside GC)
// is install the hash code. If someone add new usage of
// displaced header, please update this code
hash = test->hash();
assert (test->is_neutral(), "invariant") ;
assert (hash != 0, "Trivial unexpected object/monitor header usage.");
}
}
// We finally get the hash
return hash;
// hash operations
intptr_t hash() const {
// value() 是地址
// age_bits = 4,
// cms_shift = age_shift + age_bits,
// hash_shift = cms_shift + cms_bits,
// if 64 位
// hash_mask = right_n_bits(hash_bits);
return mask_bits(value() >> hash_shift, hash_mask);
}
看不懂先不必去深究，根据源码我们就能发现，hashCode() 返回的并不是地址那么简单，而是经过了一系列的计算得到的，有两个概念我们需要了解：两个不同的对象 hashCode 值可能会相等，hashCode 值不相等的两个对象肯定不是同一对象。
简单分析最后两行关键代码，在 C++ 中两个不同的对象的地址肯定是不同的，但是 value() >> 16 就有可能相等，源码原理就这么简单。接下来我们回到我们的重点去分析 HashMap 的源码（JDK 1.7）
// 确保数组 tab 的长度是 2 的幂次，上次已讲，不再解释
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;
}
public V put(K key, V value) {
// 如果是空的创建一个新的数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 是 null ，单独存放
if (key == null)
return putForNullKey(value);
// 二次 hash 获取 hash 值
int hash = hash(key);
// 获取应当存放的 tab 位置
int i = indexFor(hash, table.length);
// 遍历 i 上面的链表看有没有存在，如果有覆盖
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// key 不存在添加新的
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 是否需要扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 创建新的节点
createEntry(hash, key, value, bucketIndex);
}
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 扩容需要重新摆放里面的所有元素（最耗时的一个操作）
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 添加在列表最前面
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
// 获取所在的位置，遍历循环返回
for (HashMapEntry<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;
}
了解了思想，源码是非常容易理解的，至于 JDK 1.8 的红黑树知识，我们必须先要了解二叉树；ConcurrentHashMap 分段锁我们都会在后面的文章陆陆续续的做一些分析。
视频链接:https://pan.baidu.com/s/1dYd-4UG0VY1UhezE1p9s9A
视频密码:b8zd
网友评论