【Java】常用集合类框架
Collection 类关系图
容器，就是可以容纳 Java 对象的容器
优点：
- 降低编程难度
- 提高程序性能
- 提高 API 之间的互操作性
- 降低学习难度
- 降低设计和实现相关 API 的难度
- 增加程序的可复用性
一、Collection
容器主要包括 Collection 和 Map 两种 ，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。
Set
TreeSet
基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
HashSet
基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
LinkedHashSet
具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。
List
ArrayList
基于动态数组实现，支持随机访问。
Vector
和 ArrayList 类似，但它是线程安全的。
LinkedList
基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
Queue
LinkedList
可以用它来实现双向队列。
PriorityQueue
基于堆结构实现，可以用它来实现优先队列。
二、Map
TreeMap
基于红黑树实现。
HashMap
基于哈希表实现。
HashTable
和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
LinkedHashMap
使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用(LRU)顺序。
三、Collection——ArrayList
概述
-
实现了list接口、顺序容器
-
元素存放的数据和与放进去的顺序相同
-
允许有 null
-
底层通过数组实现（Object数组）、可以容纳任何类型
-
有一定的 capacity，容量不足的时候会自动扩大底层数组的大小
-
方法
-
- size(), isEmpty(), get(), set()方法均能在常数时间内完成
- add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比
- 其余方法大都是线性时间
-
为了实现效率 ArrayList 没有实现同步 synchronized
-
- 如果需要多个线程进行访问，用户可以手动同步，也可以用 Vector 来代替
ArrayList的实现
底层数据结构
/**
* 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
//关键字表示这个成员变量不会被序列化
//即在对象序列化时，它不会被写入到输出流中。这样做是为了节省空间和提高性能。
/**1
* 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.
这个构造函数用于创建一个初始容量为10的空列表。
它使用了一个预定义的空Object数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
*/
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
这个构造函数用于创建一个包含指定集合元素的列表。
它首先将集合转换为一个Object数组，然后检查数组的类型是否为Object[]。
如果不是，它会创建一个新的Object[]数组并复制元素。
如果集合为空，它将使用一个空的Object数组EMPTY_ELEMENTDATA。
*/
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;
}
}
自动扩容
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度
如果超出，数组将会进行扩容，以满足添加数据的需求。
数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。
在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。
这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造 ArrayList 实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity 方法来手动增加 ArrayList 实例的容量。
/**
* 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)
/**
这个方法首先检查当前数组是否为默认的空数组，如果不是，则将最小扩展容量设置为 0；
如果是，则将其设置为默认容量。然后，如果指定的最小容量大于最小扩展容量
就调用 ensureExplicitCapacity(int minCapacity) 方法来确保有足够的空间容纳新的元素。
*/
// 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++;
// 表示ArrayList结构修改次数的计数器
// 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
*/
/**
根据当前数组的长度计算新的容量，新容量等于旧容量加上旧容量的一半。
然后，它会检查新容量是否小于所需的最小容量，如果是，则将新容量设置为所需的最小容量。
接下来，它会检查新容量是否超过了最大数组大小
（MAX_ARRAY_SIZE 如果超过了，就调用 hugeCapacity(int minCapacity)方法来确定合适的新容量。
最后，它会使用 Arrays.copyOf() 方法将旧数组的内容复制到新的更大的数组中。
*/
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);
}
/**
用于处理特殊情况，当所需的最小容量超过最大数组大小时，它会抛出一个OutOfMemoryError异常，
或者返回Integer.MAX_VALUE或MAX_ARRAY_SIZE，取决于所需的最小容量是否大于MAX_ARRAY_SIZE。
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add()、addAll()
和 C++ 的 vector 不一样，ArrayList 没有 push_back() 方法，，对应的方法是 add(E e) , ArrayList 也没有insert()方法，对应的方法是 add(int index, E e)。
这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。
/**
* 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) {
// 这行代码检查底层数组（elementData）是否有足够的容量来存储一个以上的元素。
//如果没有，它会增大数组的容量。变量size代表当前列表中的元素数量。
ensureCapacityInternal(size + 1); // Increments modCount!!
// 这行代码将新元素e添加到数组的末尾，然后将size变量递增1，以反映新元素的添加
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++;
}
addAll()
这个方法能够一次添加多个元素
根据位置不同有两个版本：
- 在末尾添加
addAll(Collection<? extends E> c) - 在指定位置添加
addAll(int index, Collection<? extends E> c)
跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。 addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。
/**
* 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;
}
set()
直接对数组对应的位置进行赋值即可
public E set(int index, E element) {
rangeCheck(index);//下标越界检查
E oldValue = elementData(index);
elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
return oldValue;
}
get()
注意点是由于底层数组是Object[]，得到元素之后需要进行类型转换
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];//注意类型转换
}
remove()
remove()方法也有两个版本
一个是remove(int index)删除指定位置的元素
另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。
删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置
赋null值。
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; //清除该位置的引用，让GC起作用
return oldValue;
}
关于Java GC这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。
trimToSize()
将底层数组的容量调整为当前列表保存的实际元素的大小
/**
* 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);
}
}
indexOf()、lastIndexOf()
获取元素第一次出现的index
/**
* 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;
}
获取元素最后一次出现的index
/**
* 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;
}
Fail-Fast机制
ArrayList 也采用了快速失败的机制，通过记录 modCount 参数来实现。
在面对并发的修改的时候，迭代器很快就会完全失败，而不是冒着在将来某个不确定的时间发生任意不确定行为的风险。
四、Collection——HashSet & HashMap
前者只是对后者做了一层简单的包装 ，也即是说 HashSet 中有一个 HashMap（适配器模式）
Java7 - HashMap
实现了 Map 接口，就是允许放入 key 为 null 的元素，也允许插入 value 为 null 的元素。
除该类未实现同步之外，其余跟 Hashtable 大致相同；
跟 TreeMap 不同的是，该容器不保证元素顺序。
根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同。
根据对冲突的处理方式不同，哈希有两种实现方式：
- 开放地址方式
- 冲突链表方式
-
在对 HashMap 进行迭代的时候，通常需要遍历整个 table 以及后面跟的冲突链表，所以对于迭代比较频繁的场景，是不适于将HashMap的初始大小设得太大。
-
影响 HashMap 性能的的两个参数：
-
inital capacity初始容量：初定了table的大小load factor负载系数 用来指定自动扩容的临界值
-
当
entry的数量超过capacity * load_factor的时候，容器会自动扩容并且重新哈希 -
对于插入元素比较多的场景，将初始容量设大是可以减少重新哈希的次数
-
将对象放到 HashMap 或者 HashSet 中的时候，注意：
hashcode()和equals -
hashcode():决定了对象会被放在哪个bucket中equals():当多个对象的哈希值冲突的时候，决定这些对象是否是同一个对象
-
所以如果要将自定义对象放到
HashMap或者HashSet中，需要@Overridehashcode()和equals()方法。
get()
get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.getValue()。因此getEntry()是算法的核心。
算法思想是首先通过hash()函数得到对应bucket的下标，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否要找到那个entry。
上图中hash(k)&(table.length-1)等价于hash(k)%table.length，原因是HashMap要求table.length必须是2的指数，因此table.length-1就是二进制低位全是1，跟hash(k)相与会将哈希值的高位全抹掉，剩下的就是余数了。
//getEntry()方法
final Entry<K,V> getEntry(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[hash&(table.length-1)];//得到冲突链表
e != null; e = e.next) {//依次遍历冲突链表中的每个entry
Object k;
//依据equals()方法判断是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
put()
put(K key, V value)方法是将指定的key, value对添加到map里。
该方法首先会对map做一次查找，看是否包含该元组。
- 如果已经包含则直接返回，查找过程类似于
getEntry()方法； - 如果没有找到，则会通过
addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry，插入方式为头插法。
//addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//自动扩容，并重新哈希
hash = (null != key) ? hash(key) : 0;
bucketIndex = hash & (table.length-1);//hash%table.length
}
//在冲突链表头部插入新的entry
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
remove()
remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑在removeEntryForKey(Object key)里面实现的。
removeEntryForKey(Object key)方法会首先找到key值对应的entry，然后删除该entry（修改链表的相应应用）。
查找过程和getEntry()过程类似.
//removeEntryForKey()
final Entry<K,V> removeEntryForKey(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);//hash&(table.length-1)
Entry<K,V> prev = table[i];//得到冲突链表
Entry<K,V> e = prev;
while (e != null) {//遍历冲突链表
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry
modCount++; size--;
if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry
else prev.next = next;
return e;
}
prev = e; e = next;
}
return e;
}
Java8 - HashMap
修改点就在于：
- 利用了红黑树
数组+链表+红黑树
在 Java7 的 HashMap 中，查找的时候，根据 hash 值我们可以快速定位到数组的具体下标，但是之后，就需要顺着链表一个个比较下去才可以找到我们所需要的，时间复杂度取决于链表的长度O(n)
但是在 Java8 里面，为了降低这部分的开销，当链表的元素达到 8 的时候，就会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为O(logN)
Java8 的源码可读性较差，但是精简。
在 Java7 中使用 Entry 来代表每个 HashMap 中的数据节点，而 Java8 中使用的是 Node，这基本上是没有区别的。基本都是 key value hash next 这四个属性。
不过 Node 只能适用于链表的情况，红黑树的情况就需要 TreeNode
我们根据数组元素中，第一个节点数据类型是Node还是TreeNode来判断该位置下是链表还是红黑树的。
put过程分析
Java7 是先扩容后插值，Java8 是先插值后扩容，无伤大雅
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 第四个参数 onlyIfAbsent 如果是 true，那么只有在不存在该 key 时才会进行 put 操作
// 第五个参数 evict 我们这里不关心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次 put 值的时候，会触发下面的 resize()，类似 java7 的第一次 put 也要初始化数组长度
// 第一次 resize 和后续的扩容有些不一样，因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量
// 如果数组 table 为空或长度为 0，则进行初始化或扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找到具体的数组下标，如果此位置没有值，那么直接初始化一下 Node 并放置在这个位置就可以了
// 计算插入位置的索引 i
if ((p = tab[i = (n - 1) & hash]) == null)
// 若索引 i 为空，则直接插入节点
tab[i] = newNode(hash, key, value, null);
else {// 数组该位置有数据
Node<K,V> e;
K k;
// 首先，判断该位置的第一个数据和我们要插入的数据，key 是不是"相等"，如果是，取出这个节点
// 如果位置上已经有节点
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) {
// 插入到链表的最后面(Java7 是插入到链表的最前面)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 8 个
// 会触发下面的 treeifyBin，也就是将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在该链表中找到了"相等"的 key(== 或 equals)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node
break;
p = e;
}
}
// e!=null 说明存在旧值的key与要插入的key"相等"
// 对于我们分析的put操作，下面这个 if 其实就是进行 "值覆盖"，然后返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
数组扩容
resize()方法用于初始化数组或数组扩容，每次扩容之后，容量为原来的两倍，并且进行数据迁移
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; // double threshold
}
else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的时候
newCap = oldThr;
else {// 对应使用 new HashMap() 初始化后，第一次 put 的时候
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;
// 用新的数组大小初始化新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 如果是初始化数组，到这里就结束了，返回 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 {
// 这块是处理链表的情况，
// 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序
// loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表，代码还是比较简单的
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;
// 第二条链表的新的位置是 j + oldCap，这个很好理解
// 也就是将第二条链表插入到新数组的对应位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get过程分析
- 计算 key 的 hash 值，根据 hash 值找到对应数组的下标
hash & (length - 1) - 判断数组该位置处的元素是否就是我们要找的，如果不是，走第三步
- 判断该元素的类型是否是 TreeNode，如果是，就用红黑树的方法来取数据，不是的话就走第四步
- 遍历链表，直到找到相等的key（== equals）
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
// 判断第一个节点是不是就是需要的
if (first.hash == hash && // always check first node
((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;
}
HashSet
HashSet 是 HashMap 的简单包装，对 HashSet 的使用基本上都会调用到 HashMap 的函数。
原文地址：https://blog.csdn.net/m0_73075027/article/details/140570032
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！