java 常用集合类数据结构介绍(list set map ConcurrentHashMap) 一

时间:2022-08-19 17:00:01

java 中最常用集合类的类层次结构如下:

java 常用集合类数据结构介绍(list set map ConcurrentHashMap) 一

java 常用集合类数据结构介绍(list set map ConcurrentHashMap) 一


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 的数据结构其实就是一个数组加链表的组合结构,如下图:

java 常用集合类数据结构介绍(list set map ConcurrentHashMap) 一

初始化:

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);    }


为什么是2 的N 倍呢,看一下下边的代码就一目了然

static int indexFor(int h, int length) {
        // 用的是&操作
        return h & (length-1);
    }
HashMap中indexfor,hash 等方法都是用的&操作,&是计算机中运算最快的操作符,HashMap 的优点之一


扩容:

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) {
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;
}
}
}
3:由于对多个has值相同的key 采用的是链表的方式,如果has 碰撞率很高,可能导致链表很长,查找数据就存在性能问题。所以对于has冲突高的可以优化has算法或者重写这个链表数据结构优化性能。