一、List
1.ArrayList
底层是数组实现，线程不安全
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
private int size;
...
}
因为底层是数组，所以读取速度快，增改查效率低，但可以自动扩容，其扩容原理的
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
扩容机制是每次扩容到原先的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
2. LinkedList
LinkedList底层是双向链表，与ArrayList相同，都是线程不安全的，但因为是链表实现，与ArrayList相反，增删改的速度很快，查询的速度慢
因为是双向链表，不存在扩容机制（新增节点）
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
...
}
3.Vector
与ArrayList相似，但是因为加了synchronized关键字，线程安全，也因此查询效率没有ArrayList高
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
另外，与ArrayList每次1.5倍增长不同，vector的扩容机制是以每次2倍速度扩容
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
private void ensureCapacityHelper(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
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);
}
总结：
| ArrayList | LinkedList | Vector | |
| 底层实现 | 数组 | 双向链表 | 数组 |
| 线程安全 | 不安全 | 不安全 | 安全(synchronized) |
| 扩容机制 | 每次1.5倍 | 新增node节点 | 每次2倍 |
二、Map
1.HashMap
特点
- 允许null键和null值
- key构成的集合是Set:无序的、不可重复的。所以，key所在的类要重写：equals()和hashCode()
- value构成的集合是Collection:无序的、可以重复的。所以，value所在的类要重写：equals()
- key-value构成一个entry，entry是无序的、不可重复的。
- 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等。
- 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true。
- 线程不安全
JDK1.7和1.8不同特点
- 1.7以前是数组+链表，使用头插法
- 1.8以后是数组+链表/红黑树，使用尾插法
扩容机制
当HashMap中链表的对象个数如果达到了8个，如果最大容量没有达到64，那么HashMap会扩容一倍。
如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。
2.HashTable
特点和HashMap一致，但有一个不同是HashTable是线程安全的。
3.ConcurrentHashMap
ConcurrentHashMap与HashMap的区别是比如value等数据，会使用volatile 修饰，保证了获取时的可见性。
static final class HashEntry<K,V> {
final K key; // 声明 key 为 final 型
final int hash; // 声明 hash 值为 final 型
volatile V value; // 声明 value 为 volatile 型
final HashEntry<K,V> next; // 声明 next 为 final 型
HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
this.key = key;
this.hash = hash;
this.next = next;
this.value = value;
}
}
ConcurrentHashMap 通过使用锁分段技术来保证线程安全。它将哈希表分成一些段（Segment），每个段都是一个独立的哈希表。在 ConcurrentHashMap 中，读操作和写操作可以同时进行，因为每个段都有自己的锁，不同的段之间可以并行处理。这种方式相当于把一个大的哈希表拆分成了多个小的哈希表，不同的线程可以同时操作不同的哈希表段，从而提高了并发性。
当一个线程要进行写操作时，它只需要获取对应的段的锁，而不是整个哈希表的锁。这样做的好处是，如果不同的线程要修改不同的哈希表段，它们就不会相互影响，从而提高了并发性。在读操作时，ConcurrentHashMap 并不需要加锁，因为每个段都是独立的，读操作不会影响其他段的数据。
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile int count;
transient int modCount;
transient int threshold;
transient volatile HashEntry<K,V>[] table;
final float loadFactor;
Segment(int initialCapacity, float lf) {
loadFactor = lf;
setTable(HashEntry.<K,V>newArray(initialCapacity));
}
}
标签：Map,Java,int,elementData,List,newCapacity,value,minCapacity,final From： https://www.cnblogs.com/wintermist/p/17217778.html