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在并发环境下存在的安全问题

• HashMap在并发下可能出现的问题分析

常见hash算法原理

hash冲突解决办法

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

References

• 【java集合】HashMap常见面试题

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	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中实现有什么区别

• jdk7中ConcurrentHashMap源码

HashMap&HashTable&Concurrent对比分析

ConcurrentHashMap

• JAVA面试题05-ConcurrentHashMap的实现

扩展

关于红黑树算法的原理

如何防止恶意碰撞（hash）