TreeMap是如何完成添加对象与删除对象

闲着无聊，突然想到二叉树结构，这些SUM公司的大神到底是咋么完成这个结构呢？？

不多少果断打开源代码。

源码：

1. private final Comparator<? super K> comparator;//一个比较器
   
2. private transient Entry<K,V> root = null;//这是什么？？根？？
   
3. private transient int size = 0;//容器长度
   
4. private transient int modCount = 0;//应该是个计数器

复制代码

（PS:这些大神很厉害，仅仅定义了四个成员变量就完成了集合的构造？？）

构造方法：

                        public TreeMap() {comparator = null;}

（PS：构造方法一般咱都用无参的，就拿它做例子吧^_^）

添加方法：

1. public V put(K key, V value) {
   
2.         Entry<K,V> t = root;         //t=roor=null
   
3.         if (t == null) {
   
4.             compare(key, key); // type (and possibly null) check
   
5. （第一次添加元素的时候尽然是拿自己与自己做了下无聊的比较，而且还是调用键的比较方法，虽然没有接受该返回值。但是说明键一定要实现了Comparable接口,具备比较性才行。）
   
6.             root = new Entry<>(key, value, null);
   
7. (这个对象到底是什么?尽然把传进来的键值对封装起来了，很有可能这就是它内部的容器)
   
8.             size = 1;         //长度=1
   
9.             modCount++;        //计数器+1
   
10.             return null;        //返回一个null
    
11.         }

复制代码

（当TreeMap集合里为null时，会调用一次键的compareTo方法，对值进行一次比较，主要功能是判断键是否为null，也就是说键必须有唯一性，)

(好像没有对值有要求？?难道我们可以让不同的键对应同一个值？？）

——————————————————————————————————————

1. int cmp;
   
2.         Entry<K,V> parent;
   
3.         // split comparator and comparable paths
   
4.         Comparator<? super K> cpr = comparator;
   
5.         if (cpr != null) {
   
6.             do {
   
7.                 parent = t;
   
8.                 cmp = cpr.compare(key, t.key);
   
9.                 if (cmp < 0)
   
10.                     t = t.left;
    
11.                 else if (cmp > 0)
    
12.                     t = t.right;
    
13.                 else
    
14.                     return t.setValue(value);
    
15.             } while (t != null);
    
16.         }

复制代码

(PS:凭感觉我认为 if 里面这一部分应该是在利用外界传进来的比较器进行比较,集合则按照指定比较器的规则来比较,而且值没有参与比较，断定值在TreeMap集合中是可以重复的)

———————————————————————————————————————

1. else {
   
2.             if (key == null)
   
3.                 throw new NullPointerException();
   
4.             Comparable<? super K> k = (Comparable<? super K>) key;
   
5.             do {
   
6.                 parent = t;
   
7.                 cmp = k.compareTo(t.key);
   
8.                 if (cmp < 0)
   
9.                     t = t.left;
   
10.                 else if (cmp > 0)
    
11.                     t = t.right;
    
12.                 else
    
13.                     return t.setValue(value);
    
14.             } while (t != null);
    
15.         }

复制代码

（else 里的代码不用想，肯定就是利用键的比较性去比较，但是和容器为空时比较不同，这里是拿传进来的键与容器里已有的键作比较）

———————————————————————————————————————

        Entry<K,V> e = new Entry<>(key, value, parent);

(又是这个对象，又把键值对都封装起来了，还把上一个对象穿进去了,80%感觉他像容器，如同链条一样一个接一个的吧对象连接在一起)   

1. if (cmp < 0)
   
2.             parent.left = e;
   
3.         else
   
4.             parent.right = e;
   
5.         fixAfterInsertion(e);
   
6.         size++;
   
7.         modCount++;
   
8.         return null;

复制代码

}

疑问：Entry到底是个什么对象？？？不罗嗦看源码······

(找啊找啊找啊``````````咦，找到一个好朋友^_^)

源码:

