然后来看看TreeNode这个数据结构是怎样的.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } } 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); } } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); }一点点来看, 有一个属性 boolean red, 看到这个自然就联想起来红黑树, 说明这里采取的正是红黑树的处理方式. 而在非递归方式中使用红黑树, 代码无疑是比较复杂的, 而其复杂性正是在于, 无法定位其父节点, 保存其父节点的链接. 在这里就定义了一个 parent父节点. 但同时不太理解prev这个属性的作用.
同时我们也可以看到在使用 TreeNode的时候, 代价还是比较高昂的, 我们至少是需要额外的4个引用. 将空间使用量几乎要扩大一倍.
至于如何在TreeNode中插入一个节点, 和二叉树的插入并无不同, 这里有一个很有趣的地方, 由于我们可能在使用hashMap的时候, 并未实现Comparable方法, 但二叉树的插入却必须要进行比较, HashMap中采取了多种策略预防:
首先比较当前的hash值, 由于hashCode()方法的实现太差, hash值相同, 然后检查当前类, 及所有的父类, 是否有实现了Comparable的, 否则的话使用当前类的类名进行比较, 如果类名依然相同, 则采取 Object实现的默认的hashCode()进行比较, 也就是当前对象的地址.
System.identityHashCode(a)所以在对自己的hashCode()方法不够自信的情况下, 最好实现Comparable方法.对自己的代码做一个双重保证.
而在这里可以采取多种方式比较的原因是: 事实上我们并不在乎比较的最终结果及次序究竟如何, 重点在于统一的标准, 对比次序, 去进行比较.
在查找的时候采取同样的策略, 用一长串代码 来替代 compareTo() 方法;
当可以进行比较之后, 就可以在树中插入对应的数据, 但红黑树还需要进行一步平衡操作, 我就不粘贴代码:
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x);仅仅在这里给出方法的构造, 不写实现, 在之前红黑树的章节就可以看出来, 一棵树在操作过程中的主要难点就在于 父节点的获取, 而红黑树的平衡操作又要更进一步, 每次插入的节点都是红色节点, 需要自底向上不断遍历, 同时应用到左旋, 右旋的方法进行树的调整. 由于保存有父节点的链接, 因此整个操作的难度被大大简化.
在最后不要忘记将 root节点的颜色置为黑色, 同时令 root = 返回值, 还有就是将tab[i] 的位置设为root节点.
至于在这里 TreeNode的各种方法的实现细节暂时不进行过多考虑.留在 TreeMap 或 TreeSet再来看.
remove()
我觉得在put方法中, 各种东西其实已经是比较完备的, 因此不再详细贴出其他代码, 整个数据结构的框架已经搭建起来了, 对数据结构的已经有了大致的了解, 明白了底层的运作原理, 再来看实现就是一件相当简单的事情了.
containsKey()
看到方法名, 就知道是通过key值返回存在性, 不难想象必然是通过 key 的hash值到 table[] 的对应位置查找即可.
其get(Object key)与之相类似, 就不再看了.
containsValue()
public boolean containsValue(Object value) { Node<K,V>[] tab; V v; if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; }这里是采取从头到尾一个个遍历的方式进行查找, 如果能够获取到对应的key值, 还是不要使用这个方法. 但在某些情况下我们需要做反向符号表, 也就是通过值来查找出每一个对应的key.
iterator
在HashMap中, 发现一个非常有趣的实现, 并不是单纯的 Iterator方法
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; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } }