基础

List

        可重复，取出的顺序与添加的顺序一样。

        ArrayList：采用变长数组实现，内部使用数组存储添加的元素，如果元素的个数超过数组的长度，则自动扩容。

        LinkedList：内部采用双向链表实现。可以使用它模拟队列、栈等数据结构。

Set

        不可重复，无序(取出的顺序与添加的顺序不一样)

        HashSet：内部使用HashMap实现。其内部元素的排列顺序以hashCode为准。

        TreeSet：自己指定元素的排列顺序。

Map

        存储的是键值对。

        HashMap：内部以散列链表实现。

HashMap

        内部的数据结构为数组+链表，各个hash值相同的key的item以链表形式存储，而所有的链表的头节点又都存储在一个数组中。以put为例，如下：

@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);//获取key的hashCode，当然内部进行了别的处理。处理主要目的是使key的hash值能分散的均匀些
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {//取出该链表的表头tab[index]，然后通过next遍历该链表
if (e.hash == hash && key.equals(e.key)) {//如果有相同的key存在，就直接替换掉原来的value，并将旧value返回。
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;//返回旧值
}
}
// 没有key的节点，那就新建一个，并添加到节点中。
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}

        最后一步的addNewEntry是将新的key,value,hash构建成HashMapEntry对象，然后插入到该链表的表头。

        对于HashMapEntry，它表示链表的节点。对于链表的节点来说，它至少有一个指向于下一个节点的指针(这也是为什么需要将key,value重新封装成HashMapEntry对象的原因)，并有存储当前节点值的数值域。其成员变量如下：

final K key;
V value;
final int hash;
HashMapEntry<K, V> next;

        由于使用了数组存储链表的头节点，所以当item过多时就需要进行扩容，否则会导致链表越来越长，造成在查找时对性能的消耗(链表的查找需要从头节点一个个的遍历比对，不如数组方便)。扩容的方法就是doubleCapacity。如下：

private HashMapEntry<K, V>[] doubleCapacity() {
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {//达到最大容量，无法再进行扩容。其值为1<<30。
return oldTable;
}
int newCapacity = oldCapacity * 2;
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);//新建一个容量为原来2倍的HashMapEntry数组
if (size == 0) {//原来Map中没有元素，直接返回
return newTable;
}
for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry<K, V> e = oldTable[j];
if (e == null) {
continue;
}
int highBit = e.hash & oldCapacity;
HashMapEntry<K, V> broken = null;
newTable[j | highBit] = e;//将旧数组中的表头移到新数组中
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {//依次移动该链表中的每一个节点。
int nextHighBit = n.hash & oldCapacity;
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
return newTable;
}

        由于数组进行了扩容，所以旧数组中的节点的位置需要重新计算。相当于重构了整个map。

缺点

        1，无论该map中是否存有数据，都必须有一个数组，对内存有一定的浪费。

        2，需新建一个对象，用于表示链表中的节点。

        3，不支持基本数据类型，使用int作为key时，必须转换成Integer，也是一种浪费。

        4，扩容时必须重构map，还是浪费。

优点

        使用数组+链表结构，一方面利用了数组的查找方便的特性，另一方面又避免了数组对内存的高要求——分配的空间必须是连续的。

        对于大批量数据存储时，使用HashMap是一个不错的选择，最好能预估数据的大小，并且指定一个初始容量。这种方法可以避免了HashMap的多次扩容，减少性能的消耗。

ArrayDeque

        它是一个变长数组，内部含有指向数据首、尾元素的指针，类似于队列——先进先出。

        offer方法最终会执行到如下方法：

public void addLast(E e) {
if (e == null)
throw new NullPointerException("e == null");
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}

        再看一下pop方法：

public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked") E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null;
// Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}

        其最终会走到这两个方法，可以看出它只是从head中取一个元素，然后判断是否为null，如果是null就扔个异常。这是很简单粗暴的，它没有在取元素时判断当前数组中有没有元素，但这种方式我喜欢——简单直接，自己用的时候自己考虑这种事。

        而且也节约一个数组空间——使用数组实现循环队列时，一般需要留一下位置不用，这样才能判断出当前数组是没有元素还是已经满了。

        当然，ArrayDeque也不需要判断数组是不是满了，因为它会进行扩容。

        无论是从offer还是pop中都可以看出，ArrayDeque不接收null元素。

最后

以上就是温暖哈密瓜为你收集整理的java集合入门基础HashMapArrayDeque的全部内容，希望文章能够帮你解决java集合入门基础HashMapArrayDeque所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。