JDK 源码学习——集合，linux 软件架构
boolean hasNext()：这个方法是在遍历的时候，判断是否还有更多的元素
E next()： 返回下一个元素
default void remove()：这里涉及到了 jdk8 的特性，在接口定义中，将方法描述为 default-虚拟扩展方法，就可以在接口中进行默认实现，从而提高接口的扩展性，避免在接口扩展的时候，破坏原有的实现。
default void forEachRemaining(Consumer<? super E> action)：这个方面一般都用不到，不做具体描述。
collection
Collection 作为一个集合类的顶层接口，他没有直接的子类实现，而是通过实现它的子接口来实现集合容器。Collection 的特点是作为一个容器，他可以轻松的帮用户实现数据存储，动态扩容，还有方便的元素遍历和快速的增删改查等操作，这些特点都在接口定义的方法中一一体现出来，相比我们用 array 来存储数据方便不少。
Collection 的子接口主要是三大类分别是 List，Set 和 Queue。这三个接口各有特点。
list 是顺序存储的，并且可以重复，可以为空
Set 集合最大的特点是元素不能重复，所有元素都是唯一的存在。Set 集合不保证维护元素的顺序
Queue 顾名思义就是队列，队列最大的特点就是 FIFO 先进先出，与之对应的有栈 Stack 后进先出。
Map
和 Collection 一样，Map 也是集合容器的一个顶层接口。Map 是通过 key-value 方式存储数据，key 值都是唯一的，但 key 是否能为空，则要看他的不同子类的实现。我们可以把 Map 看成一个小型的数字字典，通过 key 值的方式存储数据性能非常快，比如他的子类 Hashmap，底层就是通过散列表来实现存储，他的时间复杂度是 O(1)。另一个典型的子类 Treemap 是基于红黑树实现的，时间复杂度为 O(log n)。以下将介绍部分方法。
HashSet
先说说 HashSet 的继承关系，HashSet 继承了 AbstractSet 抽象类并实现了 Set 接口，AbstractSet 的子类还包括 TreeSet，里面实现了两个类公共的一部分方法，后面也会略有介绍。
那么 HashSet 到底一个怎么样的存在呢?HashSet 顾名思义就是通过 Hash 表的方式存储数据，既然提到 hash，那么肯定少不了 HashMap，其实 HashSet 很聪明，他只需在内部维护了一个 HashMap 实例，将数据存储在了 map 中，并且集合元素不能重复。因此 HashSet 可以说是集合类中实现最简单的一个，他基本就是实现了 List 接口中定义的几个方法。
那么我想说 HashSet 和 HashMap 有什么区别呢？
1.HashMap 提供键值对的方式存储数据，而 HashSet 仅仅提供数据存储，并没有键值对应。他获取元素的方式也只能通过遍历的方式逐个获取
2.HashMap 在存入数据的时候是更加 key 值的 hash 值判断，而 HashSet 需要重写 hashCode 和 equals 两个方法，如果不重写则会调用默认的实现，用户在使用 HashSet 的时候要特别注意元素的 euqals 判断，有必要的话要重写一个，以免出现问题。
HashMap
HashMap 是 Map 的一个实现类，这个类很重要，是很多集合类的实现基础，底层用的就是他，比如前文中讲到的 HashSet，下文要讲到的 LinkedHashMap。我们可以将 HashMap 看成是一个小型的数字字典，他以 key-value 的方式保存数据，Key 全局唯一，并且 key 和 value 都允许为 null。
HashMap 底层是通过维护一个数据来保存元素。当创建 HashMap 实例的时候，会通过指定的数组大小以及负载因子等参数创建一个空的数组，当在容器中添加元素的时候，首先会通过 hash 算法求得 key 的 hash 值，再根据 hash 值确定元素在数组中对应的位置，最后将元素放入数组对应的位置。在添加元素的过程中会出现 hash 冲突问题，冲突处理的方法就是判断 key 值是否相同，如果相同则表明是同一个元素，替换 value 值。如果 key 值不同，则把当前元素添加到链表尾部。这里引出了一个概念，就是 HashMap 的数据结构其实是：hash 表+单向链表。通过链表的方式把所有冲突元素放在了数组的同一个位置。但是当链表过长的时候会影响 HashMap 的存取效率。因此我们在实际使用 HashMap 的时候就需要考虑到这个问题，那么该如何控制 hash 冲突的出现频率呢？HashMap 中有一个负载因子(loadFactor)的概念。容器中实际存储元素的 size = loadFactor * 数组长度，一旦容器元素超出了这个 size，HashMap 就会自动扩容，并对所有元素重新执行 hash 操作，调整位置。好了说了这么多，下面就开始介绍源码实现。
hashMap 的数组大小必须是 2 的幂，至于为什么，感兴趣的可以搜一下，这里先不说了，我想要的讲的是 HashMap 的 put 方法，也就是为马 map 中添加一个元素。Map 添加元素的方式是通过 put，向容器中存入一个 Key-Value 对。下面我将详细介绍 put 的实现过程，这个方法非常重要，吃透了这个方法的实现原理，基本也就能搞懂 HashMap 是怎么一回事了。
大致上：首先会判断是否第一次添加元素，如果是第一次，就会先创建一个一定大小的数组（table）。接着通过 hash 与数组长度的操作，确定 key 对应的位置，也就是 key 值通过 hash 算法在数组中确定存储位置。如果找到的位置为空，那么就在当前数组位置，为这个 key-value 创建一个节点。如果对应的位置有值，则会和 key 值进行比较，如果 key 值相同，则表明是同一个元素，直接把 value 值替换。如果 key 值不相同，那么就会进行遍历整个数组，如果找到了有相同的 key 值，则在对应位置替换其 value 值。如果没有找到相同的 key 值，那么就在链表尾部添加中这个元素。源代码如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 获取 key 的 hash 值，这里讲 hash 值的高 16 位右移和低 16 位做异或操作，目的是为了减少 hash 冲突，使 hash 值能均匀分布。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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 是空的，首先创建一个指定大小的 table。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通过对 hash 与数组长度的与操作，确定 key 对应的数组位置，然后读取该位置中的元素。
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果当前位置为空，那么就在当前数组位置，为这个 key-value 创建一个节点。
tab[i] = newNode(hash, key, value, null);
else {
// 如果当前位置已经存在元素，那么就要逐个读取这条链表的元素。
Node<K,V> e; K k;
// 如果 key 和 hash 值都等于当前头元素，那么这存放的两个元素是相同的。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果当前位置的链表类型是 TreeNode，那么就讲当前元素以红黑树的形式存放。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 遍历链表的所有元素，如果都未找到相同 key 的元素，那么说明这个元素并不在容器中存在，因此将他添加到链表尾部，并结束遍历。
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在遍历过程中，发现了相同的 key 值，那么就结束遍历。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果 e != null 说明在当前容器中，存在一个相同的 key 值，那么就要替换 key 所对应的 value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 这是专门留给 LinkedHashMap 调用的回调函数，LinkedHashMap 会实现这个方法。从这里可以看出，HashMap 充分的考虑了他的扩展性。
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 这里判断当前元素的数量是否超过了容量的上限，如果超过了，就要重新进行扩容，并对当前元素重新 hash，所以再次扩容以后的元素位置都是会改变的。
if (++size > threshold)
resize();
// 此方法也是 HashMap 留给 LinkedHashMap 实现的回调方法。透露一下，因为 LinkedHashMap 在插入元素以后，都会维护他的一个双向链表
afterNodeInsertion(evict);
return null;
}
再说一句,在 put 元素的过程中，可能会出现当前元素的数量超过了容量上限，那么就会进行扩容，前面提到了 haspmap 的容量必须为 2 的幂，所以每次扩容都是之前的两倍，再次扩容之后会对元素重新 hash,所以元素的位置会发生改变。下面附上扩容方法的源代码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果容器并不是第一次扩容的话，那么 oldCap 必定会大于 0
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// threshold 和数组大小 cap 共同扩大为原来的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
// 第一次扩容，并且设定了 threshold 值。
else if (oldThr > 0)
newCap = oldThr;
else {
// 如果在创建的时候并没有设置 threshold 值，那就用默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 第一次扩容的时候 threshold = cap * loadFactor
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];
table = newTab;
// 如果不是第一次扩容，那么 hash 表中必然存在数据，需要将这些数据重新 hash
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;
el
se if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 这里分两串，lo 表示原先位置的所有，hi 表示新的索引
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 因为 cap 都是 2 的幂次，假设 oldCap == 10000，
// 假设 e.hash= 01010 那么 e.hash & oldCap == 0。
// 老位置= e.hash & oldCap-1 = 01010 & 01111 = 01010
// newCap 此时为 100000，newCap-1=011111。
// 此时 e.hash & newCap 任然等于 01010，位置不变。
// 如果 e.hash 假设为 11010，那么 e.hash & oldCap != 0
// 原来的位置为 e.hash & oldCap-1 = 01010
// 新位置 e.hash & newCap-1 = 11010 & 011111 = 11010
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论