Collection的上层是Iterable接口，意味着Collection所有的子类都可以使用迭代器去访问元素，Collection还分为Set和List接口，Set接口下的实现子类都是不允许存在重复元素的，而List则是可以允许存在重复元素。Map这边属于双列集合(key - value)，每个key对应唯一的一个value值。
List接口实现的子类允许元素重复,List接口下的常用方法如下：
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
void clear();
boolean equals(Object o);
int hashCode();
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
ArrayList本质上就是数组，它是List接口中最常用的一个实现子类
private static final int DEFAULT_CAPACITY = 10; //ArrayList的初始化大小
private static final Object[] EMPTY_ELEMENTDATA = {};//调用有参构造器且初始化大小为0时，elementData会引用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //调用无参构造器时，elementData会引用
transient Object[] elementData;// ArrayList真正存取数据的数组(transient防止被序列化)
private int size; //ArrayList而存入元素的个数
public ArrayList(int initialCapacity) { //ArrayList的有参构造器
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() { //ArrayList的无参构造器
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) { //可以将Collection的实现类集合进行初始化
// 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;
}
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 此方法会计算添加一个元素后的长度
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//内部cal方法是计算需要的长度
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //判断elementData是否是无参构造器创建的（只判断一次）
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;//返回添加元素后的长度
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//用来记录ArrayList的修改次数
if (minCapacity - elementData.length > 0)
grow(minCapacity);//ArrayList中真正的扩容方法
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //ArrayList的1.5倍扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity); //数组元素的拷贝会调用底层native方法
}
与ArrayList一样，Vector的底层也是基于数组实现的，不过Vector是属于线程安全的。
protected Object[] elementData;// Vector用来存取元素的数组
protected int elementCount;// 记录Vector集合中有效的元素数量
protected int capacityIncrement; //扩容增加量
public Vector(int initialCapacity, int capacityIncrement) { //指定初始化容量和 capacityIncrement
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) { //指定初始化容量和 capacityIncrement为0
this(initialCapacity, 0);
}
public Vector() { //无参构造器，初始化容量默认为10
this(10);
}
public Vector(Collection<? extends E> c) { //指定实现了Collection接口的子类作为参数
elementData = c.toArray();
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
private void grow(int minCapacity) { //Vector的扩容方法
int oldCapacity = elementData.length;
//这里需要注意，如果再初始化阶段没有指定capacityIncrement大小，默认增长是原来的两倍，否则按capacityIncrement增长
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Vector和ArrayList非常类似，Vector是线程安全的，默认扩容机制是2倍且可以自定义扩容容量
LinkedList的底层实现了双向链表和双端队列的特点
transient int size = 0;//LinkedList的长度
transient Node<E> first;//LinkedList的头结点
transient Node<E> last;//LinkedList的尾结点
private static class Node<E> { //是个双向链表
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
public LinkedList() { //无参构造器
}
public LinkedList(Collection<? extends E> c) { //指定Collection的子类作为初始化
this();//这里还是会调用无参构造器
addAll(c);//addAll方法会把集合c的元素采用尾插法一一插入到LinkedList后面
}
private void linkFirst(E e) { //头插法
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
void linkLast(E e) { //尾插法
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) { //remove方法删除结点顺序遍历，时间复杂度O(N)
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
LinkedList是双链表结构，它的随机查询能力是要比基于数组结构的集合稍差，但是在增加和删除操作中，LinkedList是要比基于数组结构的集合效率高
Set接口下实现的子类，不能存取重复的元素,Set接口下的常用方法如下：
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
可以看出Set接口中没有带索引的方法
HashSet的底层本质上就是HashMap,不过HashSet只存取key值，value用来存放一个Object对象
//HashSet中大部分代码都是用HashMap中的代码，仅仅写了个clone和writeObject 和 readObject
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
@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);
}
}
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);
}
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);
// Constructing the backing map will lazily create an array when the first element is
// added, so check it before construction. Call HashMap.tableSizeFor to compute the
// actual allocation size. Check Map.Entry[].class since it's the nearest public type to
// what is actually created.
SharedSecrets.getJavaOISAccess()
.checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(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);
}
}
//见后面的HashMap中put方法
TreeSet的底层数据结构是红黑树，同HashSet一样，底层实际上是TreeMap,它的特点是元素具有唯一性并且是有序的，并且默认情况下是升序的，并且key值不能为空
private transient NavigableMap<E,Object> m;//暂时先放这，后面再说
private static final Object PRESENT = new Object();//每个value存取的就是PRESENT
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() { //无参构造器
this(new TreeMap<E,Object>());//本质上就是TreeMap
}
public TreeSet(Comparator<? super E> comparator) { //带比较器的构造器
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) { //Collection的子类的构造器
this();
addAll(c);
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
//TreeMap中的put方法
public V put(K key, V value) {
Entry<K,V> t = root;//TreeMap里的根节点
if (t == null) { //根节点为空时添加方式
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) { //如果比较器为null(这里会默认按升序方式存放)
do {
parent = t;
cmp = cpr.compare(key, t.key);//内部自带的compare方法
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else { //比较器不为null
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);//这里compareTo方法是外部匿名内部类重写后的方法
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);//如果两个key相等相当于替换
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);//这个才是真正插入元素的方法（红黑树插入元素），前面只是在找位置
size++;
modCount++;
return null;
}
LinkedhashSet作为HashSet的子类，底层本质上是LinkedHashMap，底层维护了一个数组+双链表结构,基于这个特点使得LinkedHashSet能够保证添加元素的顺序和取出的顺序一致。
//由于底层是LinkedHashMap，所以源代码很少，只有以下构造器
public LinkedHashSet(int initialCapacity, float loadFactor) { //指定初始化大小和加载因子
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) { //指定初始化大小
super(initialCapacity, .75f, true);
}
public LinkedHashSet() { //无参构造器
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) { // 采用Collectiion的实现子类作为参数
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
这个后面总结LinkedHashMap会详细讲解
map接口是一种键值对的接口（key-value），可以通过键来获取值。
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void putAll(Map<? extends K, ? extends V> m);
void clear();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> { //Map中的Entry接口
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
boolean equals(Object o);
int hashCode();
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// ise thrown from function is not a cme.
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
}
HashMap可谓是Map接口中最具有代表的k-v结构，也可以说是整个集合结构中精华所在。
首先Entry是Map接口中的一个内部接口，Node内部类是一个单链表，是HashMap在table数组中存在每个元素的单个结点，然后Entry是LinkedhashMap中的内部类，TreeNode是HashMap中一个内部类，是红黑树结构。
transient Node<K,V>[] table; //注意上面内部类的继承关系，table数组中既可以存Node数组，也可以存Entry和TreeNode数据
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap中table的初始容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//table数组的最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认加载因子
static final int TREEIFY_THRESHOLD = 8;
// 树化条件1：table数组结点链表树化临界值（树化条件还需要table长度大于64）
static final int UNTREEIFY_THRESHOLD = 6;
// 当链表长度小于这个阈值，会进行树转成链表
static final int MIN_TREEIFY_CAPACITY = 64;
//树化条件2： table数组的结点必须大于64
transient Node<K,V>[] table;
//HashMap中存放数据的地方
transient Set<Map.Entry<K,V>> entrySet;
//entrySet 存放k-v键值对的地方
transient int size;
//记录table数组中存放的数据个数
transient int modCount;
//对map的修改次数
int threshold;
final float loadFactor;
//自定义加载因子
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);
}
public HashMap(int initialCapacity) { //指定初始化大小，默认加载因子为0.75
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() { //无参构造器
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) { //用map的子类进行初始化
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//计算key键hash值的方法(为了让高16位也参与运算，目的是减少哈希冲突)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//HashMap中真正的put方法 putval
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;//辅助变量
//table数组为null时或者长度为0，就会调用resize方法(长度默认为16)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//将key的hash值和table的数组长度进行&运算，为null就加进去
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { //不为null的情况
Node<K,V> e; K k;
//判断当前table数组索引位置的hash值和新插入值的hash值是否相等，或者内容是否相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//满足上述条件之一就记录下来
//这里判断下当前p指向的结点是否是红黑树结点，若是按红黑树的方式添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //以上两个条件都不满足的话，则可判断这个Node结点一定出现形成了链表(须要遍历查找)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//遍历完链表没有相同对象，就添加到链表后面
p.next = newNode(hash, key, value, null);
//添加后还需要判断是不是达到了树化条件
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
有个问题需要注意下：为什么resize()扩容时都是以2^n次方扩容，原因在哪？
因为Hashmap计算存储位置时，使用了(n - 1) & hash。只有当容量n为2的幂次方，n-1的二进制会全为1，位运算时可以充分散列，避免不必要的哈希冲突，所以扩容必须2倍就是为了维持容量始终为2的幂次方。
比如 初始大小为16 ：
二进制： 1 0 0 0 0
n-1 = 15 : 0 1 1 1 1
可以看见n-1的二进制位全1，用来充分散列，避免哈希冲突
public V get(Object key) { //get方法
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//真正获取元素的方法 getNode
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) { //判断table表和key的hash对应的索引位置是否为null
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) //判断table的结点是否相等
return first;
if ((e = first.next) != null) { //判断first.next后面是否有结点
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;
}
由于HashMap中存在很多的内部类，而这些内部类也提供了很多的遍历方式，比如根据key，和value来遍历，借用Collection接口的迭代器。要想弄清遍历方式，就要先分析内部类中的属性。
keySet方式是根据HashMap中的所有的key值，然后可以通过key来获取对应的value值。相信大家都会有个疑问，keySet遍历方式是如何去得到HashMap的key值？下面分析下底层源码。
public Set<K> keySet() {
Set<K> ks = keySet;//keySet是在AbstractMap中定义的 transient Set<K> keySet;
if (ks == null) {
ks = new KeySet(); //这里的构造器是KeySet类的构造器
keySet = ks;
}
return ks;
}
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }//迭代器方法
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
HashMap在调用keySet方式时，会调用内部类keySet中无参构造器，但是内部类keySet中无参构造器什么都没有做，其实最主要的是看上了内部类keySet中迭代器方法
public final Iterator<K> iterator() {
return new KeyIterator();
}
也就是说，keySet方法中的ks只是一个引用,再看看KeyIterator()是个什么东东
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
层层套娃。。，keyIterator也是HashMap中的一个内部类，同样无参构造器也啥也没干，目的就是想借用next()方法，追到nextNode()中可以看到源码如下：
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;//next是table的拷贝
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
可以看到最终还是在table表中拿的key值。
总结：keySet方式获取key值，主要是keySet方法里的keySet属性指向了内部类KeySet，调用了重写的iterator方法，然后又在 iterator方法中调用KeyIterator里面的next()方法，最后又在next方法中调用了nextNode（）方法去得到最终的key。（有亿点绕）
EntrySet方式和keySet方式类似：
public Set<Map.Entry<K,V>> entrySet() { //可以发现entrySet的泛型是Map接口中的内部接口Entry
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
这里就不一一分析了，不过有两个点需要主要，entrySet虽然它定义时是Map.Entry，但是里面实际上存取的是Entry接口的实现子类Node，还有就是getKey和getValue都是Map.Entry接口里的方法，或者TreeNode,如下图所示
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iHqfOHId-1625898247395)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20210709220354393.png)]](https://img-blog.csdnimg.cn/20210710143051964.png)
values方式是HashMap中一个方法，实现方式比较简单，它继承了Collection接口,并且得到的是整个HashMap中value值。
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
最后总结下，采用以上三种遍历方式，在进行foreach循环时，本质就是调用迭代器。
LinkedHashMap是HashMap的子类，和HashMap很相似，但是LinkedHashMap维护了一个双向链表的结构，可以使得添加的元素变得有序。
public LinkedHashMap(int initialCapacity, float loadFactor) { //指定初始化容量和加载因子
super(initialCapacity, loadFactor);//调用父类的构造器
accessOrder = false;
}
//其它不一一介绍了，都是调用父类的构造器进行初始化
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);
}
}
在table数组中存取的就是LinkedHashMap中Entry结点
总结：LinkedHashMap 就是双向链表和HashMap的结合体，实现上只是多了链表的操作，其它的地方和HashMap基本一样。
TreeMap的底层是红黑树结构，与HashMap不同的是，它可以自定义排序方式，即传入一个Comparator接口并重写compare方法。默认是升序。
private final Comparator<? super K> comparator;//比较器
private transient Entry<K,V> root;//TreeMap存放数据的地方
private transient int size = 0;//添加数据的数量
private transient int modCount = 0;//修改次数
public TreeMap() { //无参构造器
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) { //自定义比较器初始化方式
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) { //使用Map的实现类作为初始化
comparator = null;
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) { //使用带比较器的SortedMap 进行初始化
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) { //第一次加入的情况
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) { //比较器不为null
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); //替换value
} while (t != null);
}
else { //比较器为null
if (key == null)
throw new NullPointerException(); //TreeMap中key不能为空
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key; //默认为升序
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
TreeMap中的root保存的结点都是Entry类型
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; //key
V value;//value
Entry<K,V> left;//左结点
Entry<K,V> right;//右节点
Entry<K,V> parent;//根节点
boolean color = BLACK;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
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 valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
Hashtable是实现了Map接口并且实现了Dictionary抽象类，并且是线程安全的，key和value都不能为null（key不能为null在Dictionary规定的，value不能为空在Hashtable中规定的）。
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gTsHCMTi-1625898247397)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20210710130249953.png)]](https://img-blog.csdnimg.cn/20210710143211413.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODUzMg==,size_16,color_FFFFFF,t_70)
private transient Entry<?,?>[] table;//Hashtable存放数据的地方
private transient int count;//统计Hashtable中存放数据的总量
private int threshold;//扩容临界值
private float loadFactor;//加载因子
private transient int modCount = 0;//修改次数
public Hashtable(int initialCapacity, float loadFactor) { //指定table初始容量和加载因子
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) { //指定table初始容量，加载因子默认0.75
this(initialCapacity, 0.75f);
}
public Hashtable() { //无参构造器（table初始容量为11，加载因子0.75）
this(11, 0.75f);
}
public Hashtable(Map<? extends K, ? extends V> t) { //使用Map的实现子类作为初始化
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
//put方法
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;//0x7FFFFFFF是int类型最大值
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) { //判断有没有相同hash值和key值是否相同
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);//真正添加数据的方法
return null;
}
//addEntry方法
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) { //大于等于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++;
}
//rehash方法
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;
}
}
}