Preface · 序
公众号内容同步备份。
- 本篇文章首发自我的公众号：
Life
- 🎵 太阳照常升起 - 久石让
先对点进文章却发现内容被删除的读者说句抱歉，昨晚的文章由于我忘记注意标题，导致带着个「未命名文章」的标题就发出了。尝试挽救未果，还是做了删除的决定，合并入今天的内容中一起发布，实在抱歉。
光，也许是最好的滤镜：
但，也少不了风雨：
风雨总会过去，也感谢朋友在那晚来地铁站为我送伞。
*vendor：n. 小贩；摊贩
今天看到 Set 集合一章，集合的特点是无序、唯一。虽然不能用下标（类似数组）的方式去遍历集合的元素，但我们仍然可以用迭代器、for-in 循环来遍历。所以我就和朋友讨论集合的遍历是如何实现的？
因为朋友是 Java 后端工程师，而我也恰好略微了解点，所以这里以 Java 为例。Java 里的 Set 是 interface 即接口，具体实现则是 HashSet，我们可以查到后者的实现源码。原来 HashSet 只是一层壳，其底层仍然是大名鼎鼎的 HashMap：
// HashSet.java from OpenJDK-16
public Iterator<E> iterator() {
return map.keySet().iterator();
}
这里不去深究细节（其实是我也不会），说说我的个人理解：HashMap 的实现方案是数组与链表（或红黑树）的结合。当出现哈希冲突时，采取链表（或红黑树）的形式存储（数组中存放头节点），其中存储的类型是 Map.Entry<K,V> 即键值对。HashSet 则是不关心值的 HashMap，相当于把集合中的值作为键存储在了底层的 HashMap 中。因此其实 HashSet 还是把内容存储在了数组与链表（或红黑树）的结合中，但存储的顺序并不是按照索引自增，而是根据哈希值，遍历则也就是遍历该数组与链表（或红黑树）的结合即可，核心源码如下：
// HashMap.java from OpenJDK-16
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null); // 🌟
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
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;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
removeNode(p.hash, p.key, null, false, false);
expectedModCount = modCount;
}
}
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
不过以上仅是班门弄斧，若表述或者分析得有问题，还望批评指出，不胜感激。
Code & Notes
可详见《Advanced Swift》笔记一文。
这一周过得可真快。晚安，明天见～
|