Java容器类

Java提供的容器类如List、Set、Map是语言的基础,熟练掌握是必备技能,本文就Java中容器相关的坑与知识做一个总结整理。本文涉及的代码摘自OpenJDK jdk9-b94,部分逻辑在不同版本的实现有所差异。

List

  • ArrayList:非线程安全,由数组实现,擅长随机访问
  • Vector:同ArrayList,但是添加了线程安全支持
  • LinkedList:非线程安全,由双向链表实现(JDK1.6之前为循环链表),擅长插入、删除操作,不擅长随机访问
  • CopyOnWriteArrayList:通过Immutable方式实现了线程安全,由数组实现,性质类似于ArrayList,但是由于CopyOnWrite的逻辑所以不适合大数据量使用

在内存使用方面,ArrayList会在结尾留有一定空闲余量,而LinkedList则是每个节点的内存使用量都比ArrayList大。LinkedList不是线程安全的,如果需要链表实现的线程安全的数据结构建议使用ConcurrentLinkedQueue、ConcurrentLinkedDeque。

Set

  • HashSet:无序、唯一、允许Null、非线程安全。底层使用HashMap保存数据
  • LinkedHashSet:有序(按插入顺序)、唯一、允许Null、非线程安全。继承自HashSet,内部由LinkedHashMap实现
  • TreeSet:有序(可自定义compare顺序)、唯一、不允许Null,非线程安全。由红黑树实现
  • CopyOnWriteArraySet:内部由CopyOnWriteArrayList实现,性质类似CopyOnWriteArrayList,但是做了Key的判断

Java没有提供Concurrent开头支持线程安全的Set类型,如果需要使用线程安全的Set我们可以通过线程安全的Map实现相关逻辑,如ConcurrentHashMap,通过put值相同的key来实现key的set属性。

当把对象加入HashSet时,HashSet会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的hashcode值作比较,如果没有相符的hashcode,HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象,这时会调用equals()方法来检查hashcode相等的对象是否真的相同。如果两者相同,HashSet就不会让加入操作成功。

Map

  • HashMap:无序、唯一、允许Null、非线程安全。JDK1.8之前由数组+链表组成,1.8之后引入了当链表长度大于阈值(默认8)的时候将链表转为红黑的操作来优化哈希冲突时的搜索效率
  • LinkedHashMap:有序(按插入顺序)、唯一、允许Null、非线程安全。继承自HashMap,在HashMap之外按插入顺序维护了一个双向链表以保证遍历对象的有序性
  • TreeMap:有序(可自定义compare顺序)、唯一、不允许Null,非线程安全。由红黑树实现
  • Hashtable:不允许Null,线程安全。数组+链表实现,为线程安全加了会锁住这个对象的全局锁,性能有较大牺牲,一般不使用
  • ConcurrentHashMap:更高效线程安全的Map实现。底层数据结构于HashMap一致。线程安全方面在JDK1.8之前使用Segment对象将数据根据hash值分段,只锁部分数据性能更好。JDK1.8之后摒弃了Segment锁,使用synchronized和CAS来操作,性能进一步提升

HashMap中怎么计算Key的hash

HashMap通过key的hashCode经过扰动函数处理过后得到hash值,然后通过扰动函数(n - 1) & hash判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的hash值以及key是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。所谓扰动函数指的就是HashMap的hash方法。使用hash方法也就是扰动函数是为了防止一些实现比较差的hashCode()方法以减少碰撞。下面是JDK 1.8以后 HashMap 的 hash 方法:

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

哈希结果的取值范围是int,也就是-2147483648到2147483647,我们显然不能初始化着么长的数组,第一想到的就是对哈希结果除以key数组长度取余数,而取余操作在除数是2的整数次幂的时候正好有 hash%length==hash&(length-1),所以HashMap的长度总是2的整数次幂以确保hash函数的高性能。

如何选用集合

主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用Map接口下的集合,需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap.当我们只需要存放元素值时,就选择实现Collection接口的集合,需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet,不需要就选择实现List接口的比如ArrayList或LinkedList,然后再根据实现这些接口的集合的特点来选用。

ArrayList的扩容

ArrayList默认构造的数组大小为0,每次扩容会添加当前容量的一半。

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;

// 计算新容量的大小
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

HashMap的扩容与拉链算法

上面说到HashMap的容量默认要求为2的整数次幂,jdk中HashMap默认大小为16,当当前数据大小大于 容量xloadFactor 时将出发扩容,扩容需要对所有数据进行rehash,是一个比较耗费资源的操作。另外当hash对应的链表元素大于 TREEIFY_THRESHOLD(默认为8)时会将链表转化为红黑树,当hash对应的链表元素小于 UNTREEIFY_THRESHOLD(默认为6)时会将红黑树转化为链表。

向HashMap中添加数据时会调用 putMapEntries 方法:

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
// 容量超过threshold 时进行扩容
// 每次扩容时会重新计算 threshold = capacity x loadFactor
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}

找到节点hash对应的链表或红黑树位置后,putVal 方法负责将值插入到相应结构中。如果定位到的数组位置没有元素就直接插入。如果定位到的数组位置有元素就和要插入的key比较,如果key相同就直接覆盖,如果key不相同,就判断p是否是一个树节点,如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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;
}

remove方法则是上述过程的逆过程。