java 中最常用集合类的类层次结构如下:
ArrayList:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private transient Object[] elementData;
数据结构:
从ArrayList 的源码中可以看出,ArrayList 采用JAVA 最基本的数据结构数组作为底层的数据结构。
需要注意的地方:
1)当我们不断往Arraylist 中添加数据,ArrayList容量不够,扩容方式如下:
<pre name="code" class="java">private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新的数据容量是旧数组容量的1.5倍左右 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); }
<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">优点:当进行一次扩容后,后续需要经过一段时间才会扩容。</span>
缺点:由于扩容后内存是以前的1.5倍左右,容易导致oom 异常
Vector:
从Vector的源码可以看出,Vector 底层也是以数组为数据结构,与ArrayList最大的区别是线程安全的,是因为Vector基本在每个方法前加了synchronized关键字,如下便add 方法的源码
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
扩容也有一定的区别,如果未指定扩容的大小,默认需要扩容时是原来的两倍,源码如下:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//如果未指定capacityIncrement大小,默认扩容成原来的两倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
所以基本可以简单的理解为Vector 就是加了synchronized 的ArrayList.
HashMap:
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
从HashMap 的源码可以看出,HashMap 的数据结构其实就是一个数组加链表的组合结构,如下图:
初始化:
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
void init() { }
从HashMap初始化的源码可以看出,HashMap初始化的时候是一个空的(Entry<K,V>[]) EMPTY_TABLE对象,当第一次put 数据的时候才会初始化实质性数据。如下代码:
public V put(K key, V value) {
<span style="white-space:pre"></span>//当map 是个空对象,初始化,注意每次初始化map 都是2 的N 倍,可以看后边源码。
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
<span style="white-space:pre"></span>//当key 是一个空的时候直接put value 进去
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<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;
}
private void inflateTable(int toSize) { //获取的实际值是2 的N 倍 int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }
static int indexFor(int h, int length) {HashMap中indexfor,hash 等方法都是用的&操作,&是计算机中运算最快的操作符,HashMap 的优点之一
// 用的是&操作
return h & (length-1);
}
扩容:
HashMap中有一个loadFactor引子,默认是0.75,当HashMap 的大小大于数组大小*loadFactor的时候,就会发生扩容,比如原来的是8,当是数组大于8*0.75=6 的时候就会发生扩容,扩容成多大呢?不会是9,也不是是10,上边说过HashMap 的大小是2的N次方,所以扩容后就会是16。由于扩容后容量是翻翻,会让数据重新复制,对性能有一定的影响,所以如果知道数据的大小,可以直接指定初始话HashMap的大小。
通ArrayList,很多的OOM 异常也是HashMap扩容导致的,并不是内存不够。
Fail-Fast机制:
我们知道java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略
这样,当我们如下方式遍历map,同时用调用remove 删除部分数据的时候就会抛ConcurrentModificationException。
Map<String,String> map = new HashMap<String,String>();
map.put("1", "1");
map.put("2", "2");
for(Entry<String, String> set : map.entrySet()){
map.remove("1");
}
为什么会出现这种情况呢?从下边的源码可以看出:
final Entry<K,V> nextEntry() {
//当remove 数据后modeCount 会变化的,所以通过nextEntry遍历数据时,不能通过remove 方法删除数据
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
但是如果我们非有这个需求,在遍历的时候删除部分数据,那样可以通过如下方法:
Map<String,String> map = new HashMap<String,String>();为什么这样删除不会抛错,从下边源码可以看出:
map.put("1", "1");
map.put("2", "2");
Iterator<Entry<String, String>> it = map.entrySet().iterator();
while(it.hasNext()){
Entry<String, String> entry = it.next();
if("1".equals(entry.getKey())){
it.remove();
}
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
<span style="white-space:pre"></span> //删除的时候重新修改了expectedModCount 的值
expectedModCount = modCount;
}
HashMap 可能导致的问题:
1:扩容引起oom 异常。
2:HashMap 在高并发中容易导致死锁,从它的源码中可以看出,如下:
void transfer(Entry[] newTable, boolean rehash) {3:由于对多个has值相同的key 采用的是链表的方式,如果has 碰撞率很高,可能导致链表很长,查找数据就存在性能问题。所以对于has冲突高的可以优化has算法或者重写这个链表数据结构优化性能。
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> 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;
}
}
}