◆
TreeMap简介
◆
推荐查看此篇文章之前首先查看 HashMap源码分析 效果更佳哦
TreeMap在jdk 1.8中使用用的是红黑树的结构来进行存储的,一个典型的红黑树就如下图所示:
而这个结构在代码中表现是这样的:
/** * 红黑树节点 */ static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; TreeMap.Entry<K,V> left; TreeMap.Entry<K,V> right; TreeMap.Entry<K,V> parent; boolean color = BLACK; Entry(K key, V value, TreeMap.Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } }
◆
TreeMap的属性
◆
TreeMap的一些基础属性:
// 比较器对象 private final Comparator<? super K> comparator; //根节点对象 private transient TreeMap.Entry<K,V> root; //集合的大小 private transient int size = 0; //结构被修改的次数 private transient int modCount = 0;
◆
TreeMap的构造方法
◆
/** * 使用默认比较器 * key的类型是什么 * 就采用该类型的compareTo方法来比较大小 * 例如key为String类型,就会用String类的compareTo方法比对大小 */ public TreeMap() { comparator = null; }
/** * 指定比较器 */ public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }
/** * 添加集合 */ public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); }
/** * 将m转换为TreeMap,使用m的比较器 */ public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }
◆
HashMap的添加方法
◆
/** * 添加方法 */ public V put(K key, V value) { TreeMap.Entry<K,V> t = root; //如果跟节点为空,把此节点置为跟节点 if (t == null) { compare(key, key); // type (and possibly null) check
root = new TreeMap.Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; TreeMap.Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator;] //如果指定比较器 if (cpr != null) { //循环比较,插入到合适的位置 do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } // 如果比较器对象为空,使用默认的比较机制 else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } // 根据key找到父节点后新建一个节点 TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent); // 根据比较的结果来确定放在左子树还是右子树 if (cmp < 0) parent.left = e; else parent.right = e; // 插入完成,红黑树的结构会被破坏,执行红黑树的恢复操作 fixAfterInsertion(e); //集合大小增加 size++; //修改次数增加 modCount++; return null; }
◆
TreeMap的查找
◆
/** * 根据key获取 */ public V get(Object key) { TreeMap.Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); } /** * 根据key获取Entry对象 */ final TreeMap.Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; TreeMap.Entry<K,V> p = root; //循环遍历查找 while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; }
◆
TreeMap的删除
◆
/** * 删除节点 */ public V remove(Object key) { //查找元素是否存在 TreeMap.Entry<K,V> p = getEntry(key); if (p == null) return null; V oldValue = p.value; //调用具体的删除方法 deleteEntry(p); return oldValue; } /** * 具体的删除方法 */ private void deleteEntry(TreeMap.Entry<K,V> p) { modCount++; size--;
// 如果待删除节点有两个子节点 if (p.left != null && p.right != null) { TreeMap.Entry<K,V> s = successor(p); p.key = s.key; p.value = s.value; p = s; } // p has 2 children
// Start fixup at replacement node, if it exists. TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right); //待删除节点只有一个孩子 if (replacement != null) { // Link replacement to parent replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion. p.left = p.right = p.parent = null;
// Fix replacement if (p.color == BLACK) fixAfterDeletion(replacement); //如果是根节点 } else if (p.parent == null) { // return if we are the only node. root = null; } else { // 没有子节点 if (p.color == BLACK) fixAfterDeletion(p);
if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } }
鉴于篇幅有限,本篇文章仅列出上方部分代码,TreeMap完整源码解析请点击下方“阅读原文”查看!!!