Java集合之TreeMap

以你之姓@ 2022-04-06 04:22 209阅读 0赞

# 1.TreeMap #

TreaaMap基于红黑树实现，是一个有序的Key-Value集合，根据Comparator 来进行排序，可以根据构造器来传入比较器来实现其他方法的比较。

//默认比较器
        private final Comparator<? super K> comparator;
        //根节点
        private transient Entry<K,V> root;
        //大小
        private transient int size = 0;
        //修改次数
        private transient int modCount = 0;

单个节点所具有的成员变量

static final class Entry<K,V> implements Map.Entry<K,V> { 
            K key;
            V value;
            Entry<K,V> left;
            Entry<K,V> right;
            Entry<K,V> parent;
            boolean color = BLACK;
            Entry(K key, V value, Entry<K,V> parent) { 
                this.key = key;
                this.value = value;
                this.parent = parent;
            }
    		//剩下都是花里胡哨的
        }

# 2. 源码解析 #

1.  构造方法

public TreeMap() { 
    		//默认比较机制
            comparator = null;
        }
    
        public TreeMap(Comparator<? super K> comparator) { 
        	//自定义的比较器
            this.comparator = comparator;
        }
    	//参数为TreeMap集合
        public TreeMap(Map<? extends K, ? extends V> m) { 
            comparator = null;
            putAll(m);
        }
     	//参数为TreeMap集合，自带比较器
        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) { 
            }
        }

1.  put方法

public V put(K key, V value) { 
            Entry<K,V> t = root;
            if (t == null) { 
            	//Key的类型确认
                compare(key, key);
                root = new Entry<>(key, value, null);
                size = 1;
                modCount++;
                return null;
            }
            int cmp;
            Entry<K,V> parent;
            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
                    	//更新Value
                        return t.setValue(value);
                } while (t != null);
            }
            //默认比较器
            else { 
                if (key == null)
                    throw new NullPointerException();
                @SuppressWarnings("unchecked")
                //key的类型确认
                    Comparable<? super K> k = (Comparable<? super K>) key;
                //比较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，根据比较器来添加节点
            Entry<K,V> e = new Entry<>(key, value, parent);
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            
            fixAfterInsertion(e);
            size++;
            modCount++;
            return null;
        }

1.  get方法

public V get(Object key) { 
            Entry<K,V> p = getEntry(key);
            return (p==null ? null : p.value);
        }
        
        final Entry<K,V> getEntry(Object key) { 
        	//具有自定义的比较器
            if (comparator != null)
                return getEntryUsingComparator(key);
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            //根据比较器的返回值进行左移/右移，直到取到Entry/null
            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;
        }
        
        final Entry<K,V> getEntryUsingComparator(Object key) { 
            @SuppressWarnings("unchecked")
                K k = (K) key;
            Comparator<? super K> cpr = comparator;
            if (cpr != null) { 
                Entry<K,V> p = root;
                while (p != null) { 
                    int cmp = cpr.compare(k, p.key);
                    if (cmp < 0)
                        p = p.left;
                    else if (cmp > 0)
                        p = p.right;
                    else
                        return p;
                }
            }
            return null;
        }

1.  remove()，rstKey()，lastKey()；firstEntry()，lastEntry()；pollFirstEntry()，pollLastEntry()  
    这些方法都是同道理实现，根据比较器来实现节点的获取！！！！
2.  比较器  
    其实一直比较好奇TreeMap的默认比较器到底是什么样的？？最后想明白，不就是需要Key实现Comparable/comparator接口,重写比较的方法，需要的时候调用就可以了！！！  
    一共有三种写法：① 类实现conparable；② 自定义比较器类实现compare ③ 匿名构造比较器

public class person implements Comparable<person> { 
    	private String name;
    	private int age;
    	//省略get,set
    	@Override
    	public int compareTo(person o) { 
    		int temp = this.age - o.age;
    		return temp == 0 ? this.name.compareTo(o.name) : temp;
    	}
    }
    public class test  { 
    	public static void main(String[] args) throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException { 
    		TreeMap< Object, Object> map = new TreeMap<>();
    		person p  = new person("老王",21);
    		person q  = new person("老电风扇",212);
    		person w  = new person("老",43);
    		person e  = new person("老水电双方都费",21);
    		map.put(p, 2);
    		map.put(q, 2);
    		map.put(w, 2);
    		map.put(e, 2);
    		Set<Entry<Object, Object>> entrySet = map.entrySet();
    		for (Entry<Object, Object> entry : entrySet) { 
    			System.out.println(entry.getKey());
    		}
    	}
    }