在項(xiàng)目中需要對(duì)一個(gè)
HashMap<String, User> userMap進(jìn)行排序,排序規(guī)則為：HashSet<String> keySet中存在的key優(yōu)先級(jí)高于其它的key，使用TreeMap進(jìn)行保存 测秸，
JDK8 + Lombok1.18
一羡榴、代碼
public class MapTest {
@Test
public void testTreeMap() {
// 里面保存的數(shù)據(jù)優(yōu)先級(jí)要高些
Set<String> keySet = new HashSet<>();
keySet.add("D") ;
keySet.add("B") ;
// 要排序的數(shù)據(jù)
Map<String, User> userMap = new HashMap<>();
userMap.put("A",new User("A",18));
userMap.put("B",new User("B",15));
userMap.put("C",new User("C",18));
userMap.put("D",new User("D",12));
// 排序后的map
Map<String,User> sortMap = new TreeMap<>((k1, k2) -> {
boolean exist1 = keySet.contains(k1);
boolean exist2 = keySet.contains(k2);
if (!exist1 && exist2) {
return -1;
} else if (exist1 && !exist2) {
return -1;
}
return 0;
});
sortMap.putAll(userMap);
System.out.println("");
}
@Setter
@Getter
@NoArgsConstructor
@AllArgsConstructor
public static class User{
private String name ;
private Integer age ;
}
}
以上排序后的結(jié)果可能是什么鳞疲？期望結(jié)果是B和D排在前面惧磺，其它的排后面
二青责、非預(yù)期輸出：
結(jié)果如下：
image.png
-
數(shù)據(jù)丟失了兩個(gè)均抽。并且數(shù)據(jù)不對(duì)
image.png
不得不吐槽簡(jiǎn)書這個(gè)代碼塊的配色嫁赏，黑挫挫的，一點(diǎn)都不利于閱讀油挥，注釋什么的看都看不清Ａ视！Ｉ盍取Ｈ疗埂！
三惋鹅、通過(guò)源碼查找原因
- 直接打開
TreeMap源碼部分, 看put()方法就可以了
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
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
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);
}
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;
}
- 因?yàn)槭亲远x了
comparator, 所以只看下面部分代碼片段
int cmp;
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; // 標(biāo)記1
else if (cmp > 0)
t = t.right; // 標(biāo)記2
else
return t.setValue(value); // 標(biāo)記3
} while (t != null);
}
- TreeMap 使用了紅黑樹結(jié)構(gòu)保存數(shù)據(jù)则酝。喜歡磕一下紅黑樹細(xì)節(jié)的先看這個(gè) 紅黑樹實(shí)現(xiàn)分析 。
標(biāo)記1：comparator.compare(k1, k2)返回值小于0闰集，則把值放在左子樹沽讹，相當(dāng)于排在前面.
標(biāo)記2：comparator.compare(k1, k2)返回值大于0般卑，則把值放在右子樹，相當(dāng)于排在后面.
標(biāo)記3：comparator.compare(k1, k2)返回值等于0爽雄，把k1和k2當(dāng)成相同key蝠检，并替換值。這就造成了上圖中key和具體數(shù)據(jù)不匹配的情況 挚瘟。
四叹谁、解決方法
- 修復(fù)BUG : TreeMap 的比較器不返回0
Map<String,User> sortMap = new TreeMap<>((k1, k2) -> {
boolean exist1 = keySet.contains(k1);
boolean exist2 = keySet.contains(k2);
if (exist1 && !exist2) {
return -1;
}
return 1;
});
-
修改后的結(jié)果如下：
image.png
image.png
五、擴(kuò)展compareTo
public class MapTest {
@Test
public void testTreeMap() {
Map<User, User> userMap = new HashMap<>();
User a = new User("A", 18);
User b = new User("B", 15);
User c = new User("C", 18);
User d = new User("D", 12);
userMap.put(a, a);
userMap.put(b, b);
userMap.put(c, c);
userMap.put(d, d);
Map<User,User> sortMap = new TreeMap<>();
sortMap.putAll(userMap);
System.out.println("");
}
@Setter
@Getter
@NoArgsConstructor
@AllArgsConstructor
private static class User implements Comparable<User>{
private String name ;
private Integer age ;
@Override
public int compareTo(User u) {
return this.getAge() - u.age ;
}
}
}
- 上面這個(gè)例子中
TreeMap的key使用的是User對(duì)象并實(shí)現(xiàn)了Comparable接口乘盖，通過(guò)age的排序焰檩。實(shí)際排序結(jié)果還是會(huì)丟數(shù)據(jù)、數(shù)據(jù)錯(cuò)亂订框，解決方案就是compareTo中不要返回0 锅尘，前提條件是user.compareTo()只用于TreeMap排序。
例子中只是為了說(shuō)明
compareTo用于TreeMap排序時(shí)也不能返回0布蔗，所以就不管Map<User, User>結(jié)構(gòu)是否合理、hashCode和equals是否規(guī)范
