在 TreeMap中采取了和HashMap相同的策略, 返回对应的 Entry类型, 在具体的iterator中再继承相应的对象即可.
abstract class PrivateEntryIterator<T> implements Iterator<T> { Entry<K,V> next; Entry<K,V> lastReturned; int expectedModCount; //传入最小节点作为起始节点. PrivateEntryIterator(Entry<K,V> first) { expectedModCount = modCount; lastReturned = null; next = first; } public final boolean hasNext() { return next != null; } final Entry<K,V> nextEntry() { Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); next = successor(e); lastReturned = e; return e; } final Entry<K,V> prevEntry() { Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); next = predecessor(e); lastReturned = e; return e; } public void remove(); }关键点在于 successor()方法, 在这里处理方法并不难, 从最小节点开始, 然后逐步向上. 和二叉树中的遍历实现方法是相同的, 不同的是, 我当时用了数组存储父节点, 而在这个地方没必要使用数组而已.
在当前节点有几个方向可以走, 必然不能向左子树深入, 因为必然是从左子树回溯上来的, 只能向上, 或是右.如果右节点不为空, 则直接向右深入, 否则的话, 说明当前节点已经是 父节点下的最大节点了, 必须向上回溯.
如果当前节点是父节点的左子节点, 说明, 父节点没有被遍历过, 返回父节点, 否则的话, 一直向上, 直到当前节点时父节点的左子节点为止.
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; else if (t.right != null) { Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else { Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }
总结
TreeMap的实现到这里告一段落, 可能会有更深入的研究, 但不在目前的探讨范围内.
红黑树的实现特点等等就不再多说, 如果有兴趣, 向上看, 否则我们直接看使用.
TreeMap为有序线程不安全集合. 这里的有序指的是大小有序.在这里并不强制要求实现equals方法.
TreeMap 必须在实现 key的 comparable接口 和 构造器中传入 comparator中选择一个, 不能两者都不实现.
TreeMap底层是红黑树, 查找, 增加, 删除操作都可以在 logn时间内完成.相当高效.
需要注意comparator的使用, 当两个元素 comparator返回0的时候, 如果我们采用的比较器 或 comparable的实现, 不够合理, 并没有利用到全部元素, 那么即使两个不等价的元素, 在这里也会被当做相等元素, 而进一步覆盖掉. 因为我们知道, 在这里是不支持相同键的存在.
因此在使用的时候, 最好同步实现 equals()方法, 并保证两者返回一致, 顺便也可以提醒自己多多注意.
TreeSet
鉴于在之前已经看过HashSet, TreeMap, 这里就不多说.
TreeSet的实现底层则是 TreeMap, 在TreeMap中的注意要点, 在这里同样适用. 因此并没有太多值得关注的地方.
哦, 除了这个:
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...)); 结束语到这里, 我想要关注的集合, 也就全部讲完了, 至于文中提到的 LinkedHashMap
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; }也并不想再多做介绍, 毕竟要学习的还很多, 没办法面面俱到. 每个细节都关注.
我觉得学习算法, 看源码, 相互理解印证这种方式还是相当不错的一种学习手段. 特别是在漫长的三个多月的算法学习中, 从一无所知, 到一点点啃下来, 链表, 队列, 排序, 二叉树, 红黑树, 散列表, 等等. 自己几乎每一种都做了实现, 而不是照抄代码, 搬运工, 很感谢自己的耐心.
实现过这些, 看看源码, 对性能, 时间, 空间的选择理解更深, 才终于觉得自己从码农的身份渐渐脱离出来, 并不仅仅是一个 会 xx.xx 的人了.
还是要多思考, 多努力, 前方的还有许许多多的知识需要学习. 不能懈怠.