作为一位小菜 ”一面面试官“,面试过程中,我肯定会问 Java 集合的内容,同时作为求职者,也肯定会被问到集合,所以整理下 Java 集合面试题
说说常见的集合有哪些吧?
HashMap说一下,其中的Key需要重写hashCode()和equals()吗?
HashMap中key和value可以为null吗?允许几个为null呀?
HashMap线程安全吗?ConcurrentHashMap和hashTable有什么区别?
List和Set说一下,现在有一个ArrayList,对其中的所有元素按照某一属性大小排序,应该怎么做?
ArrayList 和 Vector 的区别
list 可以删除吗,遍历的时候可以删除吗,为什么
面向对象语言对事物的体现都是以对象的形式,所以为了方便对多个对象的操作,需要将对象进行存储,集合就是存储对象最常用的一种方式,也叫容器。
从上面的集合框架图可以看到,Java 集合框架主要包括两种类型的容器
- 一种是集合(Collection),存储一个元素集合
- 另一种是图(Map),存储键/值对映射。
Collection 接口又有 3 种子类型,List、Set 和 Queue,再下面是一些抽象类,最后是具体实现类,常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。
集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容:
- 接口:是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口,是为了以不同的方式操作集合对象
- 实现(类):是集合接口的具体实现。从本质上讲,它们是可重复使用的数据结构,例如:ArrayList、LinkedList、HashSet、HashMap。
- 算法:是实现集合接口的对象里的方法执行的一些有用的计算,例如:搜索和排序。这些算法被称为多态,那是因为相同的方法可以在相似的接口上有着不同的实现。
说说常用的集合有哪些吧?
Map 接口和 Collection 接口是所有集合框架的父接口:
- Collection接口的子接口包括:Set、List、Queue
- List是有序的允许有重复元素的 Collection,实现类主要有:ArrayList、LinkedList、Stack以及Vector等
- Set是一种不包含重复元素且无序的Collection,实现类主要有:HashSet、TreeSet、LinkedHashSet等
- Map没有继承Collection接口,Map提供key到value的映射。实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap 以及 Properties 等
ArrayList 和 Vector 的区别
相同点:
-
ArrayList 和 Vector 都是继承了相同的父类和实现了相同的接口(都实现了List,有序、允许重复和null)
extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
- 底层都是数组(Object[])实现的
- 初始默认长度都为10
不同点:
- 同步性:Vector 中的 public 方法多数添加了 synchronized 关键字、以确保方法同步、也即是 Vector 线程安全、ArrayList 线程不安全
- 性能:Vector 存在 synchronized 的锁等待情况、需要等待释放锁这个过程、所以性能相对较差
-
扩容大小:ArrayList在底层数组不够用时在原来的基础上扩展 0.5 倍,Vector默认是扩展 1 倍
扩容机制,扩容方法其实就是新创建一个数组,然后将旧数组的元素都复制到新数组里面。其底层的扩容方法都在 grow() 中(基于JDK8)
-
ArrayList 的 grow(),在满足扩容条件时、ArrayList以1.5 倍的方式在扩容(oldCapacity >> 1 ,右移运算,相当于除以 2,结果为二分之一的 oldCapacity)
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //newCapacity = oldCapacity + O.5*oldCapacity,此处扩容0.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
-
Vector 的 grow(),Vector 比 ArrayList多一个属性,扩展因子capacityIncrement,可以扩容大小。当扩容容量增量大于0时、新数组长度为原数组长度+扩容容量增量、否则新数组长度为原数组长度的2倍
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
-
ArrayList 与 LinkedList 区别
- 是否保证线程安全: ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;
- 底层数据结构: Arraylist 底层使用的是 Object 数组;LinkedList 底层使用的是双向循环链表数据结构;
-
插入和删除是否受元素位置的影响:
-
ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行
add(E e)
方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(intindex,E element)
)时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 - LinkedList 采用链表存储,所以插入,删除元素时间复杂度不受元素位置的影响,都是近似 $O(1)$,而数组为近似 $O(n)$。
- ArrayList 一般应用于查询较多但插入以及删除较少情况,如果插入以及删除较多则建议使用 LinkedList
-
ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行
-
是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 实现了 RandomAccess 接口,所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于
get(intindex)
方法)。 - 内存空间占用: ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。
高级工程师的我,可不得看看源码,具体分析下:
- ArrayList工作原理其实很简单,底层是动态数组,每次创建一个 ArrayList 实例时会分配一个初始容量(没有指定初始容量的话,默认是 10),以add方法为例,如果没有指定初始容量,当执行add方法,先判断当前数组是否为空,如果为空则给保存对象的数组分配一个最小容量,默认为10。当添加大容量元素时,会先增加数组的大小,以提高添加的效率;
- LinkedList 是有序并且支持元素重复的集合,底层是基于双向链表的,即每个节点既包含指向其后继的引用也包括指向其前驱的引用。链表无容量限制,但双向链表本身使用了更多空间,也需要额外的链表指针操作。按下标访问元素
get(i)/set(i,e)
要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半,会从末尾移起)。插入、删除元素时修改前后节点的指针即可,但还是要遍历部分链表的指针才能移动到下标所指的位置,只有在链表两头的操作add()
,addFirst()
,removeLast()
或用iterator()
上的remove()
能省掉指针的移动。此外 LinkedList 还实现了 Deque(继承自Queue接口)接口,可以当做队列使用。
不会囊括所有方法,只是为了学习,记录思想。
ArrayList 和 LinkedList 两者都实现了 List 接口
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable{
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
构造器
ArrayList 提供了 3 个构造器,①无参构造器 ②带初始容量构造器 ③参数为集合构造器
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable{
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 创建初始容量的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
public ArrayList() {
// 默认为空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection extends E> c) { //...}
}
LinkedList 提供了 2 个构造器,因为基于链表,所以也就没有初始化大小,也没有扩容的机制,就是一直在前面或者后面插插插~~
public LinkedList() {
}
public LinkedList(Collection extends E> c) {
this();
addAll(c);
}
// LinkedList 既然作为链表,那么肯定会有节点
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
插入
ArrayList:
public boolean add(E e) {
// 确保数组的容量,保证可以添加该元素
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将该元素放入数组中
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 如果数组是空的,那么会初始化该数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// DEFAULT_CAPACITY 为 10,所以调用无参默认 ArrayList 构造方法初始化的话,默认的数组容量为 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 确保数组的容量,如果不够的话,调用 grow 方法扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容具体的方法
private void grow(int minCapacity) {
// 当前数组的容量
int oldCapacity = elementData.length;
// 新数组扩容为原来容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新数组扩容容量还是比最少需要的容量还要小的话,就设置扩充容量为最小需要的容量
if (newCapacity - minCapacity 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 复制元素到新的数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
当然也可以插入指定位置,还有一个重载的方法 add(int index, E element)
public void add(int index, E element) {
// 判断 index 有没有超出索引的范围
rangeCheckForAdd(index);
// 和之前的操作是一样的,都是保证数组的容量足够
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将指定位置及其后面数据向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将该元素添加到指定的数组位置
elementData[index] = element;
// ArrayList 的大小改变
size++;
}
可以看到每次插入指定位置都要移动元素,效率较低。
再来看 LinkedList 的插入,也有插入末尾,插入指定位置两种,由于基于链表,肯定得先有个 Node
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
public boolean add(E e) {
// 直接往队尾加元素
linkLast(e);
return true;
}
void linkLast(E e) {
// 保存原来链表尾部节点,last 是全局变量,用来表示队尾元素
final Node l = last;
// 为该元素 e 新建一个节点
final Node newNode = new Node(l, e, null);
// 将新节点设为队尾
last = newNode;
// 如果原来的队尾元素为空,那么说明原来的整个列表是空的,就把新节点赋值给头结点
if (l == null)
first = newNode;
else
// 原来尾结点的后面为新生成的结点
l.next = newNode;
// 节点数 +1
size++;
modCount++;
}
public void add(int index, E element) {
// 检查 index 有没有超出索引范围
checkPositionIndex(index);
// 如果追加到尾部,那么就跟 add(E e) 一样了
if (index == size)
linkLast(element);
else
// 否则就是插在其他位置
linkBefore(element, node(index));
}
//linkBefore方法中调用了这个node方法,类似二分查找的优化
Node node(int index) {
// assert isElementIndex(index);
// 如果 index 在前半段,从前往后遍历获取 node
if (index > 1)) {
Node x = first;
for (int i = 0; i x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
void linkBefore(E e, Node succ) {
// assert succ != null;
// 保存 index 节点的前节点
final Node pred = succ.prev;
// 新建一个目标节点
final Node newNode = new Node(pred, e, succ);
succ.prev = newNode;
// 如果是在开头处插入的话
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
获取
ArrayList 的 get() 方法很简单,就是在数组中返回指定位置的元素即可,所以效率很高
public E get(int index) {
// 检查 index 有没有超出索引的范围
rangeCheck(index);
// 返回指定位置的元素
return elementData(index);
}
LinkedList 的 get() 方法,就是在内部调用了上边看到的 node() 方法,判断在前半段还是在后半段,然后遍历得到即可。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
HashMap的底层实现
什么时候会使用HashMap?他有什么特点?
你知道HashMap的工作原理吗?
你知道get和put的原理吗?equals()和hashCode()的都有什么作用?
你知道hash的实现吗?为什么要这样实现?
如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?
HashMap 在 JDK 7 和 JDK8 中的实现方式略有不同。分开记录。
深入 HahsMap 之前,先要了解的概念
-
initialCapacity:初始容量。指的是 HashMap 集合初始化的时候自身的容量。可以在构造方法中指定;如果不指定的话,总容量默认值是 16 。需要注意的是初始容量必须是 2 的幂次方。(1.7中,已知HashMap中将要存放的KV个数的时候,设置一个合理的初始化容量可以有效的提高性能)
static final int DEFAULT_INITIAL_CAPACITY = 1
- size:当前 HashMap 中已经存储着的键值对数量,即
HashMap.size()
。 - loadFactor:加载因子。所谓的加载因子就是 HashMap (当前的容量/总容量) 到达一定值的时候,HashMap 会实施扩容。加载因子也可以通过构造方法中指定,默认的值是 0.75 。举个例子,假设有一个 HashMap 的初始容量为 16 ,那么扩容的阀值就是 0.75 * 16 = 12 。也就是说,在你打算存入第 13 个值的时候,HashMap 会先执行扩容。
- threshold:扩容阀值。即 扩容阀值 = HashMap 总容量 * 加载因子。当前 HashMap 的容量大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为当前 HashMap 总容量的两倍。比如,当前 HashMap 的总容量为 16 ,那么扩容之后为 32 。
- table:Entry 数组。我们都知道 HashMap 内部存储 key/value 是通过 Entry 这个介质来实现的。而 table 就是 Entry 数组。
JDK1.7 实现
JDK1.7 中 HashMap 由 数组+链表 组成(“链表散列” 即数组和链表的结合体),数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(HashMap 采用 “拉链法也就是链地址法” 解决冲突),如果定位到的数组位置不含链表(当前 entry 的 next 指向 null ),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度依然为 O(1),因为最新的 Entry 会插入链表头部,即需要简单改变引用链即可,而对于查找操作来讲,此时就需要遍历链表,然后通过 key 对象的 equals 方法逐一比对查找。
所谓 “拉链法” 就是将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。
源码解析
构造方法
《阿里巴巴 Java 开发手册》推荐集合初始化时,指定集合初始值大小。(说明:HashMap 使用HashMap(int initialCapacity) 初始化)建议原因: https://www.zhihu.com/question/314006228/answer/611170521
// 默认的构造方法使用的都是默认的初始容量和加载因子
// DEFAULT_INITIAL_CAPACITY = 16,DEFAULT_LOAD_FACTOR = 0.75f
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 可以指定初始容量,并且使用默认的加载因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
// 对初始容量的值判断
if (initialCapacity MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
HashMap 的前 3 个构造方法最后都会去调用 HashMap(int initialCapacity, float loadFactor)
。在其内部去设置初始容量和加载因子。而最后的 init()
是空方法,主要给子类实现,比如LinkedHashMap。
put() 方法
public V put(K key, V value) {
// 如果 table 数组为空时先创建数组,并且设置扩容阀值
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 为空时,调用 putForNullKey 方法特殊处理
if (key == null)
return putForNullKey(value);
// 计算 key 的哈希值
int hash = hash(key);
// 根据计算出来的哈希值和当前数组的长度计算在数组中的索引
int i = indexFor(hash, table.length);
// 先遍历该数组索引下的整条链表
// 如果该 key 之前已经在 HashMap 中存储了的话,直接替换对应的 value 值即可
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
//先判断hash值是否一样,如果一样,再判断key是否一样,不同对象的hash值可能一样
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果该 key 之前没有被存储过,那么就进入 addEntry 方法
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);
}
//扩容,创建了一个新的数组,然后把数据全部复制过去,再把新数组的引用赋给 table
void resize(int newCapacity) {
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
return;
}
// 创建新的 entry 数组
Entry[] newTable = new Entry[newCapacity];
// 将旧 entry 数组中的数据复制到新 entry 数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将新数组的引用赋给 table
table = newTable;
// 计算新的扩容阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 取出table中下标为bucketIndex的Entry
Entry e = table[bucketIndex];
// 利用key、value来构建新的Entry
// 并且之前存放在table[bucketIndex]处的Entry作为新Entry的next
// 把新创建的Entry放到table[bucketIndex]位置
table[bucketIndex] = new Entry(hash, key, value, e);
// 当前 HashMap 的容量加 1
size++;
}
最后的 createEntry()
方法就说明了当 hash 冲突时,采用的拉链法来解决 hash 冲突的,并且是把新元素插入到单链表的表头。
get() 方法
public V get(Object key) {
// 如果 key 是空的,就调用 getForNullKey 方法特殊处理
if (key == null)
return getForNullKey();
// 获取 key 相对应的 entry
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//找到对应 key 的数组索引,然后遍历链表查找即可
final Entry getEntry(Object key) {
if (size == 0) {
return null;
}
// 计算 key 的哈希值
int hash = (key == null) ? 0 : hash(key);
// 得到数组的索引,然后遍历链表,查看是否有相同 key 的 Entry
for (Entry 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;
}
// 没有的话,返回 null
return null;
}
JDK1.8 实现
JDK 1.7 中,如果哈希碰撞过多,拉链过长,极端情况下,所有值都落入了同一个桶内,这就退化成了一个链表。通过 key 值查找要遍历链表,效率较低。 JDK1.8 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。
TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。
源码解析
构造方法
JDK8 构造方法改动不是很大
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
确定哈希桶数组索引位置(hash 函数的实现)
//方法一:
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//方法二:
static int indexFor(int h, int length) { //jdk1.7的源码,jdk1.8没有提取这个方法,而是放在了其他方法中,比如 put 的p = tab[i = (n - 1) & hash]
return h & (length-1); //第三步 取模运算
}
HashMap 定位数组索引位置,直接决定了 hash 方法的离散性能。Hash 算法本质上就是三步:取key的hashCode值、高位运算、取模运算。
为什么要这样呢?
HashMap 的长度为什么是 2 的幂次方?
目的当然是为了减少哈希碰撞,使 table 里的数据分布的更均匀。
-
HashMap 中桶数组的大小 length 总是2的幂,此时,
h & (table.length -1)
等价于对 length 取模h%length
。但取模的计算效率没有位运算高,所以这是是一个优化。假设h = 185
,table.length-1 = 15(0x1111)
,其实散列真正生效的只是低 4bit 的有效位,所以很容易碰撞。 -
图中的 hash 是由键的 hashCode 产生。计算余数时,由于 n 比较小,hash 只有低4位参与了计算,高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关,高位数据没发挥作用。为了处理这个缺陷,我们可以上图中的 hash 高4位数据与低4位数据进行异或运算,即
hash ^ (hash >>> 4)
。通过这种方式,让高位数据与低位数据进行异或,以此加大低位信息的随机性,变相的让高位数据参与到计算中。此时的计算过程如下:在 Java 中,hashCode 方法产生的 hash 是 int 类型,32 位宽。前16位为高位,后16位为低位,所以要右移16位,即
hash ^ (hash >>> 16)
。这样还增加了hash 的复杂度,进而影响 hash 的分布性。
HashMap 的长度为什么是2的幂次方?
为了能让HashMap存取高效,尽量减少碰撞,也就是要尽量把数据分配均匀,Hash值的范围是-2147483648到2147483647,前后加起来有40亿的映射空间,只要哈希函数映射的比较均匀松散,一般应用是很难出现碰撞的,但一个问题是40亿的数组内存是放不下的。所以这个散列值是不能直接拿来用的。用之前需要先对数组长度取模运算,得到余数才能用来存放位置也就是对应的数组小标。这个数组下标的计算方法是 (n-1)&hash
,n代表数组长度。
这个算法应该如何设计呢?
我们首先可能会想到采用%取余的操作来实现。但是,重点来了。
取余操作中如果除数是2的幂次则等价于其除数减一的与操作,也就是说 hash%length=hash&(length-1)
,但前提是 length 是 2 的 n 次方,并且采用 &运算比 %运算效率高,这也就解释了 HashMap 的长度为什么是2的幂次方。
get() 方法
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
//定位键值对所在桶的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未命中
if ((e = first.next) != null) {
// 如果 first 是 TreeNode 类型,则调用黑红树查找方法
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
// 在链表中查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
put() 方法
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算index,并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// 节点key存在,直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判断该链为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
//该链为链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key已经存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
HashMap 的 put 方法的具体流程?
①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;
②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;
③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;
④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;
⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。
resize() 扩容
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了,就只好随你碰撞了
if (oldCap >= MAXIMUM_CAPACITY) {
//修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值,就扩充为原来的2倍
else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)
newThr = oldThr 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap [] newTab = (Node[])new Node[newCap];
table = newTab;
// 把每个bucket都移动到新的buckets中
if (oldTab != null) {
// 循环遍历旧的 table 数组
for (int j = 0; j e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果该桶只有一个元素,那么直接复制
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是红黑树,那么对红黑树进行拆分
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
// 遍历链表,将原链表节点分成lo和hi两个链表
// 其中 lo 表示在原来的桶位置,hi 表示在新的桶位置
else { // preserve order 链表优化重hash的代码块
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
// 原索引
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap的扩容操作是怎么实现的?
- 在jdk1.8中,resize方法是在HashMap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容;
- 每次扩展的时候,都是扩展2倍;
- 扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。
在 putVal()
中,我们看到在这个函数里面使用到了2次 resize()
方法,resize()
方法表示在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其扩容阈值(第一次为0.75 * 16 = 12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8 版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上
链表树化
当桶中链表长度超过 TREEIFY_THRESHOLD(默认为8)时,就会调用 treeifyBin 方法进行树化操作。但此时并不一定会树化,因为在 treeifyBin 方法中还会判断 HashMap 的容量是否大于等于 64。如果容量大于等于 64,那么进行树化,否则优先进行扩容。
为什么树化还要判断整体容量是否大于 64 呢?
当桶数组容量比较小时,键值对节点 hash 的碰撞率可能会比较高,进而导致链表长度较长,从而导致查询效率低下。这时候我们有两种选择,一种是扩容,让哈希碰撞率低一些。另一种是树化,提高查询效率。
如果我们采用扩容,那么我们需要做的就是做一次链表数据的复制。而如果我们采用树化,那么我们需要将链表转化成红黑树。到这里,貌似没有什么太大的区别,但我们让场景继续延伸下去。当插入的数据越来越多,我们会发现需要转化成树的链表越来越多。
到了一定容量,我们就需要进行扩容了。这个时候我们有许多树化的红黑树,在扩容之时,我们需要将许多的红黑树拆分成链表,这是一个挺大的成本。而如果我们在容量小的时候就进行扩容,那么需要树化的链表就越少,我们扩容的成本也就越低。
接下来我们看看链表树化是怎么做的:
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
// 1. 容量小于 MIN_TREEIFY_CAPACITY,优先扩容
if (tab == null || (n = tab.length) hd = null, tl = null;
// 2.1 先将链表转成 TreeNode 表示的双向链表
do {
TreeNode p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 2.2 将 TreeNode 表示的双向链表树化
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
我们可以看到链表树化的整体思路也比较清晰。首先将链表转成 TreeNode 表示的双向链表,之后再调用 treeify()
方法进行树化操作。那么我们继续看看 treeify()
方法的实现。
final void treeify(Node[] tab) {
TreeNode root = null;
// 1. 遍历双向 TreeNode 链表,将 TreeNode 节点一个个插入
for (TreeNode x = this, next; x != null; x = next) {
next = (TreeNode)x.next;
x.left = x.right = null;
// 2. 如果 root 节点为空,那么直接将 x 节点设置为根节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class> kc = null;
// 3. 如果 root 节点不为空,那么进行比较并在合适的地方插入
for (TreeNode p = root;;) {
int dir, ph;
K pk = p.key;
// 4. 计算 dir 值,-1 表示要从左子树查找插入点,1表示从右子树
if ((ph = p.hash) > h)
dir = -1;
else if (ph xp = p;
// 5. 如果查找到一个 p 点,这个点是叶子节点
// 那么这个就是插入位置
if ((p = (dir
从上面代码可以看到,treeify() 方法其实就是将双向 TreeNode 链表进一步树化成红黑树。其中大致的步骤为:
- 遍历 TreeNode 双向链表,将 TreeNode 节点一个个插入
- 如果 root 节点为空,那么表示红黑树现在为空,直接将该节点作为根节点。否则需要查找到合适的位置去插入 TreeNode 节点。
- 通过比较与 root 节点的位置,不断寻找最合适的点。如果最终该节点的叶子节点为空,那么该节点 p 就是插入节点的父节点。接着,将 x 节点的 parent 引用指向 xp 节点,xp 节点的左子节点或右子节点指向 x 节点。
- 接着,调用 balanceInsertion 做一次动态平衡。
- 最后,调用 moveRootToFront 方法将 root 节点移动到链表头。
关于 balanceInsertion() 动平衡可以参考红黑树的插入动平衡,这里暂不深入讲解。最后我们继续看看 moveRootToFront 方法。
static void moveRootToFront(Node[] tab, TreeNode root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode first = (TreeNode)tab[index];
// 如果插入红黑树的 root 节点不是链表的第一个元素
// 那么将 root 节点取出来,插在 first 节点前面
if (root != first) {
Node rn;
tab[index] = root;
TreeNode rp = root.prev;
// 下面的两个 if 语句,做的事情是将 root 节点取出来
// 让 root 节点的前继指向其后继节点
// 让 root 节点的后继指向其前继节点
if ((rn = root.next) != null)
((TreeNode)rn).prev = rp;
if (rp != null)
rp.next = rn;
// 这里直接让 root 节点插入到 first 节点前方
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
红黑树拆分
扩容后,普通节点需要重新映射,红黑树节点也不例外。按照一般的思路,我们可以先把红黑树转成链表,之后再重新映射链表即可。但因为红黑树插入的时候,TreeNode 保存了元素插入的顺序,所以直接可以按照插入顺序还原成链表。这样就避免了将红黑树转成链表后再进行哈希映射,无形中提高了效率。
final void split(HashMap map, Node[] tab, int index, int bit) {
TreeNode b = this;
// Relink into lo and hi lists, preserving order
TreeNode loHead = null, loTail = null;
TreeNode hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 1. 将红黑树当成是一个 TreeNode 组成的双向链表
// 按照链表扩容一样,分别放入 loHead 和 hiHead 开头的链表中
for (TreeNode e = b, next; e != null; e = next) {
next = (TreeNode)e.next;
e.next = null;
// 1.1. 扩容后的位置不变,还是原来的位置,该节点放入 loHead 链表
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
// 1.2 扩容后的位置改变了,放入 hiHead 链表
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 2. 对 loHead 和 hiHead 进行树化或链表化
if (loHead != null) {
// 2.1 如果链表长度小于阈值,那就链表化,否则树化
if (lc
从上面的代码我们知道红黑树的扩容也和链表的转移是一样的,不同的是其转化成 hiHead 和 loHead 之后,会根据链表长度选择拆分成链表还是继承维持红黑树的结构。
红黑树链化
我们在说到红黑树拆分的时候说到,红黑树结构在扩容的时候如果长度低于阈值,那么就会将其转化成链表。其实现代码如下:
final Node untreeify(HashMap map) {
Node hd = null, tl = null;
for (Node q = this; q != null; q = q.next) {
Node p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
因为红黑树中包含了插入元素的顺序,所以当我们将红黑树拆分成两个链表 hiHead 和 loHead 时,其还是保持着原来的顺序的。所以此时我们只需要循环遍历一遍,然后将 TreeNode 节点换成 Node 节点即可。
HashMap 为什么线程不安全
- put的时候导致的多线程数据不一致。
这个问题比较好想象,比如有两个线程A和B,首先A希望插入一个key-value对到HashMap中,首先计算记录所要落到的桶的索引坐标,然后获取到该桶里面的链表头结点,此时线程A的时间片用完了,而此时线程B被调度得以执行,和线程A一样执行,只不过线程B成功将记录插到了桶里面,假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的,那么当线程B成功插入之后,线程A再次被调度运行时,它依然持有过期的链表头但是它对此一无所知,以至于它认为它应该这样做,如此一来就覆盖了线程B插入的记录,这样线程B插入的记录就凭空消失了,造成了数据不一致的行为。 -
另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环(cpu100%),具体分析如下:
下面的代码是resize的核心内容:
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {
while(null != e) {
Entry next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
这个方法的功能是将原来的记录重新计算在新桶的位置,然后迁移过去。
多线程HashMap的resize
我们假设有两个线程同时需要执行resize操作,我们原来的桶数量为2,记录数为3,需要resize桶到4,原来的记录分别为:[3,A],[7,B],[5,C],在原来的map里面,我们发现这三个entry都落到了第二个桶里面。
假设线程thread1执行到了transfer方法的Entry next = e.next这一句,然后时间片用完了,此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作,需要注意的是,此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行,此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上,然后再处理[7,B],而[7,B]被链接到了[3,A]的后面,处理完[7,B]之后,就需要处理[7,B]的next了啊,而通过thread2的resize之后,[7,B]的next变为了[3,A],此时,[3,A]和[7,B]形成了环形链表,在get的时候,如果get的key的桶索引和[3,A]和[7,B]一样,那么就会陷入死循环。
如果在取链表的时候从头开始取(现在是从尾部开始取)的话,则可以保证节点之间的顺序,那样就不存在这样的问题了。
HashMap:JDK1.7 VS JDK1.8
JDK1.8主要解决或优化了一下问题:
- resize 扩容优化
- 引入了红黑树,目的是避免单条链表过长而影响查询效率
- 解决了多线程死循环问题,但仍是非线程安全的,多线程时可能会造成数据丢失问题
不同 | JDK 1.7 | JDK 1.8 |
---|---|---|
存储结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
初始化方式 | 单独函数:inflateTable() | 直接集成到了扩容函数resize()中 |
hash值计算方式 | 扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算 | 扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算 |
存放数据的规则 | 无冲突时,存放数组;冲突时,存放链表 | 无冲突时,存放数组;冲突 & 链表长度 8:树化并存放红黑树 |
插入数据方式 | 头插法(先将原位置的数据移到后1位,再插入数据到该位置) | 尾插法(直接插入到链表尾部/红黑树) |
扩容后存储位置的计算方式 | 全部按照原来方法进行计算(即hashCode ->> 扰动函数 ->> (h&length-1)) | 按照扩容后的规律计算(即扩容后的位置=原位置 or 原位置 + 旧容量 |
Hashtable
Hashtable 和 HashMap 都是散列表,也是用”拉链法“实现的哈希表。保存数据和 JDK7 中的 HashMap 一样,是 Entity 对象,只是 Hashtable 中的几乎所有的 public 方法都是 synchronized 的,而有些方法也是在内部通过 synchronized 代码块来实现,效率肯定会降低。且 put() 方法不允许空值。
HashMap 和 Hashtable 的区别
-
线程是否安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过
synchronized
修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!); - 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它;
- 对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛出 NullPointerException。
-
初始容量大小和每次扩充容量大小的不同 :
① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。
② 创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂次方作为哈希表的大小,后面会介绍到为什么是2的幂次方。
- 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。
- HashMap的迭代器(
Iterator
)是fail-fast迭代器,但是 Hashtable的迭代器(enumerator
)不是 fail-fast的。如果有其它线程对HashMap进行的添加/删除元素,将会抛出ConcurrentModificationException
,但迭代器本身的remove
方法移除元素则不会抛出异常。这条同样也是 Enumeration 和 Iterator 的区别。
了解过 LinkedHashMap、TreeMap 吗
LinkedHashMap属于HashMap的子类,与HashMap的区别在于LinkedHashMap保存了记录插入的顺序。TreeMap实现了SortedMap接口,TreeMap 有能力对插入的记录根据 key 排序,默认按照升序排序,也可以自定义比较项,在使用 TreeMap 的时候,key 应当实现 Comparable。
ConcurrentHashMap
HashMap 在多线程情况下,在 put 的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是 resize,这个会重新将原数组的内容重新 hash 到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行 put 操作,如果 hash 值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在 get 时会出现死循环,所以 HashMap 是线程不安全的。(可参考:https://www.jianshu.com/p/e2f75c8cce01)
Hashtable,是线程安全的,它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table,这就意味着所有的线程都在竞争一把锁,在多线程的环境下,它是安全的,但是无疑是效率低下的。
JDK1.7 实现
Hashtable 容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有访问 Hashtable 的线程都必须竞争同一把锁,那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,这就是 ConcurrentHashMap 所使用的锁分段技术。
在 JDK1.7 版本中,ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成。Segment 数组的意义就是将一个大的 table 分割成多个小的 table 来进行加锁。每一个 Segment 元素存储的是 HashEntry数组+链表,这个和 HashMap 的数据存储结构一样。
ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。
HashEntry 用来封装映射表的键值对,Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。每个 Segment 守护着一个 HashEntry 数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得它对应的 Segment 锁。
Segment 类
Segment 类继承于 ReentrantLock 类,从而使得 Segment 对象能充当可重入锁的角色。一个 Segment 就是一个子哈希表,Segment 里维护了一个 HashEntry 数组,并发环境下,对于不同 Segment 的数据进行操作是不用考虑锁竞争的。
从源码可以看到,Segment 内部类和我们上边看到的 HashMap 很相似。也有负载因子,阈值等各种属性。
static final class Segment extends ReentrantLock implements Serializable {
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
transient volatile HashEntry[] table;
transient int count;
transient int modCount; //记录修改次数
transient int threshold;
final float loadFactor;
Segment(float lf, int threshold, HashEntry[] tab) {
this.loadFactor = lf;
this.threshold = threshold;
this.table = tab;
}
//put 方法会有加锁操作,
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
// ...
}
@SuppressWarnings("unchecked")
private void rehash(HashEntry node) {
// ...
}
private HashEntry scanAndLockForPut(K key, int hash, V value) {
//...
}
private void scanAndLock(Object key, int hash) {
//...
}
final V remove(Object key, int hash, Object value) {
//...
}
final boolean replace(K key, int hash, V oldValue, V newValue) {
//...
}
final V replace(K key, int hash, V value) {
//...
}
final void clear() {
//...
}
}
HashEntry 类
HashEntry 是目前最小的逻辑处理单元。一个 ConcurrentHashMap 维护一个 Segment 数组,一个 Segment 维护一个 HashEntry 数组。
static final class HashEntry {
final int hash;
final K key;
volatile V value; // value 为 volatie 类型,保证可见
volatile HashEntry next;
//...
}
ConcurrentHashMap 类
默认的情况下,每个 ConcurrentHashMap 类会创建16个并发的 segment,每个 segment 里面包含多个 Hash表,每个 Hash 链都是由 HashEntry 节点组成的。
public class ConcurrentHashMap extends AbstractMap
implements ConcurrentMap, Serializable {
//默认初始容量为 16,即初始默认为 16 个桶
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认并发级别为 16。该值表示当前更新线程的估计数
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
static final int MAXIMUM_CAPACITY = 1 [] segments; //主干就是这个分段锁数组
//构造器
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// 2的sshif次方等于ssize,例:ssize=16,sshift=4;ssize=32,sshif=5
int sshift = 0;
// ssize 为segments数组长度,根据concurrentLevel计算得出
int ssize = 1;
while (ssize MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize s0 =
new Segment(loadFactor, (int)(cap * loadFactor),
(HashEntry[])new HashEntry[cap]);
Segment[] ss = (Segment[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
}
put() 方法
- 定位segment并确保定位的Segment已初始化
- 调用 Segment的 put 方法。
public V put(K key, V value) {
Segment s;
//concurrentHashMap不允许key/value为空
if (value == null)
throw new NullPointerException();
//hash函数对key的hashCode重新散列,避免差劲的不合理的hashcode,保证散列均匀
int hash = hash(key);
//返回的hash值无符号右移segmentShift位与段掩码进行位运算,定位segment
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment)UNSAFE.getObject // nonvolatile; recheck
(segments, (j
get() 方法
get方法无需加锁,由于其中涉及到的共享变量都使用volatile修饰,volatile可以保证内存可见性,所以不会读取到过期数据
public V get(Object key) {
Segment s; // manually integrate access methods to reduce overhead
HashEntry[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) )UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry e = (HashEntry) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h))
JDK1.8 实现
ConcurrentHashMap 在 JDK8 中进行了巨大改动,光是代码量就从1000多行增加到6000行!1.8 摒弃了Segment
(锁段)的概念,采用了 CAS + synchronized
来保证并发的安全性。
可以看到,和 HashMap 1.8 的数据结构很像。底层数据结构改变为采用数组+链表+红黑树的数据形式。
和HashMap1.8相同的一些地方
- 底层数据结构一致
- HashMap初始化是在第一次put元素的时候进行的,而不是init
- HashMap的底层数组长度总是为2的整次幂
- 默认树化的阈值为 8,而链表化的阈值为 6(当低于这个阈值时,红黑树转成链表)
- hash算法也很类似,但多了一步
& HASH_BITS
,该步是为了消除最高位上的负符号,hash的负在ConcurrentHashMap中有特殊意义表示在扩容或者是树节点
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
一些关键属性
private static final int MAXIMUM_CAPACITY = 1 >> 1)代替了更高效
static final int TREEIFY_THRESHOLD = 8; // 链表转树阀值,大于8时
static final int UNTREEIFY_THRESHOLD = 6; //树转链表阀值,小于等于6(tranfer时,lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量,[] table; //装载Node的数组,作为ConcurrentHashMap的数据容器,采用懒加载的方式,直到第一次插入数据的时候才会进行初始化操作,数组的大小总是为2的幂次方。
private transient volatile Node[] nextTable; //扩容时使用,平时为null,只有在扩容的时候才为非null
/**
* 实际上保存的是hashmap中的元素个数 利用CAS锁进行更新但它并不用返回当前hashmap的元素个数
*/
private transient volatile long baseCount;
/**
*该属性用来控制table数组的大小,根据是否初始化和是否正在扩容有几种情况:
*当值为负数时:如果为-1表示正在初始化,如果为-N则表示当前正有N-1个线程进行扩容操作;
*当值为正数时:如果当前数组为null的话表示table在初始化过程中,sizeCtl表示为需要新建数组的长度;若已经初始化了,表示当前数据容器(table数组)可用容量也可以理解成临界值(插入节点数超过了该临界值就需要扩容),具体指为数组的长度n 乘以 加载因子loadFactor;当值为0时,即数组长度为默认初始值。
*/
private transient volatile int sizeCtl;
put() 方法
- 首先会判断 key、value是否为空,如果为空就抛异常!
-
spread()
方法获取hash,减小hash冲突 - 判断是否初始化table数组,没有的话调用
initTable()
方法进行初始化 - 判断是否能直接将新值插入到table数组中
- 判断当前是否在扩容,
MOVED
为-1说明当前ConcurrentHashMap正在进行扩容操作,正在扩容的话就进行协助扩容 -
当table[i]为链表的头结点,在链表中插入新值,通过synchronized (f)的方式进行加锁以实现线程安全性。
- 在链表中如果找到了与待插入的键值对的key相同的节点,就直接覆盖
- 如果没有找到的话,就直接将待插入的键值对追加到链表的末尾
- 当table[i]为红黑树的根节点,在红黑树中插入新值/覆盖旧值
- 根据当前节点个数进行调整,否需要转换成红黑树(个数大于等于8,就会调用
treeifyBin
方法将tabel[i]第i个散列桶
拉链转换成红黑树) - 对当前容量大小进行检查,如果超过了临界值(实际大小*加载因子)就进行扩容
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key 和 value 均不允许为 null
if (key == null || value == null) throw new NullPointerException();
// 根据 key 计算出 hash 值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node[] tab = table;;) {
Node f; int n, i, fh;
// 判断是否需要进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// f 即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试写入,失败则自旋保证成功
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 如果都不满足,则利用 synchronized 锁写入数据
else {
// 剩下情况又分两种,插入链表、插入红黑树
V oldVal = null;
//采用同步内置锁实现并发控制
synchronized (f) {
if (tabAt(tab, i) == f) {
// 如果 fh=f.hash >=0,当前为链表,在链表中插入新的键值对
if (fh >= 0) {
binCount = 1;
//遍历链表,如果找到对应的 node 节点,修改 value,否则直接在链表尾部加入节点
for (Node e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node pred = e;
if ((e = e.next) == null) {
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
// 当前为红黑树,将新的键值对插入到红黑树中
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 插入完键值对后再根据实际大小看是否需要转换成红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 对当前容量大小进行检查,如果超过了临界值(实际大小*加载因子)就需要扩容
addCount(1L, binCount);
return null;
}
我们可以发现 JDK8 中的实现也是锁分离的思想,只是锁住的是一个Node,而不是JDK7中的Segment,而锁住Node之前的操作是无锁的并且也是线程安全的,建立在之前提到的原子操作上。
get() 方法
get方法无需加锁,由于其中涉及到的共享变量都使用volatile修饰,volatile可以保证内存可见性,所以不会读取到过期数据
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
int h = spread(key.hashCode());
// 判断数组是否为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 判断node 节点第一个元素是不是要找的,如果是直接返回
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// // hash小于0,说明是特殊节点(TreeBin或ForwardingNode)调用find
else if (eh
Hashtable 和 ConcurrentHashMap 的区别
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
- 底层数据结构: JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构和 HashMap1.8 的结构类似,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;
-
实现线程安全的方式(重要) :
- 在 JDK1.7 的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表/红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;
- Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争越激烈效率越低。
Java快速失败(fail-fast)和安全失败(fail-safe)区别
快速失败(fail—fast)
在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出 ConcurrentModificationException
。
原理:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前,都会检测 modCount 变量是否为 expectedmodCount 值,是的话就返回遍历;否则抛出异常,终止遍历。
注意:这里异常的抛出条件是检测到 modCount!=expectedmodCount 这个条件。如果集合发生变化时修改modCount 值刚好又设置为了 expectedmodCount 值,则异常不会抛出。因此,不能依赖于这个异常是否抛出而进行并发操作的编程,这个异常只建议用于检测并发修改的 bug。
场景:java.util
包下的集合类都是快速失败的,不能在多线程下发生并发修改(迭代过程中被修改)。
安全失败(fail—safe)
采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。
原理:由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发 Concurrent Modification Exception
。
缺点:基于拷贝内容的优点是避免了 Concurrent Modification Exception
,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的。
场景:java.util.concurrent
包下的容器都是安全失败,可以在多线程下并发使用,并发修改。
快速失败和安全失败是对迭代器而言的。
快速失败:当在迭代一个集合的时候,如果有另外一个线程在修改这个集合,就会抛出ConcurrentModification
异常,java.util
下都是快速失败。
安全失败:在迭代时候会在集合二层做一个拷贝,所以在修改集合上层元素不会影响下层。在 java.util.concurrent
下都是安全失败
如何避免fail-fast ?
- 在单线程的遍历过程中,如果要进行 remove 操作,可以调用迭代器 ListIterator 的 remove 方法而不是集合类的 remove方法。看看 ArrayList 中迭代器的 remove 方法的源码,该方法不能指定元素删除,只能 remove 当前遍历元素。
public void remove() {
if (lastRet
-
使用并发包(
java.util.concurrent
)中的类来代替 ArrayList 和 hashMap- CopyOnWriterArrayList 代替 ArrayList
- ConcurrentHashMap 代替 HashMap
Iterator 和 Enumeration 区别
在 Java 集合中,我们通常都通过 “Iterator(迭代器)” 或 “Enumeration(枚举类)” 去遍历集合。
public interface Enumeration {
boolean hasMoreElements();
E nextElement();
}
public interface Iterator {
boolean hasNext();
E next();
void remove();
}
- 函数接口不同,Enumeration只有2个函数接口。通过Enumeration,我们只能读取集合的数据,而不能对数据进行修改。Iterator只有3个函数接口。Iterator除了能读取集合的数据之外,也能数据进行删除操作。
-
Iterator支持 fail-fast机制,而Enumeration不支持。Enumeration 是 JDK 1.0 添加的接口。使用到它的函数包括 Vector、Hashtable 等类,这些类都是 JDK 1.0中加入的,Enumeration 存在的目的就是为它们提供遍历接口。Enumeration 本身并没有支持同步,而在 Vector、Hashtable 实现 Enumeration 时,添加了同步。
而 Iterator 是 JDK 1.2 才添加的接口,它也是为了 HashMap、ArrayList 等集合提供遍历接口。Iterator 是支持 fail-fast 机制的:当多个线程对同一个集合的内容进行操作时,就可能会产生 fail-fast 事件
Comparable 和 Comparator 接口有何区别?
Java 中对集合对象或者数组对象排序,有两种实现方式:
-
对象实现Comparable 接口
-
Comparable 在
java.lang
包下,是一个接口,内部只有一个方法compareTo()
public interface Comparable { public int compareTo(T o); }
- Comparable 可以让实现它的类的对象进行比较,具体的比较规则是按照 compareTo 方法中的规则进行。这种顺序称为 自然顺序。
- 实现了 Comparable 接口的 List 或则数组可以使用
Collections.sort()
或者Arrays.sort()
方法进行排序
-
-
定义比较器,实现 Comparator接口
-
Comparator 在
java.util
包下,也是一个接口,JDK 1.8 以前只有两个方法:public interface Comparator { public int compare(T lhs, T rhs); public boolean equals(Object object); }
-
comparable 相当于内部比较器。comparator 相当于外部比较器
区别:
- Comparator 位于
java.util
包下,而 Comparable 位于java.lang
包下 - Comparable 接口的实现是在类的内部(如 String、Integer已经实现了 Comparable 接口,自己就可以完成比较大小操作),Comparator 接口的实现是在类的外部(可以理解为一个是自已完成比较,一个是外部程序实现比较)
-
实现 Comparable 接口要重写 compareTo 方法, 在 compareTo 方法里面实现比较。一个已经实现Comparable 的类的对象或数据,可以通过 Collections.sort(list) 或者 Arrays.sort(arr)实现排序。通过 Collections.sort(list,Collections.reverseOrder()) 对list进行倒序排列。
-
实现Comparator需要重写 compare 方法
HashSet
HashSet 是用来存储没有重复元素的集合类,并且它是无序的。HashSet 内部实现是基于 HashMap ,实现了 Set 接口。
从 HahSet 提供的构造器可以看出,除了最后一个 HashSet 的构造方法外,其他所有内部就是去创建一个 HashMap 。没有其他的操作。而最后一个构造方法不是 public 的,所以不对外公开。
HashSet如何检查重复
HashSet 的底层其实就是 HashMap,只不过我们 HashSet 是实现了 Set 接口并且把数据作为 K 值,而 V 值一直使用一个相同的虚值来保存,HashMap的 K 值本身就不允许重复,并且在 HashMap 中如果 K/V 相同时,会用新的 V 覆盖掉旧的 V,然后返回旧的 V。
Iterater 和 ListIterator 之间有什么区别?
- 我们可以使用 Iterator来遍历 Set 和 List 集合,而 ListIterator 只能遍历List
- ListIterator有add方法,可以向List中添加对象,而Iterator不能
- ListIterator和Iterator都有hasNext()和next()方法,可以实现顺序向后遍历,但是ListIterator有hasPrevious()和previous()方法,可以实现逆向(顺序向前)遍历。Iterator不可以
- ListIterator可以定位当前索引的位置,nextIndex()和previousIndex()可以实现。Iterator没有此功能
- 都可实现删除操作,但是 ListIterator可以实现对象的修改,set()方法可以实现。Iterator仅能遍历,不能修改
参考与感谢
所有内容都是基于源码阅读和各种大佬之前总结的知识整理而来,输入并输出,奥利给。
https://www.javatpoint.com/java-arraylist
https://www.runoob.com/java/java-collections.html
https://www.javazhiyin.com/21717.html
https://yuqirong.me/2018/01/31/LinkedList内部原理解析/
https://youzhixueyuan.com/the-underlying-structure-and-princi…
《HashMap源码详细分析》http://www.tianxiaobo.com/2018/01/18/HashMap-源码详细分析-JDK1-8/
《ConcurrentHashMap1.7源码分析》https://www.cnblogs.com/chengxiao/p/6842045.html
http://www.justdojava.com/2019/12/18/java-collection-15.1/
本文由mdnice多平台发布
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net