Java源码之集合框架（图）
最后更新于：2022-04-01 09:38:00
**百度“java 集合”图时，搜出来一张图，图蛮不错的，现在借用一下。**
**图片来自：[http://blog.csdn.net/bondsui/article/details/8520078](http://blog.csdn.net/bondsui/article/details/8520078)**
Java源码之LinkedHashMap
最后更新于：2022-04-01 09:37:58
**Java源码之LinkedHashMap**
转载请注明出处：[http://blog.csdn.net/itismelzp/article/details/50554412](http://blog.csdn.net/itismelzp/article/details/50554412)
# 一、LinkedHashMap概述
LinkedHashMap是Map接口的哈希表和链接列表实现，具有**可预知的迭代顺序**。此实现与 HashMap 的不同之处在于，LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。注意，如果在映射中重新插入键，则插入顺序不受影响。（如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true，则调用时会将键 k 重新插入到映射 m 中。）
注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
# 二、数据结构
数组 + 双链表结构
~~~
/**
* 双链表结点Entry，继承自HashMap.Node
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after; // 分别 指向前、后结点
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
~~~
# 三、LinkedHashMap源码
### 1.头文件
~~~
package java.util;
import java.util.function.Consumer;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.io.IOException;
~~~
### 2.继承与实现关系
~~~
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
~~~
### 3.属性
~~~
/**
* 双链表的头结点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 双链表的尾结点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 迭代顺序
* true:访问顺序
* false:插入顺序
*/
final boolean accessOrder;
~~~
### 4.构造方法
~~~
/**
* 构造方法一：
* 指定初始容量和装载因子
* 顺序规则：插入顺序
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 构造方法二：
* 指定初始容量并使用默认装载因子（0.75）
* 顺序规则：插入顺序
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 构造方法三：
* 使用默认初始容量（16）和默认装载因子（0.75）
* 顺序规则：插入顺序
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 构造方法四：
* 使用指定Map来构造
* 顺序规则：插入顺序
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
/**
* 构造方法五：
* 指定初始容量、装载因子和顺序规则构造
*
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
~~~
### 5.方法
### (1) 存储数据
LinkedListHashMap并未重写HashMap中的put方法。
具体实现可参考[【](http://blog.csdn.net/itismelzp/article/details/50525647)[Java源码之HashMap】](http://blog.csdn.net/itismelzp/article/details/50525647)[](http://blog.csdn.net/itismelzp/article/details/50525647)中put与putValue方法。
### (2) 读取数据
~~~
/**
* 如果key存在返回对应的value
* 如果key不存在返回指定的null
*/
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
/**
* 如果key存在返回对应的value
* 如果key不存在返回指定的defaultValue
*/
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
~~~
### 6.迭代
集合中的类都有一个共同的迭代方式，就是先把这个集合转化成Set视图，然后再对这个Set视图进行迭代。
~~~
/**
* 返回一个包含此Map所有元素的Set视图（实际是LinkedEntrySet类）
* 改变Map也会改变视图
*/
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
/**
* 内部类LinkedEntrySet
* 里面封闭了迭代方法
*/
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED |
Spliterator.DISTINCT);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
~~~
Java源码之Hashtable
最后更新于：2022-04-01 09:37:56
**Java源码之Hashtable**
转载请注明出处：[http://blog.csdn.net/itismelzp/article/details/50553711](http://blog.csdn.net/itismelzp/article/details/50553711)
一、Hashtable概述
类实现一个哈希表，该哈希表将键key对象映射到相应的值value对象。要求key和value都**非null**。为了成功地在哈希表中存储和获取对象，用作键的对象必须实现 hashCode 方法和 equals 方法。
Hashtable是线程同步的，但是非线程同步的HashMap完全可以取代它。
如果不需要线程安全，可以直接使用HashMap取代；
如果需要线程安全高并发，可以使用java.util.concurrent.ConcurrentHashMap取代。
二、Hashtable数据结构
Hashtable与jdk1.8之前的HashMap一样，是用**数组+链表**实现。
~~~
/**
* Hashtable数组冲突链结点
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next; // 下一个结点
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}
// Map.Entry Ops
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() {
return hash ^ Objects.hashCode(value);
}
public String toString() {
return key.toString()+"="+value.toString();
}
}
~~~
三、Hashtable源码
1.头文件
~~~
package java.util;
import java.io.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.BiConsumer;
import java.util.function.Function;
import java.util.function.BiFunction;
~~~
2.实现与继承
~~~
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
~~~
3.属性
~~~
/**
* hash表数组
*/
private transient Entry<?,?>[] table;
/**
* 数组中存储的元素个数
*/
private transient int count;
/**
* 阈值，超过这个值数组要扩容
* threshold = capacity * loadFactor
*/
private int threshold;
/**
* 装载因子
*/
private float loadFactor;
/**
* 修改次数
* 采用fail-fast机制
*/
private transient int modCount = 0;
~~~
4.构造器与方法
这部分与HashMap的主要区别是，hash函数的算法。
这里用的是典型的除留取余法：
~~~
int index = (hash & 0x7FFFFFFF) % tab.length;
~~~
这部分的构造器、方法与HashMap的差别不大，只是在方法前面加了synchronized使方法同步。
~~~
/**
* 构造方法一：
* 用指定容量 + 指定装载因子构造
*/
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
/**
* 构造方法二：
* 指定容量 + 默认装载因子构造
*/
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
/**
* 构造方法三：
* 使用默认容量11 + 默认装载因子
*/
public Hashtable() {
this(11, 0.75f);
}
/**
* 构造方法四：
* 使用Map构造
*/
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
/**
* 返回容量大小
*/
public synchronized int size() {
return count;
}
/**
* 判空
*/
public synchronized boolean isEmpty() {
return count == 0;
}
/**
* 返回所有key值的枚举集合
*/
public synchronized Enumeration<K> keys() {
return this.<K>getEnumeration(KEYS);
}
/**
* 返回所有value值的枚举集合
*/
public synchronized Enumeration<V> elements() {
return this.<V>getEnumeration(VALUES);
}
/**
* 判断是否包含value值对象
*/
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
/**
* 判断是否包含value值对象
*/
public boolean containsValue(Object value) {
return contains(value);
}
/**
* 判断是否包含key键值对象
*/
public synchronized boolean containsKey(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}
/**
* 获取键值key对应的value
*/
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
/**
* 规定的最大数组容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩容（2*oldCap + 1）
*/
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
/**
* 添加元素
* 原key键值存在，返回原key键对应的value
* 原key键值不存在，返回null
*/
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
/**
* 删除并返回要删除的value
*/
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}
/**
* 将Map中的元素添加进来
*/
public synchronized void putAll(Map<? extends K, ? extends V> t) {
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
put(e.getKey(), e.getValue());
}
/**
* 清空
*/
public synchronized void clear() {
Entry<?,?> tab[] = table;
modCount++;
for (int index = tab.length; --index >= 0; )
tab[index] = null;
count = 0;
}
/**
* 克隆对象
*/
public synchronized Object clone() {
try {
Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
t.table = new Entry<?,?>[table.length];
for (int i = table.length ; i-- > 0 ; ) {
t.table[i] = (table[i] != null)
? (Entry<?,?>) table[i].clone() : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
private <T> Enumeration<T> getEnumeration(int type) {
if (count == 0) {
return Collections.emptyEnumeration();
} else {
return new Enumerator<>(type, false);
}
}
// 获得迭代器
private <T> Iterator<T> getIterator(int type) {
if (count == 0) {
return Collections.emptyIterator();
} else {
return new Enumerator<>(type, true);
}
}
// Views
/**
* Each of these fields are initialized to contain an instance of the
* appropriate view the first time this view is requested. The views are
* stateless, so there's no reason to create more than one of each.
*/
private transient volatile Set<K> keySet;
private transient volatile Set<Map.Entry<K,V>> entrySet;
private transient volatile Collection<V> values;
/**
* 返回包含此map的Set视图
* 通过Set视图可获得迭代器Iterator对象，对map进行迭代
*/
public Set<Map.Entry<K,V>> entrySet() {
if (entrySet==null)
entrySet = Collections.synchronizedSet(new EntrySet(), this);
return entrySet;
}
// Set视图类
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return getIterator(ENTRIES);
}
public boolean add(Map.Entry<K,V> o) {
return super.add(o);
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
Object key = entry.getKey();
Entry<?,?>[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index]; e != null; e = e.next)
if (e.hash==hash && e.equals(entry))
return true;
return false;
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
Entry<?,?>[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
modCount++;
if (prev != null)
prev.next = e.next;
else
tab[index] = e.next;
count--;
e.value = null;
return true;
}
}
return false;
}
public int size() {
return count;
}
public void clear() {
Hashtable.this.clear();
}
}
/**
* Returns a {@link Collection} view of the values contained in this map.
* The collection is backed by the map, so changes to the map are
* reflected in the collection, and vice-versa. If the map is
* modified while an iteration over the collection is in progress
* (except through the iterator's own <tt>remove</tt> operation),
* the results of the iteration are undefined. The collection
* supports element removal, which removes the corresponding
* mapping from the map, via the <tt>Iterator.remove</tt>,
* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
* support the <tt>add</tt> or <tt>addAll</tt> operations.
*
* @since 1.2
*/
public Collection<V> values() {
if (values==null)
values = Collections.synchronizedCollection(new ValueCollection(),
this);
return values;
}
private class ValueCollection extends AbstractCollection<V> {
public Iterator<V> iterator() {
return getIterator(VALUES);
}
public int size() {
return count;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
Hashtable.this.clear();
}
}
// Comparison and hashing
/**
* 实现equals
* 判等
*/
public synchronized boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map<?,?> t = (Map<?,?>) o;
if (t.size() != size())
return false;
try {
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(t.get(key)==null && t.containsKey(key)))
return false;
} else {
if (!value.equals(t.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
/**
* 实现hashCode
*/
public synchronized int hashCode() {
/*
* This code detects the recursion caused by computing the hash code
* of a self-referential hash table and prevents the stack overflow
* that would otherwise result. This allows certain 1.1-era
* applets with self-referential hash tables to work. This code
* abuses the loadFactor field to do double-duty as a hashCode
* in progress flag, so as not to worsen the space performance.
* A negative load factor indicates that hash code computation is
* in progress.
*/
int h = 0;
if (count == 0 || loadFactor < 0)
return h; // Returns zero
loadFactor = -loadFactor; // Mark hashCode computation in progress
Entry<?,?>[] tab = table;
for (Entry<?,?> entry : tab) {
while (entry != null) {
h += entry.hashCode();
entry = entry.next;
}
}
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
}
@Override
public synchronized boolean replace(K key, V oldValue, V newValue) {
Objects.requireNonNull(oldValue);
Objects.requireNonNull(newValue);
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for (; e != null; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
if (e.value.equals(oldValue)) {
e.value = newValue;
return true;
} else {
return false;
}
}
}
return false;
}
/*
* 替换
*/
@Override
public synchronized V replace(K key, V value) {
Objects.requireNonNull(value);
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for (; e != null; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
return null;
}
~~~
Java源码之HashSet
最后更新于：2022-04-01 09:37:53
**Java源码之HashSet**
转载请注明出处：[http://blog.csdn.net/itismelzp/article/details/50540610](http://blog.csdn.net/itismelzp/article/details/50540610)
# 一、HashSet概述
HashSet是java.util包中的类，该容器只能存储不重复的对象。允许使用null元素。
它不保证set 的迭代顺序，特别是它不保证该顺序恒久不变，这点跟HashMap一样，事实上在HashSet内部就是使用HashMap来存储元素的。
它实现了Set接口，由哈希表（实际上是一个HashMap实例）支持。
# 二、HashSet实现
### 1.头文件与继承关系
~~~
package java.util;
import java.util.Set;
import java.io.InvalidObjectException;
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
~~~
### 2.属性
~~~
private transient HashMap<E,Object> map;
// 为支持Map所用的哑值（看到add方法时自然会知道干什么用的）
private static final Object PRESENT = new Object();
~~~
### 3.构造方法（4个）
~~~
/**
* 构造函数一：
* 构造空的HashSet，内部使用HashMap实现，
* 并使用默认的容量16和默认装载因子0.75
*/
public HashSet() {
map = new HashMap<>();
}
/**
* 构造函数二：
* 利用指定的"集合"构造HashSet
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 构造方法三：
* 使用指定的容量和装载因子来构造HashSet
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
* 构造方法四：
* 使用指定容量(默认装载因子)构造HashSet
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
/**
* 构造方法四：
* 以指定的initialCapacity、loadFactor和dummy构造一个LinkedHashMap。
* 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
~~~
### 4.方法
~~~
/**
* 返回一个迭代HashSet元素的迭代器，元素的顺序不是固定的
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
/**
* 返回set中元素个数，即map大小
*/
public int size() {
return map.size();
}
/**
* 判空
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
* 判断HashSet中是否包含元素o
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* 添加元素e，确保元素不重复
* map中put方法说明：
* 如果map中键e存在，则返回旧的键e对应的value值；
* 如果map中键e不存在，则返回null
* 返回值：有重复返回false，无重复返回true
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* 删除元素o
* 返回值：如果元素存在返回true，不存在返回false
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
/**
* 删除所有元素
*/
public void clear() {
map.clear();
}
/**
* 克隆一个新HashSet
*/
@SuppressWarnings("unchecked")
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
~~~
========================================================================
HashSet的源码比较简单，下面是完整的源码：
~~~
/*
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
package java.util;
import java.io.InvalidObjectException;
/**
* This class implements the <tt>Set</tt> interface, backed by a hash table
* (actually a <tt>HashMap</tt> instance). It makes no guarantees as to the
* iteration order of the set; in particular, it does not guarantee that the
* order will remain constant over time. This class permits the <tt>null</tt>
* element.
*
* <p>This class offers constant time performance for the basic operations
* (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
* assuming the hash function disperses the elements properly among the
* buckets. Iterating over this set requires time proportional to the sum of
* the <tt>HashSet</tt> instance's size (the number of elements) plus the
* "capacity" of the backing <tt>HashMap</tt> instance (the number of
* buckets). Thus, it's very important not to set the initial capacity too
* high (or the load factor too low) if iteration performance is important.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a hash set concurrently, and at least one of
* the threads modifies the set, it <i>must</i> be synchronized externally.
* This is typically accomplished by synchronizing on some object that
* naturally encapsulates the set.
*
* If no such object exists, the set should be "wrapped" using the
* {@link Collections#synchronizedSet Collections.synchronizedSet}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the set:<pre>
* Set s = Collections.synchronizedSet(new HashSet(...));</pre>
*
* <p>The iterators returned by this class's <tt>iterator</tt> method are
* <i>fail-fast</i>: if the set is modified at any time after the iterator is
* created, in any way except through the iterator's own <tt>remove</tt>
* method, the Iterator throws a {@link ConcurrentModificationException}.
* Thus, in the face of concurrent modification, the iterator fails quickly
* and cleanly, rather than risking arbitrary, non-deterministic behavior at
* an undetermined time in the future.
*
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @param <E> the type of elements maintained by this set
*
* @author Josh Bloch
* @author Neal Gafter
* @see Collection
* @see Set
* @see TreeSet
* @see HashMap
* @since 1.2
*/
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
/**
* Constructs a new set containing the elements in the specified
* collection. The <tt>HashMap</tt> is created with default load factor
* (0.75) and an initial capacity sufficient to contain the elements in
* the specified collection.
*
* @param c the collection whose elements are to be placed into this set
* @throws NullPointerException if the specified collection is null
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* the specified initial capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* the specified initial capacity and default load factor (0.75).
*
* @param initialCapacity the initial capacity of the hash table
* @throws IllegalArgumentException if the initial capacity is less
* than zero
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
/**
* Constructs a new, empty linked hash set. (This package private
* constructor is only used by LinkedHashSet.) The backing
* HashMap instance is a LinkedHashMap with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @param dummy ignored (distinguishes this
* constructor from other int, float constructor.)
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
/**
* Returns an iterator over the elements in this set. The elements
* are returned in no particular order.
*
* @return an Iterator over the elements in this set
* @see ConcurrentModificationException
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
/**
* Returns the number of elements in this set (its cardinality).
*
* @return the number of elements in this set (its cardinality)
*/
public int size() {
return map.size();
}
/**
* Returns <tt>true</tt> if this set contains no elements.
*
* @return <tt>true</tt> if this set contains no elements
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
* Returns <tt>true</tt> if this set contains the specified element.
* More formally, returns <tt>true</tt> if and only if this set
* contains an element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this set is to be tested
* @return <tt>true</tt> if this set contains the specified element
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element <tt>e</tt> to this set if
* this set contains no element <tt>e2</tt> such that
* <tt>(e==null ? e2==null : e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns <tt>false</tt>.
*
* @param e element to be added to this set
* @return <tt>true</tt> if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* Removes the specified element from this set if it is present.
* More formally, removes an element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>,
* if this set contains such an element. Returns <tt>true</tt> if
* this set contained the element (or equivalently, if this set
* changed as a result of the call). (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return <tt>true</tt> if the set contained the specified element
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
/**
* Removes all of the elements from this set.
* The set will be empty after this call returns.
*/
public void clear() {
map.clear();
}
/**
* Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
* themselves are not cloned.
*
* @return a shallow copy of this set
*/
@SuppressWarnings("unchecked")
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
/**
* Save the state of this <tt>HashSet</tt> instance to a stream (that is,
* serialize it).
*
* @serialData The capacity of the backing <tt>HashMap</tt> instance
* (int), and its load factor (float) are emitted, followed by
* the size of the set (the number of elements it contains)
* (int), followed by all of its elements (each an Object) in
* no particular order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out HashMap capacity and load factor
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
// Write out size
s.writeInt(map.size());
// Write out all elements in the proper order.
for (E e : map.keySet())
s.writeObject(e);
}
/**
* Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read capacity and verify non-negative.
int capacity = s.readInt();
if (capacity < 0) {
throw new InvalidObjectException("Illegal capacity: " +
capacity);
}
// Read load factor and verify positive and non NaN.
float loadFactor = s.readFloat();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// Read size and verify non-negative.
int size = s.readInt();
if (size < 0) {
throw new InvalidObjectException("Illegal size: " +
size);
}
// Set the capacity according to the size and load factor ensuring that
// the HashMap is at least 25% full but clamping to maximum capacity.
capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
HashMap.MAXIMUM_CAPACITY);
// Create backing HashMap
map = (((HashSet<?>)this) instanceof LinkedHashSet ?
new LinkedHashMap<E,Object>(capacity, loadFactor) :
new HashMap<E,Object>(capacity, loadFactor));
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
@SuppressWarnings("unchecked")
E e = (E) s.readObject();
map.put(e, PRESENT);
}
}
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* set.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
* {@link Spliterator#DISTINCT}. Overriding implementations should document
* the reporting of additional characteristic values.
*
* @return a {@code Spliterator} over the elements in this set
* @since 1.8
*/
public Spliterator<E> spliterator() {
return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
}
}
~~~
Java源码之HashMap
最后更新于：2022-04-01 09:37:51
**Java源码之HashMap**
转载请注意出处：[http://blog.csdn.net/itismelzp/article/details/50525647](http://blog.csdn.net/itismelzp/article/details/50525647)
# 一、HashMap概述
HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。
~~~
Map map = Collections.synchronizedMap(new HashMap());
~~~
# 二、HashMap中的数据结构
### 1.jdk1.8之前
在jdk1.8之前的HashMap是基于**数组+链表**来实现，即严蔚敏版《数据结构》中**哈希表（散列表）**链地址法，哈希表的优点是查询速度快。
HashMap中主要是通过key的hashCode来计算hash值，只要hashCode相同，计算出来的hash值就一样。如果存储的对象多了，就有可能不同的对象映射到相同的hash值，这就是所谓的hash冲突。HashMap中所用解决hash冲突的方法是链地址法。
可参考严蔚敏版《数据结构》哈希表解决hash冲突的**链地址法**。
图中，黄色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。
### 2.jdk1.8中HashMap的实现方式
jdk1.8中对HashMap做的很大的改进，采用**数组+链表+红黑树**实现，当链表长度超过阈值(8)时，将链表转换为红黑树，大大减少了hash冲突时查找时间（从原来的O(n)->O(logn)）。由于红黑树的结点空间是链表空间的2倍，为了节省空间，当链表长度减少（如删除操作）到阈值(6)时，又会转换为链表形式。
链表中的结点对应HashMap中的Node类（jdk1.8之前用的是Entry类，原理差不多），具体如下：
~~~
// Node是单向链表，实现了Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // hash值
final K key; // 键
V value; // 值
Node<K,V> next; // 指向下一个结点
/*
* 构造函数
* 利用（hash值、键、值、下一个结点）来构造结点
*/
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final String toString() { return key + "=" + value; }
// 实现hashCode()
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 判断两个结点是否相等
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
~~~
HashMap其实就是一个Node数组，Node对象中包含了键和值，其中next也是一个Node对象，它用来处理hash冲突，
使具有相同hash值的结点连在一个链表或树中。
下面是红黑树结点：
它继承自LinkedListMap.Entry，这是一种双链表结点（具体可参考[【Java源码之LinkedHashMap】](http://blog.csdn.net/itismelzp/article/details/50554412)）。
~~~
/**
* 红黑树结点，继承自LinkedHashMap.Entry
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 指向父结点
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 结点颜色（红或黑）
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 返回当前节点所在树的树结点
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
~~~
# 三、HashMap源码
### 1.头文件
~~~
package java.util;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
~~~
### 2.继承情况
~~~
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
~~~
### 3.属性
~~~
/**
* 默认初始容量 - 必须是2的幂次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
/**
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 当构造函数不指定时，默认（Hash表）装载因子。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表->红黑树的阈值
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 红黑树->链表的阈值
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
~~~
~~~
/**
* 存放元素的Node数组
*/
transient Node<K,V>[] table;
/**
* 装Map用Set集合（可用于迭代Map）
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* map中的包含的元素个数
*/
transient int size;
/**
* HashMap的修改次数
*/
transient int modCount; // fail-fast机制，下面有解释
/**
* 阈值 - 当实际大小超过临界值时，会进行扩容。threshold = capacity * loadFactor(注意这里的capacity与size的区别)
*/
int threshold; // 默认情况下是12
/**
* 装载因子，表示Hsah表中元素的填满的程度
*/
final float loadFactor;
~~~
fail-fast机制：即快速失败机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；
那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
### 4.构造函数（4个）
~~~
/**
* 构造函数一：指定初始容量和装载因子
*/
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;
this.threshold = tableSizeFor(initialCapacity); // tableSizeFor方法会将initialCapacity转化成2的幂次方，详见tableSizeFor方法
}
/**
* 构造函数二：指定初始容量并使用默认装载因子（0.75）
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造函数三：使用默认初始容量（16）和默认装载因子（0.75）
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 构造函数四：使用另一个Map来构造
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
~~~
### 5.常用方法
### **(1)hash方法**
严版《数据结构》中提到的哈希函数的构造方法有：
- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留取余法
在**Hashtable**中用的是 **除留取余法**， 即便于计算，又能减少冲突。
~~~
index = (hash & 0x7FFFFFFF) % tab.length;
~~~
但是取模中的除法运算效率很低，HashMap则通过h & (length - 1)替代取模，得到所在数组位置，这样效率会高很多。
~~~
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
~~~
代码中，首先由key值通过hashCode()方法获取h值，再通过h & (length - 1)来得到所在数组的位置。
在HashMap实现中还可以看到如下代码取代了jdk1.8以前用while循环来保证哈希表的容量一直是2的整数倍数，用移位操作取代了循环移位。
~~~
/**
* 根据给定的容量cap来构造符合2的次幂的值
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; // ">>>"为右移填0操作，即不管符号位是什么都用0填充
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
~~~
可以从源码看出，在HashMap的构造函数中，都直接或间接的调用了tableSizeFor函数。
下面分析原因：length为2的整数幂保证了length-1最后一位（当然是二进制表示）为**1**，从而保证了取索引操作 h & (length - 1)的最后一位同时有为0和为1的可能性，保证了散列的均匀性。反过来，如果length为奇数时，length-1最后一位为**0**，这样与h按位“与”的最后一位肯定为0，即索引位置肯定是偶数，这样数组的奇数位置全部没有放置元素，浪费了大量空间。
### (2)数据读取：get和getNode方法
~~~
/**
* 根据key返回对应的value值
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 实现Map.get和相关方法
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) { // 使用hash & (length-1)得到所在位置
if (first.hash == hash && // 判断头结点
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 搜索“冲突”链表或红黑树
if ((e = first.next) != null) {
if (first instanceof TreeNode) // 红黑树情况
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do { // 链表情况
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
~~~
### (3)存储数据：put和putValue方法
~~~
/**
* 实现Map.put和相关方法
* 参数hash：key的hash值
* 参数key：要设置的key值
* 参数value：要设置的value值
* 参数onlyIfAbsent if true, don't change existing value
* 如果为假，则替换原来的value
* 参数evict：if false, the table is in creation mode.
* 返回：替换时返回oldValue，非替换时返回null
*/
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) // 如果tab为空，则调用resize分配内存
n = (tab = resize()).length;
// 使用hash & (lengt-1)得到存入位置，得到插入位置中的结点p
if ((p = tab[i = (n - 1) & hash]) == null) // 结点p为null，直接插入
tab[i] = newNode(hash, key, value, null);
else { // 插入位置冲突
Node<K,V> e; K k;
// 与第一个结点相同：hash值与key值相同（1）
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) {
// p从表头依次后移
if ((e = p.next) == null) { // 到达链尾
p.next = newNode(hash, key, value, null); // 接入链尾
if (binCount >= TREEIFY_THRESHOLD - 1) // 达到（链->树）阈值
treeifyBin(tab, hash);
break;
}
// 找到"相同"对象：hash值与key值相同（2）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // p后移：p=p.next
}
}
// 处理上述两处hash值与key值相同
if (e != null) { // 已有key值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) // 如果size>threshold时进行扩容，见后面的reise()函数
resize();
afterNodeInsertion(evict);
return null;
}
~~~
### (4)扩容策略：resize方法
当**size > threshold**时调用resize()扩容。
~~~
/**
* 初始化或加倍容量大小。
*
* 返回新的hash table数组
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { // 超过最大容量，无法扩容，只能改变阈值
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 容量加倍
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 阈值加倍
}
else if (oldThr > 0) // 用阈值初始值新的容量
newCap = oldThr;
else { // 当阈值==0时
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 下面是将旧tab中的Node转移到新tab中，分链表和红黑树两种情况
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 红黑树情况
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 链表情况
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
~~~
Java源码之Stack
最后更新于：2022-04-01 09:37:49
**Java源码之Stack**
转载请注明出处：[http://blog.csdn.net/itismelzp/article/details/50371987](http://blog.csdn.net/itismelzp/article/details/50371987)
Stack的源码较短，在这里直接贴出：
Stack继承自Vetor实现的，所以基础的策略也来自Vector
~~~
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package java.util;
/**
* {@code Stack} is a Last-In/First-Out(LIFO) data structure which represents a
* stack of objects. It enables users to pop to and push from the stack,
* including null objects. There is no limit to the size of the stack.
*/
public class Stack<E> extends Vector<E> {
private static final long serialVersionUID = 1224463164541339165L;
/**
* Constructs a stack with the default size of {@code Vector}.
*/
public Stack() {
}
/**
* 调用父类方法isEmpty判断
*/
public boolean empty() {
return isEmpty();
}
/**
* 返回栈顶元素（元素不删除）
*/
@SuppressWarnings("unchecked")
public synchronized E peek() {
try {
return (E) elementData[elementCount - 1]; // elementData见Vector
} catch (IndexOutOfBoundsException e) {
throw new EmptyStackException();
}
}
/**
* 删除栈顶元素，并返回顶栈元素
*/
@SuppressWarnings("unchecked")
public synchronized E pop() {
if (elementCount == 0) {
throw new EmptyStackException();
}
final int index = --elementCount;
final E obj = (E) elementData[index];
elementData[index] = null;
modCount++;
return obj;
}
/**
* 元素入栈
*/
public E push(E object) {
addElement(object); // 依然是父类方法addElement
return object;
}
/**
* 返回元素在栈中的索引（栈顶元素索引为0，往下递增）
*/
public synchronized int search(Object o) {
final Object[] dumpArray = elementData;
final int size = elementCount;
if (o != null) {
for (int i = size - 1; i >= 0; i--) {
if (o.equals(dumpArray[i])) {
return size - i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (dumpArray[i] == null) {
return size - i;
}
}
}
return -1;
}
}
~~~
Java源码之Vector
最后更新于：2022-04-01 09:37:46
**Java源码之Vector**
转载请注明出处：[http://blog.csdn.net/itismelzp/article/details/50371830](http://blog.csdn.net/itismelzp/article/details/50371830)
概述
Vector与C++中的vector类似，即动态数组。它可以自适合数组容量，它还是线程安全的，即线程同步的。
如果不需要线程，可以用ArrayList取代它。
头文件：
~~~
package java.util;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Array;
~~~
继承与实现：
~~~
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
~~~
属性：
~~~
/**
* 当前向量中元数个数
*/
protected int elementCount;
/**
* 对象数组，用于存放实际数据
*/
protected Object[] elementData;
/**
* 增长因子：用户可指定大小，不指定则为0。
* 当为0时，向量按2倍容量的方式扩容
* 当不为0时，向量按此参数固定数量扩容
*/
protected int capacityIncrement;
// 向量默认大小（当用户不指定的时候使用该值）
private static final int DEFAULT_SIZE = 10;
~~~
构造方法：
~~~
/**
* 构造方法一：
* 无参数：用默认大小10，构造向量，capacityIncrement = 0
*/
public Vector() {
this(DEFAULT_SIZE, 0);
}
/**
* 构造方法一：
* 用指定大小构造
*
* 参数capacity：向量元素数组大小
*/
public Vector(int capacity) {
this(capacity, 0);
}
/**
* 构造方法三：指定大小、增长因子构造向量
* 参数1：初始化容量大小
* 参数2：增长因子
*/
public Vector(int capacity, int capacityIncrement) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
elementData = newElementArray(capacity);
elementCount = 0;
this.capacityIncrement = capacityIncrement;
}
/**
* 构造方法四：用集合构造向量
*
* 参数 collection：集合
*/
public Vector(Collection<? extends E> collection) {
this(collection.size(), 0);
Iterator<? extends E> it = collection.iterator();
while (it.hasNext()) {
elementData[elementCount++] = it.next();
}
}
~~~
常用方法：
~~~
/**
* 添加元素到向量
*
* 参数：添加的元素
* 返回true
*/
@Override
public synchronized boolean add(E object) {
if (elementCount == elementData.length) {
growByOne();
}
elementData[elementCount++] = object;
modCount++;
return true;
}
/**
* JIT optimization
*/
private void growByOne() {
int adding = 0;
if (capacityIncrement <= 0) {
if ((adding = elementData.length) == 0) { // 2倍扩容
adding = 1;
}
} else {
adding = capacityIncrement; // 按指定增长因子增加
}
E[] newData = newElementArray(elementData.length + adding);
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
}
~~~
下面是Vector的全部源码，感兴趣的朋友可以自行查看：
~~~
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package java.util;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Array;
/**
* Vector is an implementation of {@link List}, backed by an array and synchronized.
* All optional operations including adding, removing, and replacing elements are supported.
*
* <p>All elements are permitted, including null.
*
* <p>This class is equivalent to {@link ArrayList} with synchronized operations. This has a
* performance cost, and the synchronization is not necessarily meaningful to your application:
* synchronizing each call to {@code get}, for example, is not equivalent to synchronizing on the
* list and iterating over it (which is probably what you intended). If you do need very highly
* concurrent access, you should also consider {@link java.util.concurrent.CopyOnWriteArrayList}.
*
* @param <E> The element type of this list.
*/
public class Vector<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, Serializable {
private static final long serialVersionUID = -2767605614048989439L;
/**
* The number of elements or the size of the vector.
*/
protected int elementCount;
/**
* The elements of the vector.
*/
protected Object[] elementData;
/**
* How many elements should be added to the vector when it is detected that
* it needs to grow to accommodate extra entries. If this value is zero or
* negative the size will be doubled if an increase is needed.
*/
protected int capacityIncrement;
private static final int DEFAULT_SIZE = 10;
/**
* Constructs a new vector using the default capacity.
*/
public Vector() {
this(DEFAULT_SIZE, 0);
}
/**
* Constructs a new vector using the specified capacity.
*
* @param capacity
* the initial capacity of the new vector.
* @throws IllegalArgumentException
* if {@code capacity} is negative.
*/
public Vector(int capacity) {
this(capacity, 0);
}
/**
* Constructs a new vector using the specified capacity and capacity
* increment.
*
* @param capacity
* the initial capacity of the new vector.
* @param capacityIncrement
* the amount to increase the capacity when this vector is full.
* @throws IllegalArgumentException
* if {@code capacity} is negative.
*/
public Vector(int capacity, int capacityIncrement) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
elementData = newElementArray(capacity);
elementCount = 0;
this.capacityIncrement = capacityIncrement;
}
/**
* Constructs a new instance of {@code Vector} containing the elements in
* {@code collection}. The order of the elements in the new {@code Vector}
* is dependent on the iteration order of the seed collection.
*
* @param collection
* the collection of elements to add.
*/
public Vector(Collection<? extends E> collection) {
this(collection.size(), 0);
Iterator<? extends E> it = collection.iterator();
while (it.hasNext()) {
elementData[elementCount++] = it.next();
}
}
@SuppressWarnings("unchecked")
private E[] newElementArray(int size) {
return (E[]) new Object[size];
}
/**
* Adds the specified object into this vector at the specified location. The
* object is inserted before any element with the same or a higher index
* increasing their index by 1. If the location is equal to the size of this
* vector, the object is added at the end.
*
* @param location
* the index at which to insert the element.
* @param object
* the object to insert in this vector.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location > size()}.
* @see #addElement
* @see #size
*/
@Override
public void add(int location, E object) {
insertElementAt(object, location);
}
/**
* Adds the specified object at the end of this vector.
*
* @param object
* the object to add to the vector.
* @return {@code true}
*/
@Override
public synchronized boolean add(E object) {
if (elementCount == elementData.length) {
growByOne();
}
elementData[elementCount++] = object;
modCount++;
return true;
}
/**
* Inserts the objects in the specified collection at the specified location
* in this vector. The objects are inserted in the order in which they are
* returned from the Collection iterator. The elements with an index equal
* or higher than {@code location} have their index increased by the size of
* the added collection.
*
* @param location
* the location to insert the objects.
* @param collection
* the collection of objects.
* @return {@code true} if this vector is modified, {@code false} otherwise.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0} or {@code location > size()}.
*/
@Override
public synchronized boolean addAll(int location, Collection<? extends E> collection) {
if (location >= 0 && location <= elementCount) {
int size = collection.size();
if (size == 0) {
return false;
}
int required = size - (elementData.length - elementCount);
if (required > 0) {
growBy(required);
}
int count = elementCount - location;
if (count > 0) {
System.arraycopy(elementData, location, elementData, location
+ size, count);
}
Iterator<? extends E> it = collection.iterator();
while (it.hasNext()) {
elementData[location++] = it.next();
}
elementCount += size;
modCount++;
return true;
}
throw arrayIndexOutOfBoundsException(location, elementCount);
}
/**
* Adds the objects in the specified collection to the end of this vector.
*
* @param collection
* the collection of objects.
* @return {@code true} if this vector is modified, {@code false} otherwise.
*/
@Override
public synchronized boolean addAll(Collection<? extends E> collection) {
return addAll(elementCount, collection);
}
/**
* Adds the specified object at the end of this vector.
*
* @param object
* the object to add to the vector.
*/
public synchronized void addElement(E object) {
if (elementCount == elementData.length) {
growByOne();
}
elementData[elementCount++] = object;
modCount++;
}
/**
* Returns the number of elements this vector can hold without growing.
*
* @return the capacity of this vector.
* @see #ensureCapacity
* @see #size
*/
public synchronized int capacity() {
return elementData.length;
}
/**
* Removes all elements from this vector, leaving it empty.
*
* @see #isEmpty
* @see #size
*/
@Override
public void clear() {
removeAllElements();
}
/**
* Returns a new vector with the same elements, size, capacity and capacity
* increment as this vector.
*
* @return a shallow copy of this vector.
* @see java.lang.Cloneable
*/
@Override
@SuppressWarnings("unchecked")
public synchronized Object clone() {
try {
Vector<E> vector = (Vector<E>) super.clone();
vector.elementData = elementData.clone();
return vector;
} catch (CloneNotSupportedException e) {
throw new AssertionError(e);
}
}
/**
* Searches this vector for the specified object.
*
* @param object
* the object to look for in this vector.
* @return {@code true} if object is an element of this vector,
* {@code false} otherwise.
* @see #indexOf(Object)
* @see #indexOf(Object, int)
* @see java.lang.Object#equals
*/
@Override
public boolean contains(Object object) {
return indexOf(object, 0) != -1;
}
/**
* Searches this vector for all objects in the specified collection.
*
* @param collection
* the collection of objects.
* @return {@code true} if all objects in the specified collection are
* elements of this vector, {@code false} otherwise.
*/
@Override
public synchronized boolean containsAll(Collection<?> collection) {
return super.containsAll(collection);
}
/**
* Attempts to copy elements contained by this {@code Vector} into the
* corresponding elements of the supplied {@code Object} array.
*
* @param elements
* the {@code Object} array into which the elements of this
* vector are copied.
* @throws IndexOutOfBoundsException
* if {@code elements} is not big enough.
* @see #clone
*/
public synchronized void copyInto(Object[] elements) {
System.arraycopy(elementData, 0, elements, 0, elementCount);
}
/**
* Returns the element at the specified location in this vector.
*
* @param location
* the index of the element to return in this vector.
* @return the element at the specified location.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #size
*/
@SuppressWarnings("unchecked")
public synchronized E elementAt(int location) {
if (location < elementCount) {
return (E) elementData[location];
}
throw arrayIndexOutOfBoundsException(location, elementCount);
}
/**
* Returns an enumeration on the elements of this vector. The results of the
* enumeration may be affected if the contents of this vector is modified.
*
* @return an enumeration of the elements of this vector.
* @see #elementAt
* @see Enumeration
*/
public Enumeration<E> elements() {
return new Enumeration<E>() {
int pos = 0;
public boolean hasMoreElements() {
return pos < elementCount;
}
@SuppressWarnings("unchecked")
public E nextElement() {
synchronized (Vector.this) {
if (pos < elementCount) {
return (E) elementData[pos++];
}
}
throw new NoSuchElementException();
}
};
}
/**
* Ensures that this vector can hold the specified number of elements
* without growing.
*
* @param minimumCapacity
* the minimum number of elements that this vector will hold
* before growing.
* @see #capacity
*/
public synchronized void ensureCapacity(int minimumCapacity) {
if (elementData.length < minimumCapacity) {
int next = (capacityIncrement <= 0 ? elementData.length
: capacityIncrement)
+ elementData.length;
grow(minimumCapacity > next ? minimumCapacity : next);
}
}
/**
* Compares the specified object to this vector and returns if they are
* equal. The object must be a List which contains the same objects in the
* same order.
*
* @param object
* the object to compare with this object
* @return {@code true} if the specified object is equal to this vector,
* {@code false} otherwise.
* @see #hashCode
*/
@Override
public synchronized boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof List) {
List<?> list = (List<?>) object;
if (list.size() != elementCount) {
return false;
}
int index = 0;
Iterator<?> it = list.iterator();
while (it.hasNext()) {
Object e1 = elementData[index++], e2 = it.next();
if (!(e1 == null ? e2 == null : e1.equals(e2))) {
return false;
}
}
return true;
}
return false;
}
/**
* Returns the first element in this vector.
*
* @return the element at the first position.
* @throws NoSuchElementException
* if this vector is empty.
* @see #elementAt
* @see #lastElement
* @see #size
*/
@SuppressWarnings("unchecked")
public synchronized E firstElement() {
if (elementCount > 0) {
return (E) elementData[0];
}
throw new NoSuchElementException();
}
/**
* Returns the element at the specified location in this vector.
*
* @param location
* the index of the element to return in this vector.
* @return the element at the specified location.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #size
*/
@Override
public E get(int location) {
return elementAt(location);
}
private void grow(int newCapacity) {
E[] newData = newElementArray(newCapacity);
// Assumes elementCount is <= newCapacity
// assert elementCount <= newCapacity;
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
}
/**
* JIT optimization
*/
private void growByOne() {
int adding = 0;
if (capacityIncrement <= 0) {
if ((adding = elementData.length) == 0) {
adding = 1;
}
} else {
adding = capacityIncrement;
}
E[] newData = newElementArray(elementData.length + adding);
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
}
private void growBy(int required) {
int adding = 0;
if (capacityIncrement <= 0) {
if ((adding = elementData.length) == 0) {
adding = required;
}
while (adding < required) {
adding += adding;
}
} else {
adding = (required / capacityIncrement) * capacityIncrement;
if (adding < required) {
adding += capacityIncrement;
}
}
E[] newData = newElementArray(elementData.length + adding);
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
}
/**
* Returns an integer hash code for the receiver. Objects which are equal
* return the same value for this method.
*
* @return the receiver's hash.
* @see #equals
*/
@Override
public synchronized int hashCode() {
int result = 1;
for (int i = 0; i < elementCount; i++) {
result = (31 * result)
+ (elementData[i] == null ? 0 : elementData[i].hashCode());
}
return result;
}
/**
* Searches in this vector for the index of the specified object. The search
* for the object starts at the beginning and moves towards the end of this
* vector.
*
* @param object
* the object to find in this vector.
* @return the index in this vector of the specified element, -1 if the
* element isn't found.
* @see #contains
* @see #lastIndexOf(Object)
* @see #lastIndexOf(Object, int)
*/
@Override
public int indexOf(Object object) {
return indexOf(object, 0);
}
/**
* Searches in this vector for the index of the specified object. The search
* for the object starts at the specified location and moves towards the end
* of this vector.
*
* @param object
* the object to find in this vector.
* @param location
* the index at which to start searching.
* @return the index in this vector of the specified element, -1 if the
* element isn't found.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0}.
* @see #contains
* @see #lastIndexOf(Object)
* @see #lastIndexOf(Object, int)
*/
public synchronized int indexOf(Object object, int location) {
if (object != null) {
for (int i = location; i < elementCount; i++) {
if (object.equals(elementData[i])) {
return i;
}
}
} else {
for (int i = location; i < elementCount; i++) {
if (elementData[i] == null) {
return i;
}
}
}
return -1;
}
/**
* Inserts the specified object into this vector at the specified location.
* This object is inserted before any previous element at the specified
* location. All elements with an index equal or greater than
* {@code location} have their index increased by 1. If the location is
* equal to the size of this vector, the object is added at the end.
*
* @param object
* the object to insert in this vector.
* @param location
* the index at which to insert the element.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location > size()}.
* @see #addElement
* @see #size
*/
public synchronized void insertElementAt(E object, int location) {
if (location >= 0 && location <= elementCount) {
if (elementCount == elementData.length) {
growByOne();
}
int count = elementCount - location;
if (count > 0) {
System.arraycopy(elementData, location, elementData,
location + 1, count);
}
elementData[location] = object;
elementCount++;
modCount++;
} else {
throw arrayIndexOutOfBoundsException(location, elementCount);
}
}
/**
* Returns if this vector has no elements, a size of zero.
*
* @return {@code true} if this vector has no elements, {@code false}
* otherwise.
* @see #size
*/
@Override
public synchronized boolean isEmpty() {
return elementCount == 0;
}
/**
* Returns the last element in this vector.
*
* @return the element at the last position.
* @throws NoSuchElementException
* if this vector is empty.
* @see #elementAt
* @see #firstElement
* @see #size
*/
@SuppressWarnings("unchecked")
public synchronized E lastElement() {
try {
return (E) elementData[elementCount - 1];
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
/**
* Searches in this vector for the index of the specified object. The search
* for the object starts at the end and moves towards the start of this
* vector.
*
* @param object
* the object to find in this vector.
* @return the index in this vector of the specified element, -1 if the
* element isn't found.
* @see #contains
* @see #indexOf(Object)
* @see #indexOf(Object, int)
*/
@Override
public synchronized int lastIndexOf(Object object) {
return lastIndexOf(object, elementCount - 1);
}
/**
* Searches in this vector for the index of the specified object. The search
* for the object starts at the specified location and moves towards the
* start of this vector.
*
* @param object
* the object to find in this vector.
* @param location
* the index at which to start searching.
* @return the index in this vector of the specified element, -1 if the
* element isn't found.
* @throws ArrayIndexOutOfBoundsException
* if {@code location >= size()}.
* @see #contains
* @see #indexOf(Object)
* @see #indexOf(Object, int)
*/
public synchronized int lastIndexOf(Object object, int location) {
if (location < elementCount) {
if (object != null) {
for (int i = location; i >= 0; i--) {
if (object.equals(elementData[i])) {
return i;
}
}
} else {
for (int i = location; i >= 0; i--) {
if (elementData[i] == null) {
return i;
}
}
}
return -1;
}
throw arrayIndexOutOfBoundsException(location, elementCount);
}
/**
* Removes the object at the specified location from this vector. All
* elements with an index bigger than {@code location} have their index
* decreased by 1.
*
* @param location
* the index of the object to remove.
* @return the removed object.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
*/
@SuppressWarnings("unchecked")
@Override
public synchronized E remove(int location) {
if (location < elementCount) {
E result = (E) elementData[location];
elementCount--;
int size = elementCount - location;
if (size > 0) {
System.arraycopy(elementData, location + 1, elementData,
location, size);
}
elementData[elementCount] = null;
modCount++;
return result;
}
throw arrayIndexOutOfBoundsException(location, elementCount);
}
/**
* Removes the first occurrence, starting at the beginning and moving
* towards the end, of the specified object from this vector. All elements
* with an index bigger than the element that gets removed have their index
* decreased by 1.
*
* @param object
* the object to remove from this vector.
* @return {@code true} if the specified object was found, {@code false}
* otherwise.
* @see #removeAllElements
* @see #removeElementAt
* @see #size
*/
@Override
public boolean remove(Object object) {
return removeElement(object);
}
/**
* Removes all occurrences in this vector of each object in the specified
* Collection.
*
* @param collection
* the collection of objects to remove.
* @return {@code true} if this vector is modified, {@code false} otherwise.
* @see #remove(Object)
* @see #contains(Object)
*/
@Override
public synchronized boolean removeAll(Collection<?> collection) {
return super.removeAll(collection);
}
/**
* Removes all elements from this vector, leaving the size zero and the
* capacity unchanged.
*
* @see #isEmpty
* @see #size
*/
public synchronized void removeAllElements() {
for (int i = 0; i < elementCount; i++) {
elementData[i] = null;
}
modCount++;
elementCount = 0;
}
/**
* Removes the first occurrence, starting at the beginning and moving
* towards the end, of the specified object from this vector. All elements
* with an index bigger than the element that gets removed have their index
* decreased by 1.
*
* @param object
* the object to remove from this vector.
* @return {@code true} if the specified object was found, {@code false}
* otherwise.
* @see #removeAllElements
* @see #removeElementAt
* @see #size
*/
public synchronized boolean removeElement(Object object) {
int index;
if ((index = indexOf(object, 0)) == -1) {
return false;
}
removeElementAt(index);
return true;
}
/**
* Removes the element found at index position {@code location} from
* this {@code Vector}. All elements with an index bigger than
* {@code location} have their index decreased by 1.
*
* @param location
* the index of the element to remove.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #removeElement
* @see #removeAllElements
* @see #size
*/
public synchronized void removeElementAt(int location) {
if (location >= 0 && location < elementCount) {
elementCount--;
int size = elementCount - location;
if (size > 0) {
System.arraycopy(elementData, location + 1, elementData,
location, size);
}
elementData[elementCount] = null;
modCount++;
} else {
throw arrayIndexOutOfBoundsException(location, elementCount);
}
}
/**
* Removes the objects in the specified range from the start to the, but not
* including, end index. All elements with an index bigger than or equal to
* {@code end} have their index decreased by {@code end - start}.
*
* @param start
* the index at which to start removing.
* @param end
* the index one past the end of the range to remove.
* @throws IndexOutOfBoundsException
* if {@code start < 0, start > end} or
* {@code end > size()}.
*/
@Override
protected void removeRange(int start, int end) {
if (start >= 0 && start <= end && end <= elementCount) {
if (start == end) {
return;
}
if (end != elementCount) {
System.arraycopy(elementData, end, elementData, start,
elementCount - end);
int newCount = elementCount - (end - start);
Arrays.fill(elementData, newCount, elementCount, null);
elementCount = newCount;
} else {
Arrays.fill(elementData, start, elementCount, null);
elementCount = start;
}
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
/**
* Removes all objects from this vector that are not contained in the
* specified collection.
*
* @param collection
* the collection of objects to retain.
* @return {@code true} if this vector is modified, {@code false} otherwise.
* @see #remove(Object)
*/
@Override
public synchronized boolean retainAll(Collection<?> collection) {
return super.retainAll(collection);
}
/**
* Replaces the element at the specified location in this vector with the
* specified object.
*
* @param location
* the index at which to put the specified object.
* @param object
* the object to add to this vector.
* @return the previous element at the location.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #size
*/
@SuppressWarnings("unchecked")
@Override
public synchronized E set(int location, E object) {
if (location < elementCount) {
E result = (E) elementData[location];
elementData[location] = object;
return result;
}
throw arrayIndexOutOfBoundsException(location, elementCount);
}
/**
* Replaces the element at the specified location in this vector with the
* specified object.
*
* @param object
* the object to add to this vector.
* @param location
* the index at which to put the specified object.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #size
*/
public synchronized void setElementAt(E object, int location) {
if (location < elementCount) {
elementData[location] = object;
} else {
throw arrayIndexOutOfBoundsException(location, elementCount);
}
}
/**
* This method was extracted to encourage VM to inline callers.
* TODO: when we have a VM that can actually inline, move the test in here too!
*/
private static ArrayIndexOutOfBoundsException arrayIndexOutOfBoundsException(int index, int size) {
throw new ArrayIndexOutOfBoundsException(size, index);
}
/**
* Sets the size of this vector to the specified size. If there are more
* than length elements in this vector, the elements at end are lost. If
* there are less than length elements in the vector, the additional
* elements contain null.
*
* @param length
* the new size of this vector.
* @see #size
*/
public synchronized void setSize(int length) {
if (length == elementCount) {
return;
}
ensureCapacity(length);
if (elementCount > length) {
Arrays.fill(elementData, length, elementCount, null);
}
elementCount = length;
modCount++;
}
/**
* Returns the number of elements in this vector.
*
* @return the number of elements in this vector.
* @see #elementCount
* @see #lastElement
*/
@Override
public synchronized int size() {
return elementCount;
}
/**
* Returns a List of the specified portion of this vector from the start
* index to one less than the end index. The returned List is backed by this
* vector so changes to one are reflected by the other.
*
* @param start
* the index at which to start the sublist.
* @param end
* the index one past the end of the sublist.
* @return a List of a portion of this vector.
* @throws IndexOutOfBoundsException
* if {@code start < 0} or {@code end > size()}.
* @throws IllegalArgumentException
* if {@code start > end}.
*/
@Override
public synchronized List<E> subList(int start, int end) {
return new Collections.SynchronizedRandomAccessList<E>(super.subList(
start, end), this);
}
/**
* Returns a new array containing all elements contained in this vector.
*
* @return an array of the elements from this vector.
*/
@Override
public synchronized Object[] toArray() {
Object[] result = new Object[elementCount];
System.arraycopy(elementData, 0, result, 0, elementCount);
return result;
}
/**
* Returns an array containing all elements contained in this vector. If the
* specified array is large enough to hold the elements, the specified array
* is used, otherwise an array of the same type is created. If the specified
* array is used and is larger than this vector, the array element following
* the collection elements is set to null.
*
* @param contents
* the array to fill.
* @return an array of the elements from this vector.
* @throws ArrayStoreException
* if the type of an element in this vector cannot be
* stored in the type of the specified array.
*/
@Override
@SuppressWarnings("unchecked")
public synchronized <T> T[] toArray(T[] contents) {
if (elementCount > contents.length) {
Class<?> ct = contents.getClass().getComponentType();
contents = (T[]) Array.newInstance(ct, elementCount);
}
System.arraycopy(elementData, 0, contents, 0, elementCount);
if (elementCount < contents.length) {
contents[elementCount] = null;
}
return contents;
}
/**
* Returns the string representation of this vector.
*
* @return the string representation of this vector.
* @see #elements
*/
@Override
public synchronized String toString() {
if (elementCount == 0) {
return "[]";
}
int length = elementCount - 1;
StringBuilder buffer = new StringBuilder(elementCount * 16);
buffer.append('[');
for (int i = 0; i < length; i++) {
if (elementData[i] == this) {
buffer.append("(this Collection)");
} else {
buffer.append(elementData[i]);
}
buffer.append(", ");
}
if (elementData[length] == this) {
buffer.append("(this Collection)");
} else {
buffer.append(elementData[length]);
}
buffer.append(']');
return buffer.toString();
}
/**
* Sets the capacity of this vector to be the same as the size.
*
* @see #capacity
* @see #ensureCapacity
* @see #size
*/
public synchronized void trimToSize() {
if (elementData.length != elementCount) {
grow(elementCount);
}
}
private synchronized void writeObject(ObjectOutputStream stream)
throws IOException {
stream.defaultWriteObject();
}
}
~~~
Java源码之ArrayList
最后更新于：2022-04-01 09:37:44
**Java源码之ArrayList**
转载请注明出处：[http://blog.csdn.net/itismelzp/article/details/50371326](http://blog.csdn.net/itismelzp/article/details/50371326)
# 一、ArrayList概述
ArrayList就是动态数组，用MSDN中的说法，就是Array的复杂版本，它提供了动态的增加和减少元素，实现了ICollection和IList接口，灵活的设置数组的大小等好处。
ArrayList位于API文档的java.util.ArrayList<E>。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）
# 二、源码
### 1.头文件
~~~
package java.util;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Array;
import libcore.util.EmptyArray;
~~~
### 2.继承与实现关系
~~~
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
~~~
### 3.属性
~~~
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
* 空对象数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默认大小的空对象数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 数据存放数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 包括元素个数
*/
private int size;
~~~
### 4.构造函数（共3个）
~~~
/**
* 构造方法一：
* 用指定容量构造
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) { // 非法容量
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 构造方法二：
* 用默认默认空数组构造
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 构造方法三：
* 用指定集合c构造
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// 将c中的元素复制到elementData
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// c是空的，用空数组对象构造
this.elementData = EMPTY_ELEMENTDATA;
}
}
~~~
### 5.方法
### (1) add添加（插入）方法：
~~~
/**
* 指定的元素e添加到尾部
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // size+1，如果容量不够会进行扩容
elementData[size++] = e; // 加到未尾
return true;
}
/**
* 在指定的位置插入元素
*/
public void add(int index, E element) {
rangeCheckForAdd(index); // 检查插入位置合法性
ensureCapacityInternal(size + 1); // size+1，如果容量不够会进行扩容
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 将index后的数据后移
elementData[index] = element;
size++;
}
~~~
### (2) 列表 -> 数组toArray方法
~~~
/**
* 将列表转化为数组，并将你数组返回
*
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
~~~
### (3) 扩容策略
add方法添加元素时如果容量不够时，会调用grow方法进行扩容，ArrayList的扩容策略是，
新容量扩大为原来的**1.5倍**。
~~~
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 容量不足
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 扩容方法
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // （1+0.5）倍
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);
}
~~~
其他方法其实都比较简单，这里不再列举。
下面是ArrayList的源码：
~~~
/*
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
/**
* Resizable-array implementation of the <tt>List</tt> interface. Implements
* all optional list operations, and permits all elements, including
* <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
* this class provides methods to manipulate the size of the array that is
* used internally to store the list. (This class is roughly equivalent to
* <tt>Vector</tt>, except that it is unsynchronized.)
*
* <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
* <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
* time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
* that is, adding n elements requires O(n) time. All of the other operations
* run in linear time (roughly speaking). The constant factor is low compared
* to that for the <tt>LinkedList</tt> implementation.
*
* <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
* the size of the array used to store the elements in the list. It is always
* at least as large as the list size. As elements are added to an ArrayList,
* its capacity grows automatically. The details of the growth policy are not
* specified beyond the fact that adding an element has constant amortized
* time cost.
*
* <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
* before adding a large number of elements using the <tt>ensureCapacity</tt>
* operation. This may reduce the amount of incremental reallocation.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access an <tt>ArrayList</tt> instance concurrently,
* and at least one of the threads modifies the list structurally, it
* <i>must</i> be synchronized externally. (A structural modification is
* any operation that adds or deletes one or more elements, or explicitly
* resizes the backing array; merely setting the value of an element is not
* a structural modification.) This is typically accomplished by
* synchronizing on some object that naturally encapsulates the list.
*
* If no such object exists, the list should be "wrapped" using the
* {@link Collections#synchronizedList Collections.synchronizedList}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the list:<pre>
* List list = Collections.synchronizedList(new ArrayList(...));</pre>
*
* <p><a name="fail-fast">
* The iterators returned by this class's {@link #iterator() iterator} and
* {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
* if the list is structurally modified at any time after the iterator is
* created, in any way except through the iterator's own
* {@link ListIterator#remove() remove} or
* {@link ListIterator#add(Object) add} methods, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of
* concurrent modification, the iterator fails quickly and cleanly, rather
* than risking arbitrary, non-deterministic behavior at an undetermined
* time in the future.
*
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @author Josh Bloch
* @author Neal Gafter
* @see Collection
* @see List
* @see LinkedList
* @see Vector
* @since 1.2
*/
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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;
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}
/**
* Returns <tt>true</tt> if this list contains no elements.
*
* @return <tt>true</tt> if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)
*
* @return a clone of this <tt>ArrayList</tt> instance
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
/**
* Returns an array containing all of the elements in this list
* in proper sequence (from first to last element).
*
* <p>The returned array will be "safe" in that no references to it are
* maintained by this list. (In other words, this method must allocate
* a new array). The caller is thus free to modify the returned array.
*
* <p>This method acts as bridge between array-based and collection-based
* APIs.
*
* @return an array containing all of the elements in this list in
* proper sequence
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* Returns an array containing all of the elements in this list in proper
* sequence (from first to last element); the runtime type of the returned
* array is that of the specified array. If the list fits in the
* specified array, it is returned therein. Otherwise, a new array is
* allocated with the runtime type of the specified array and the size of
* this list.
*
* <p>If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
* <tt>null</tt>. (This is useful in determining the length of the
* list <i>only</i> if the caller knows that the list does not contain
* any null elements.)
*
* @param a the array into which the elements of the list are to
* be stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose.
* @return an array containing the elements of the list
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this list
* @throws NullPointerException if the specified array is null
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
/**
* Retains only the elements in this list that are contained in the
* specified collection. In other words, removes from this list all
* of its elements that are not contained in the specified collection.
*
* @param c collection containing elements to be retained in this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
/**
* Save the state of the <tt>ArrayList</tt> instance to a stream (that
* is, serialize it).
*
* @serialData The length of the array backing the <tt>ArrayList</tt>
* instance is emitted (int), followed by all of its elements
* (each an <tt>Object</tt>) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
/**
* Returns a list iterator over the elements in this list (in proper
* sequence), starting at the specified position in the list.
* The specified index indicates the first element that would be
* returned by an initial call to {@link ListIterator#next next}.
* An initial call to {@link ListIterator#previous previous} would
* return the element with the specified index minus one.
*
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
* Returns a list iterator over the elements in this list (in proper
* sequence).
*
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @see #listIterator(int)
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* An optimized version of AbstractList.ListItr
*/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
/**
* Returns a view of the portion of this list between the specified
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If
* {@code fromIndex} and {@code toIndex} are equal, the returned list is
* empty.) The returned list is backed by this list, so non-structural
* changes in the returned list are reflected in this list, and vice-versa.
* The returned list supports all of the optional list operations.
*
* <p>This method eliminates the need for explicit range operations (of
* the sort that commonly exist for arrays). Any operation that expects
* a list can be used as a range operation by passing a subList view
* instead of a whole list. For example, the following idiom
* removes a range of elements from a list:
* <pre>
* list.subList(from, to).clear();
* </pre>
* Similar idioms may be constructed for {@link #indexOf(Object)} and
* {@link #lastIndexOf(Object)}, and all of the algorithms in the
* {@link Collections} class can be applied to a subList.
*
* <p>The semantics of the list returned by this method become undefined if
* the backing list (i.e., this list) is <i>structurally modified</i> in
* any way other than via the returned list. (Structural modifications are
* those that change the size of this list, or otherwise perturb it in such
* a fashion that iterations in progress may yield incorrect results.)
*
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public int size() {
checkForComodification();
return this.size;
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+this.size;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
}
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* list.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
* {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
* Overriding implementations should document the reporting of additional
* characteristic values.
*
* @return a {@code Spliterator} over the elements in this list
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
/** Index-based split-by-two, lazily initialized Spliterator */
static final class ArrayListSpliterator<E> implements Spliterator<E> {
/*
* If ArrayLists were immutable, or structurally immutable (no
* adds, removes, etc), we could implement their spliterators
* with Arrays.spliterator. Instead we detect as much
* interference during traversal as practical without
* sacrificing much performance. We rely primarily on
* modCounts. These are not guaranteed to detect concurrency
* violations, and are sometimes overly conservative about
* within-thread interference, but detect enough problems to
* be worthwhile in practice. To carry this out, we (1) lazily
* initialize fence and expectedModCount until the latest
* point that we need to commit to the state we are checking
* against; thus improving precision. (This doesn't apply to
* SubLists, that create spliterators with current non-lazy
* values). (2) We perform only a single
* ConcurrentModificationException check at the end of forEach
* (the most performance-sensitive method). When using forEach
* (as opposed to iterators), we can normally only detect
* interference after actions, not before. Further
* CME-triggering checks apply to all other possible
* violations of assumptions for example null or too-small
* elementData array given its size(), that could only have
* occurred due to interference. This allows the inner loop
* of forEach to run without any further checks, and
* simplifies lambda-resolution. While this does entail a
* number of checks, note that in the common case of
* list.stream().forEach(a), no checks or other computation
* occur anywhere other than inside forEach itself. The other
* less-often-used methods cannot take advantage of most of
* these streamlinings.
*/
private final ArrayList<E> list;
private int index; // current index, modified on advance/split
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
/** Create new spliterator covering the given range */
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; // OK if null unless traversed
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
}
private int getFence() { // initialize fence to size on first use
int hi; // (a specialized variant appears in method forEach)
ArrayList<E> lst;
if ((hi = fence) < 0) {
if ((lst = list) == null)
hi = fence = 0;
else {
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
}
public ArrayListSpliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
}
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc; // hoist accesses and checks from loop
ArrayList<E> lst; Object[] a;
if (action == null)
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;
}
else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
}
public long estimateSize() {
return (long) (getFence() - index);
}
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
}
~~~
前言
最后更新于：2022-04-01 09:37:42
> 原文出处：[Java源码解析](http://blog.csdn.net/column/details/java-source-study.html)
作者：[itismelzp](http://blog.csdn.net/itismelzp)
**本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！**
# Java源码解析
> 解析JDK1.8中集合及其它一些常用类的源码，与大家一起探讨学习。