2

我正在尝试对键上的 TreeMap 进行排序。键是一些具有 int、List、String 等的自定义 DataStructure。我期望排序的成员有一些重复项。假设该成员是Rank。超过 1 个对象可以具有相同的等级。

简化版示例：

注意：在 CompareTo 方法中，不会有意返回 0 以不忽略重复项。（如果这不是避免重复项的正确方法，请纠正我）

import java.util.TreeMap;


public class TreeTest {

public static void main(String[] args) {
    TreeMap<Custom,String> t = new TreeMap<Custom,String>();
    Custom c1 = new Custom();
    c1.setName("a");
    c1.setRank(0);

    Custom c2 = new Custom();
    c2.setName("b");
    c2.setRank(1);

    Custom c3 = new Custom();
    c3.setName("c");
    c3.setRank(0);

    t.put(c1, "first");
    t.put(c2, "Second");
    t.put(c3, "Third");

    System.out.println(t.keySet());

    for(Custom c:t.keySet()){
        System.out.println(t.get(c));
    }
  }
}

和自定义对象

package com.example.ui;

 public class Custom implements Comparable<Custom>{

int rank;
String name;

public int getRank() {
    return rank;
}

public void setRank(int rank) {
    this.rank = rank;
}

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}



@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    result = prime * result + rank;
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Custom other = (Custom) obj;
    if (name == null) {
        if (other.name != null)
            return false;
    } else if (!name.equals(other.name))
        return false;
    if (rank != other.rank)
        return false;
    return true;
}

    // 0 is not returned intentionally to NOT ignore duplicates.
 public int compareTo(Custom o) {
    if(o.rank>this.rank)
        return 1;
    if(o.rank==this.rank)
        return -1;
    return -1;
 }
 }

输出：：

[com.example.ui.Custom@fa0, com.example.ui.Custom@fbe, com.example.ui.Custom@f80]
空值
空值
空值

预期：分别基于排名 0、1、0 的第一、第二、第三。

我在谷歌上看了几个例子。它们中的大多数是使用具有原始数据类型的键或值进行 TreeMap 排序的基本用法，但当排序成员是自定义键 DataStructure 的一部分时，没有一个具有重复项。

请帮忙？

4

3 回答 3

8

问题是您的实现compareTo与 equals 不一致，这是TreeMap. 从 API 文档：

请注意，如果该排序映射要正确实现 Map 接口，则排序映射维护的排序（无论是否提供显式比较器）必须与 equals 一致。

一种可能的一致实现是首先按等级比较，然后在等级值相等时按名称进行比较。对于具有相同等级和相同名称的两个 Custom 实例，您不应该期望能够将它们都存储为同一个 Map 中的键 -这违反了 Map 的约定。

public int compareTo(Custom o) {
  int ret = this.rank - o.rank;

  // Equal rank so fall back to comparing by name.
  if (ret == 0) {
    ret = this.name.compareTo(o.name);
  }

  return ret;
}
于 2011-09-12T08:40:23.807 回答
0

如前所述，您对 equals 和 compareTo 的实现彼此不一致。如果我正确阅读了您的问题，您需要保留具有相同密钥的重复项。我建议您查看 Google Guava 集合的TreeMultimap。它为每个值对象创建集合容器，以便保留具有相同键的不同值。例如

treeMultimap.put ("rank1", "Joe");
treeMultimap.put ("rank1", Jane");
treeMultimap.get ("rank1"); // Set("Joe","Jane");

这个数据结构的约束是 K,V 对必须是唯一的。也就是说，您不能在 Multimap 中插入 ("rank1", "Joe") 两次。

一个重要的提示：为什么你看到这么多 Map 的例子，使用简单的类型，特别是字符串，是因为 map 中的键必须是不可变的。对象的 equals 和 hashcode 值在它用作映射中的键时不得更改。customObject.setRank(...)转换为您的示例，当排名值用作键时，您无法执行和更新排名值。为此，您首先需要删除键及其值，对其进行更新，然后再次插入。

于 2011-09-12T09:11:00.940 回答
0

您也可以通过将 Comparator 实现为匿名内部类型并覆盖 compare() 以返回所需的比较来实现。

public class TreeMaps 
{
    public static void main(String[] args) 
    {
    Custom c1 = new Custom(1,"A");
    Custom c2 = new Custom(3,"C");
    Custom c3 = new Custom(2,"B");

    TreeMap<Custom , Integer > tree = new TreeMap<Custom, Integer>  (new Comparator<Custom>() {

                                            @Override
                                            public int compare(Custom o1, Custom o2) {

                                                return o1.rank - o2.rank;
                                            }
                                        });
    tree.put(c1, 1);
    tree.put(c2, 2);
    tree.put(c3, 3);

    System.out.println(tree);
}
}

class Custom
{
int rank ; 
String name  ; 
public Custom(int rank , String name) {
    this.rank = rank ;
    this.name = name ;

}

@Override
public String toString()
{
    return "Custom[" + this.rank + "-" + this.name + "]" ;
}
}
于 2019-04-28T21:30:38.010 回答