Сортировка пользовательской структуры данных по ключу в TreeMap - PullRequest
Новая
       13

Сортировка пользовательской структуры данных по ключу в TreeMap

1 голос
/ 12 сентября 2011

Я пытаюсь отсортировать TreeMap по ключу. Ключ - это некоторая пользовательская DataStructure, имеющая int, List, String и т. Д. Член, на котором я ожидаю сортировку, имеет несколько дубликатов. Допустим, этот участник - Ранг. Более 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]
null
null
null

Ожидаемое: Первый, Второй, Третий на основании Ранга 0,1,0 соответственно.

Я посмотрел пару примеров в Google. Большинство из них были базовыми для сортировки TreeMap с использованием ключей или значений с примитивными типами данных, но ни один с дубликатами при сортировке члена является частью пользовательского ключа DataStructure.

Пожалуйста, помогите?

Ответы [ 3 ]

7 голосов
/ 12 сентября 2011

Проблема в том, что ваша реализация compareTo не согласуется с equals, что требуется для TreeMap.Из документации API:

Обратите внимание, что порядок, поддерживаемый отсортированной картой (независимо от того, предоставляется ли явный компаратор), должен соответствовать уравнениям, если эта отсортированная карта должна правильно реализовывать интерфейс карты.

Одна из возможных последовательных реализаций будет состоять в том, чтобы сначала сравнить по рангу, а затем по имени, если значения ранга равны.Для двух экземпляров Custom с одинаковыми рангами и одинаковыми именами вы не должны ожидать, что сможете хранить их как ключи на одной и той же карте - Это нарушает контракт карты . 

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;
}
0 голосов
/ 29 апреля 2019

Вы также можете сделать это, реализовав 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 + "]" ;
}
}
0 голосов
/ 12 сентября 2011

Как уже упоминалось, ваша реализация equals и compareTo не согласуются друг с другом.Если я правильно прочитал ваш вопрос, вам нужно сохранить дубликаты с одинаковым ключом.Я бы порекомендовал вам взглянуть на TreeMultimap коллекций Google Guava.Он создает наборы контейнеров для каждого объекта значения, так что различные значения, имеющие один и тот же ключ, сохраняются.например, 

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

Ограничение в этой структуре данных состоит в том, что пары K, V должны быть уникальными.То есть вы не можете вставить ("rank1", "Joe") дважды в Multimap.

Одно важное замечание: причина, по которой вы видите так много примеров Map, используя простые типы и, в частности,Строки, это то, что ключи на карте должны быть неизменными.Значения equals и hashcode объекта не должны изменяться во время его использования в качестве ключа на карте.В переводе на ваш пример вы не можете выполнить customObject.setRank(...) и обновите значение ранга, когда оно используется в качестве ключа.Для этого сначала необходимо удалить ключ и его значения, обновить его, а затем вставить его снова.

...