1.          static final class Entry<K,V> implements Map.Entry<K,V> {
   
2.         K key;
   
3.         V value;
   
4.         Entry<K,V> left = null;
   
5.         Entry<K,V> right = null;
   
6.         Entry<K,V> parent;
   
7.     boolean color = BLACK;<span style="font-size: 10.5pt; text-indent: 21pt; line-height: 1.5;"> </span>

复制代码

Entry尽然是TreeMap的内部静态类，大神的设计果然很不一般。。。。

看到这些Entry的成员变量，我想应该明白TreeMap是如何完成二叉树的数据结构了，这就是活生生的递归原理，看样子Tree这结构的弊端也展现出来，占内存！！

--------------------------------------------------------------------

当建立一个TreeMap对象时，里面还没有结构，|

一旦添加对个元素进去，就会创建一个第一个Entry|

对象,而Entry对象内部又有三个Entry对象，会形 |

成一个三脚架，而第对元素会以地址的形式存到   |

Entry的key和value里面，然后这个Entry对象的         |

Parent始终指向null,而left与reght却没有明确 |

指向,暂时指向null。当有其他元素对进来时，将 |

改变指向。

而之后的Entry则指向上一个Entry。

（PS：好复杂的关系，头都大了）                     

（还是用图片描述快捷）

删除元素的话就更简单了，就是拿最下层的一个Entry对象拷贝到将要删除的Entry对象的指向，用一个Object变量记录要删除Entry的value，再把将要删除Entry的指向都都指向null，然后返回记录的变量，就可以完成删除。

（其实删除的那个元素还是存在的，只是改变了指向······又是题外话了）

以上纯属个人推测，不对不怪~~

TreeMap是如何完成添加对象与删除对象

闲着无聊，突然想到二叉树结构，这些SUM公司的大神到底是咋么完成这个结构呢？？

不多少果断打开源代码。

源码：

1. private final Comparator<? super K> comparator;//一个比较器
   
2. private transient Entry<K,V> root = null;//这是什么？？根？？
   
3. private transient int size = 0;//容器长度
   
4. private transient int modCount = 0;//应该是个计数器

复制代码

（PS:这些大神很厉害，仅仅定义了四个成员变量就完成了集合的构造？？）

构造方法：

                        public TreeMap() {comparator = null;}

（PS：构造方法一般咱都用无参的，就拿它做例子吧^_^）

添加方法：

1. public V put(K key, V value) {
   
2.         Entry<K,V> t = root;         //t=roor=null
   
3.         if (t == null) {
   
4.             compare(key, key); // type (and possibly null) check
   
5. （第一次添加元素的时候尽然是拿自己与自己做了下无聊的比较，而且还是调用键的比较方法，虽然没有接受该返回值。但是说明键一定要实现了Comparable接口,具备比较性才行。）
   
6.             root = new Entry<>(key, value, null);
   
7. (这个对象到底是什么?尽然把传进来的键值对封装起来了，很有可能这就是它内部的容器)
   
8.             size = 1;         //长度=1
   
9.             modCount++;        //计数器+1
   
10.             return null;        //返回一个null
    
11.         }

复制代码

（当TreeMap集合里为null时，会调用一次键的compareTo方法，对值进行一次比较，主要功能是判断键是否为null，也就是说键必须有唯一性，)

(好像没有对值有要求？?难道我们可以让不同的键对应同一个值？？）

——————————————————————————————————————

1. int cmp;
   
2.         Entry<K,V> parent;
   
3.         // split comparator and comparable paths
   
4.         Comparator<? super K> cpr = comparator;
   
5.         if (cpr != null) {
   
6.             do {
   
7.                 parent = t;
   
8.                 cmp = cpr.compare(key, t.key);
   
9.                 if (cmp < 0)
   
10.                     t = t.left;
    
11.                 else if (cmp > 0)
    
12.                     t = t.right;
    
13.                 else
    
14.                     return t.setValue(value);
    
15.             } while (t != null);
    
16.         }

复制代码

(PS:凭感觉我认为 if 里面这一部分应该是在利用外界传进来的比较器进行比较,集合则按照指定比较器的规则来比较,而且值没有参与比较，断定值在TreeMap集合中是可以重复的)

———————————————————————————————————————

1. else {
   
2.             if (key == null)
   
3.                 throw new NullPointerException();
   
4.             Comparable<? super K> k = (Comparable<? super K>) key;
   
5.             do {
   
6.                 parent = t;
   
7.                 cmp = k.compareTo(t.key);
   
8.                 if (cmp < 0)
   
9.                     t = t.left;
   
10.                 else if (cmp > 0)
    
11.                     t = t.right;
    
12.                 else
    
13.                     return t.setValue(value);
    
14.             } while (t != null);
    
15.         }

复制代码

（else 里的代码不用想，肯定就是利用键的比较性去比较，但是和容器为空时比较不同，这里是拿传进来的键与容器里已有的键作比较）

———————————————————————————————————————

        Entry<K,V> e = new Entry<>(key, value, parent);

(又是这个对象，又把键值对都封装起来了，还把上一个对象穿进去了,80%感觉他像容器，如同链条一样一个接一个的吧对象连接在一起)   

1. if (cmp < 0)
   
2.             parent.left = e;
   
3.         else
   
4.             parent.right = e;
   
5.         fixAfterInsertion(e);
   
6.         size++;
   
7.         modCount++;
   
8.         return null;

复制代码

}

疑问：Entry到底是个什么对象？？？不罗嗦看源码······

(找啊找啊找啊``````````咦，找到一个好朋友^_^)

源码:

1.          static final class Entry<K,V> implements Map.Entry<K,V> {
   
2.         K key;
   
3.         V value;
   
4.         Entry<K,V> left = null;
   
5.         Entry<K,V> right = null;
   
6.         Entry<K,V> parent;
   
7.     boolean color = BLACK;<span style="font-size: 10.5pt; text-indent: 21pt; line-height: 1.5;"> </span>

复制代码

Entry尽然是TreeMap的内部静态类，大神的设计果然很不一般。。。。

看到这些Entry的成员变量，我想应该明白TreeMap是如何完成二叉树的数据结构了，这就是活生生的递归原理，看样子Tree这结构的弊端也展现出来，占内存！！

--------------------------------------------------------------------

当建立一个TreeMap对象时，里面还没有结构，|

一旦添加对个元素进去，就会创建一个第一个Entry|

对象,而Entry对象内部又有三个Entry对象，会形 |

成一个三脚架，而第对元素会以地址的形式存到   |

Entry的key和value里面，然后这个Entry对象的         |

Parent始终指向null,而left与reght却没有明确 |

指向,暂时指向null。当有其他元素对进来时，将 |

改变指向。

而之后的Entry则指向上一个Entry。

（PS：好复杂的关系，头都大了）                     

（还是用图片描述快捷）

删除元素的话就更简单了，就是拿最下层的一个Entry对象拷贝到将要删除的Entry对象的指向，用一个Object变量记录要删除Entry的value，再把将要删除Entry的指向都都指向null，然后返回记录的变量，就可以完成删除。

（其实删除的那个元素还是存在的，只是改变了指向······又是题外话了）

以上纯属个人推测，不对不怪~~