HashMap&HashTable&ConcurrentHashMap (jdk1.8)

HashMap&HashTable&ConcurrentHashMap (jdk1.8)

Java中常用Map数据结构介绍

HashMap

HashMap基本属性及其默认值

HashMap底部数据结构

get()和put()方法

resize()方法

resize()方法主要包括两个核心过程:

  • 在第一次调用put()函数时时对数组进行初始化
  • size > threshold时进行扩容

分别讲一下这两个过程,在第一次初始化的时候,如果指定了初始容量

treeifyBin()方法

tableSizeFor()方法

红黑树TreeNode在HashMap中的实现

HashMap在jdk1.7和jdk1.8中的区别

HashMap在并发环境下存在的安全问题

常见hash算法原理

hash冲突解决办法

开放地址法、链地址法、再哈希法

References

HashTable

基本属性及其默认值

get()和put()方法

rehash()方法

ConcurrentHashMap

get()方法没有加锁,如何能保证线程安全

为什么ConcurrentHashMap的读操作不需要加锁?

get 操作的高效之处在于整个 get 过程不需要加锁,除非读到的值是空的才会加锁重读,我们知道 HashTable 容器的 get 方法是需要加锁的,那么 ConcurrentHashMap 的 get 操作是如何做到不加锁的呢?原因是它的 get 方法里将要使用的共享变量都定义成 volatile,如用于统计当前 Segement 大小的 count 字段和用于存储值的 HashEntry 的 value。定义成 volatile 的变量,能够在线程之间保持可见性,能够被多线程同时读,并且保证不会读到过期的值,但是只能被单线程写(有一种情况可以被多线程写,就是写入的值不依赖于原值),在 get 操作里只需要读不需要写共享变量 count 和 value,所以可以不用加锁。之所以不会读到过期的值,是根据 java 内存模型的 happen before 原则,对 volatile 字段的写入操作先于读操作,即使两个线程同时修改和获取 volatile 变量,get 操作也能拿到最新的值,这是用 volatile 替换锁的经典应用场景。

1
2
3
> transient volatile int count;
> volatile V value;
>

如何保证多线程环境下对数组修改的可见性

1
2
3
4
5
6
7
8
9
10
11
12
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

jdk1.7和jdk1.8中实现有什么区别

HashMap&HashTable&Concurrent对比分析

HashMap HashTable ConcurrentHashMap
默认DEFAULT_CAPACITY 16 11 16
默认loadFactors 0.75f 0.75f 0.75f
安全性 不安全 使用synchronize同步 线程安全,采用分段锁
扩容 newCap = oldCap << 1 int newCapacity = (oldCapacity << 1) + 1; ??
hash算法 int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
int index = (tab.length - 1) & hash
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
int h = key.hashCode()
int hash = (h ^ (h >>> 16)) & HASH_BITS;
int index = (tab.length - 1) & hash;
是否支持NULL key和value都能为null key和value都不能为null key和value都不能为null

ConcurrentHashMap

扩展

关于红黑树算法的原理

如何防止恶意碰撞(hash)

# java

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×