在TreeMap中的Key上对自定义数据结构进行排序 [英] Sorting custom data structure on Key in TreeMap

问题描述

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

I am trying to sort a TreeMap on key. Key is some custom DataStructure having int, List, String, etc. The member on which I am expecting a sort has some duplicates. Let's say that member is Rank. More than 1 object can have same rank.

简化版本示例:

注意:在CompareTo方法中，不会故意返回0以下以不忽略重复项.(如果这不是避免重复项的正确方法，请纠正我的意思

NOTE: in the CompareTo method below 0 is not returned intentionally to NOT ignore duplicates.(Please correct me if this is not the right way to avoid duplicates)

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]
null
null
null

预期: 第一，第二，第三分别基于等级0,1,0.

Expected: First, Second, Third based on Rank 0,1,0 respectively.

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

I looked at couple of examples on Google. Most of them were basic usage on TreeMap sort using keys or values with primitive datatypes, but none with duplicates when sorting member is a part of custom key DataStructure.

请帮助?

推荐答案

问题是compareTo的实现与equals不一致，这是

The problem is that your implementation of compareTo is not consistent with equals, which is required by TreeMap. From the API docs:

请注意，排序后的地图(无论是否 如果提供显式比较器，则必须与equals保持一致，如果 排序后的地图是为了正确实现Map接口.

Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if this sorted map is to correctly implement the Map interface.

一种可能的一致实现方式是，如果等级值相等，则首先按等级比较，然后按名称比较.对于具有相同等级和相同名称的两个Custom实例，您不应期望能够将它们都存储为同一地图中的键-这违反了Map的合同.

One possible consistent implementation would be to first compare by rank and then by name if the rank values are equal. For two instances of Custom with equal ranks and identical names you should not expect to be able to store them both as keys within the same Map - This violates the contract of 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;
}

这篇关于在TreeMap中的Key上对自定义数据结构进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！