13-TreeSet和TreeMap基本介绍
13-TreeSet和TreeMap基本介绍
介绍汇总：
- TreeSet基本介绍
- TreeMap基本介绍
1-TreeSet基本介绍
- TreeSet 类用于存储一组对象，并将对象按照自然规则（实现 Comparator 接口的）或者指定 Comparator 对象的比较器进行排序。
- TreeSet 类中的底层是 TreeMap 。
- key 值不可以为 null ，也不可以重复。
- 自然规则排序和指定比较器排序
// 无参构造器，使用元素的自然规则排序
public TreeSet() {
this(new TreeMap<E,Object>());
}
// 指定比较器的构造器，按照该比较器中的规则进行排序
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
- 使用自然规则的话，就需要注意元素需实现 Comparable 接口，并且加入的元素有某种关联，例如，可以进行比较以及同一类元素。
package set.treeset;
import java.util.TreeSet;
public class TreeSetSource {
@SuppressWarnings({"all"})
public static void main(String[] args) {
TreeSet treeSet = new TreeSet();
treeSet.add("aaa");
treeSet.add("bca");
treeSet.add("aba");
treeSet.add("aac");
System.out.println("====treeSet中自然元素有" + treeSet + "====");
}
}
- 指定比较器
package set.treeset;
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetComparator {
@SuppressWarnings({"all"})
public static void main(String[] args) {
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 按照字符串的大小比较 ((String) o1).compareTo((String) o2)
// 结果为 0 的话，表示相等
// 还可以根据字符串长度进行排序 ((String) o1).length() - ((String) o2).length()
// 若结果为 0 ，则说明相等，重复了（TreeMap 的话会更新对应的 value 值）
return ((String) o1).length() - ((String) o2).length();
}
});
treeSet.add("adk");
treeSet.add("bkd");
treeSet.add("kij");
treeSet.add("a");
treeSet.add("ccccc");
System.out.println("====treeSet中自然元素有" + treeSet + "====");
}
}
注：加入的元素符合比较器，可以进行相互的比较。
- TreeSet（TreeMap）部分底层源码分析
// TreeSet.add 添加数据
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
// TreeMap.put 存储数据
public V put(K key, V value) {
// 获取红黑树的根结点
Entry<K,V> t = root;
// 根结点为空，说明为存储数据
if (t == null) {
// 主要确认 key 是否为空，为空会抛异常
compare(key, key); // type (and possibly null) check
// 存储数据创建新结点，并未根结点
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 辅助变量
// 初始比较的结果
int cmp;
// 父节点
Entry<K,V> parent;
// split comparator and comparable paths
// 获取 TreeMap 中的比较器
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 {
// 确保 key 不为空
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 转换成 Comparable 对象，为了获取 compareTo 方法
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);
}
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;
}
2-TreeMap基本介绍
- TreeMap 类用于存储一组键值对，并将键值对按照自然规则（实现 Comparator 接口的）或者指定 Comparator 对象的比较器将 Key 值排序，并以此顺序决定键值对的顺序。
- TreeMap 底层是红黑树。
- Key 值不可以重复，也不可以为 null，而 Value 可以重复，也可以为 null。
- 使用自然规则的话，就需要注意元素需实现 Comparable 接口，并且加入的元素有某种关联，例如，可以进行比较以及同一类元素。
package map.treemap;
import java.util.TreeMap;
public class TreeMapSource {
@SuppressWarnings({"all"})
public static void main(String[] args) {
TreeMap treeMap = new TreeMap();
treeMap.put("aaa","aaa");
treeMap.put("bca","bca");
treeMap.put("aba","aba");
treeMap.put("aac","aac");
System.out.println("====treeMap中自然元素有" + treeMap + "====");
}
}
注：加入的元素的 key 符合比较器，可以进行相互的比较。
- 指定比较器
package map.treemap;
import java.util.Comparator;
import java.util.TreeMap;
public class TreeMapComparator {
@SuppressWarnings({"all"})
public static void main(String[] args) {
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 按照字符串的大小比较 ((String) o1).compareTo((String) o2)
// 结果为 0 的话，表示相等
// 还可以根据字符串长度进行排序 ((String) o1).length() - ((String) o2).length()
// 若结果为 0 ，则说明相等，重复了（TreeMap 的话会更新对应的 value 值）
return ((String) o1).length() - ((String) o2).length();
}
});
treeMap.put("aaa","aaa");
treeMap.put("ab","ab");
treeMap.put("ccc","ccc");
treeMap.put("aadcb","aadcb");
treeMap.put("ddddddd","aaa");
System.out.println("====treeMap中自然元素有" + treeMap + "====");
}
}
- TreeSet（TreeMap）部分底层源码分析
// TreeSet.add 添加数据
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
// TreeMap.put 存储数据
public V put(K key, V value) {
// 获取红黑树的根结点
Entry<K,V> t = root;
// 根结点为空，说明为存储数据
if (t == null) {
// 主要确认 key 是否为空，为空会抛异常
compare(key, key); // type (and possibly null) check
// 存储数据创建新结点，并未根结点
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 辅助变量
// 初始比较的结果
int cmp;
// 父节点
Entry<K,V> parent;
// split comparator and comparable paths
// 获取 TreeMap 中的比较器
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 {
// 确保 key 不为空
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 转换成 Comparable 对象，为了获取 compareTo 方法
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);
}
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;
}