性能文章>【译】Java HashMap的内部实现原理>

【译】Java HashMap的内部实现原理转载

2月前
278814
transient HashMapEntry<K,V>[] table

class HashMapEntry<K,V> {
    final K key;
    V value;
    HashMapEntry<K,V> next;
    int hash;
    // Some utility methods
}
 

放置操作

最初,表被初始化为EMPTY_TABLE,如:

final HashMapEntry<?,?>[] EMPTY_TABLE = {};
HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
 
if (table == EMPTY_TABLE) {
    table = new HashMapEntry[capacity];
}
 
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
    if (e.key == null) { // Found the null key
        V oldValue = e.value;
        e.value = value;
        return oldValue;
    }
}
 
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))) {                
       // Means there is already the Node with same key present.
        V oldValue = e.value;
        e.value = value;
        return oldValue;
    }
}
 
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;
        }
    }
}
 

createEntry() 阶段

在这个方法中,条目最终被添加到一个 hashmap 中。
所以新节点计算哈希,索引插入方式如上图类似。
让插入它的索引为 i。
让索引 i 的状态为
table[i] -> Node1 -> Node2
现在将 Node3 插入其中,
插入后 table[i] 将是:
table[i] -> Node 3 -> Node1 -> Node2
所以新节点被插入到索引处所有节点的顶部。

HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
 
HashMapEntry<K,V> e = table[bucketIndex]; // points to Node1
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e); // i.e. Node1 is passed
 
 
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
    value = v;
    key = k;
    hash = h;
    next = n; // new Node i.e. Node3 is created with its next pointing to n which is Node1 passed.
}
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
    int i = indexFor(hash, table.length);
    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;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
 

获取操作:

Get 匹配 hashcode 和 equals 后找到 Node 的值。
如果没有找到这样的节点,则返回 null。
它检查作为输入提供的键是否为空。

 
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
    if (e.key == null)
        return e.value;
}
return null;
for (HashMapEntry<K,V> e = table[index]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e.value;
}
return null;
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}
 
 
点赞收藏
金色梦想

终身学习。

请先登录,查看1条精彩评论吧
快去登录吧,你将获得
  • 浏览更多精彩评论
  • 和开发者讨论交流,共同进步

为你推荐

讲透JAVA Stream的collect用法与原理,远比你想象的更强大

讲透JAVA Stream的collect用法与原理,远比你想象的更强大

没有二十年功力,写不出Thread.sleep(0)这一行“看似无用”的代码!

没有二十年功力,写不出Thread.sleep(0)这一行“看似无用”的代码!

填坑来了!关于“Thread.sleep(0)这一行‘看似无用’的代码”里面留下的坑。

填坑来了!关于“Thread.sleep(0)这一行‘看似无用’的代码”里面留下的坑。

【译】记一次数据库连接泄漏导致的响应迟缓

【译】记一次数据库连接泄漏导致的响应迟缓

【全网首发】微服务10:系统服务熔断、限流

【全网首发】微服务10:系统服务熔断、限流

【全网首发】MQ-消息堆积-JDK Bug导致线程阻塞案例分析

【全网首发】MQ-消息堆积-JDK Bug导致线程阻塞案例分析

4
1