Gibt es so eine SortedMap?

  • Themenstarter Themenstarter Gast2
  • Beginndatum Beginndatum
G

Gast2

Gast
Hallo,

ich bin auf der Suche nach einer SortedMap die folgendes kann.
Wenn man 2 gleiche Keys(equals) hat soll nur der Value verändert werden.
Wenn man aber einen eigenen Comparator hat soll dieser die Keys sortieren, aber nicht daüber bestimmen welcher Key rein soll oder nicht... Mir ist keine Map bekannt die sowas kann, darum wollte ich fragen ob einer eine kennt ?
Beispiel an der TreeMap:
Java: 
public class TreeMapDemo {
	
	public static void main(String[] args) {
		
		MyKey myKey1 = new MyKey();
		myKey1.layer = 1;
		MyKey myKey2 = new MyKey();
		myKey2.layer = 4;
		MyKey myKey3 = new MyKey();
		myKey3.layer = 1;
		
		Map<MyKey, String> map = new TreeMap<MyKey, String>(new MyComparator ());
		//die hier sollten rein
		map.put(myKey1, "dd");
		map.put(myKey2, "ff");
		map.put(myKey3, "ee");// hier ist das Problem wo ich suche dieser key soll ein neuer eintrag geben und nicht die value von myKey1 überschreiben.
		
		// der sollte übeschrieben werden das equals keys gleich sind
		map.put(myKey1, "zz");
		
		//sollte 3 sein ist aber 2 
		System.out.println(map.size());
	}
	
	public static class MyKey{
		public Integer layer;	
	}
	
	public static class MyComparator implements Comparator<MyKey>{

		@Override
		public int compare(MyKey o1, MyKey o2) {
			return o1.layer.compareTo(o2.layer);
		}
		
	}

}

Edit: Comparator eingefügt

EDIT EDIT: Gewünschte Ausgabe:
1 zz
1 ee
4 ff
 
Zuletzt bearbeitet von einem Moderator:
in deinem Beispiel spielt MyComparator keine Rolle, wird nirgendwo verwendet

ein Comparator bestimmt bei TreeMap und anderen NICHT über das einfügen, allein equals,
sicherlich sollten Comparator und equals einigermaßen zusammenarbeiten, aus A equals B folgt immer compare-Wert 0, andersrum muss das aber nicht gelten

ob ein anderes Key-Objekt mit gleichem layer unterschiedlich ist oder nicht hängt allein von der equals-Methode ab,
die kann man so oder so implementieren, wie es dir gefällt

richtig ist, dass du TreeMap nicht mit unterschiedlichen equals-Methoden-Objekten konfigurieren kannst, ähnlich einem Comparator, gehts darum?
 
Zuletzt bearbeitet von einem Moderator:
SlaterB hat gesagt.:
in deinem Beispiel spielt MyComparator keine Rolle, wird nirgendwo verwendet

ein Comparator bestimmt bei TreeMap und anderen NICHT über das einfügen, allein equals,
sicherlich sollten Comparator und equals einigermaßen zusammenarbeiten, aus A equals B folgt immer compare-Wert 0, andersrum muss das aber nicht gelten

ob ein anderes Key-Objekt mit gleichem layer unterschiedlich ist oder nicht hängt allein von der equals-Methode ab,
die kann man so oder so implementieren, wie es dir gefällt

richtig ist, dass du TreeMap nicht mit unterschiedlichen equals-Methoden-Objekten konfigurieren kannst, ähnlich einem Comparator, gehts darum?
Zum Vergrößern anklicken....

Sorry ja den Comparator hab ich vergessen im TreeMap Konstruktor anzugeben...

Das Ziel der Map sollte folgendes beim Einfügen sein:
Das wenn die 2 Layer in dem Comparator gleich sind, dass er diesen Wert hinten anfügt, aber nur wenn die beiden die equals methode der übegebenen Objekte nicht passt...
 
Also des war mal meine 1. idee

Java: 
	private class PositionComparator implements Comparator<MyKey> {

		@Override
		public int compare(MyKey o1, MyKey o2) {
			if(o1.equals(o2)) return 0;
			Integer i1 = o1.layer;
			Integer i2 = o1.layer;
			int result = i1.compareTo(i2);
			
			if(result == 0){
				result = -1;
			}
			
			return result;
		}

	}
 
wie anfügen, die put-Methode soll einen anderen Wert in der Map verändern?
das wirst du bei keiner normalen Collection in der Welt finden,
speziell das zu suchen kann ewig dauern, oder einfach ganz normal selber schreiben

eine normale Map, einfügen per eigener Methode

putOrAdd(key, Value) {
if (key vorhanden) {
..
} else {
..
}
}


(die erste Antwort war übrigens auf Erstposter-Niveau, hab nicht genau geschaut, wer da geschrieben hat)
 
Ganz einfach:
es ist nicht möglich 😉

Selbst wenn du es schaffen solltest, dass 2 Values mit gleichem Key in der Map landen, wie willst du nachher wieder einen bestimmten der Werte wiederbekommen? Die Suche in einem Baum terminiert, sobald der erste übereinstimmende Wert gefunden wurde.

Lösungsvorschlag 1:
pack eine List<String> als Value für einen Key in den Baum

Lösungsvorschlag 2:
implementiere einen Baum, der doppelte Werte für einen Key speichern kann.
 
SlaterB hat gesagt.:
wie anfügen, die put-Methode soll einen anderen Wert in der Map verändern?
das wirst du bei keiner normalen Collection in der Welt finden,
speziell das zu suchen kann ewig dauern, oder einfach ganz normal selber schreiben
Zum Vergrößern anklicken....

He? Ich glaub wir reden aneinander vorbei schau doch mal die implentierung von TreeMap an die macht es doch so ähnlich nur anhand des Comparators... wenn da 0 rauskommt akualisiert dieser den value in der map... Das ist ja schon standard verhalten...
 
ice-breaker hat gesagt.:
Ganz einfach:
es ist nicht möglich 😉

Selbst wenn du es schaffen solltest, dass 2 Values mit gleichem Key in der Map landen, wie willst du nachher wieder einen bestimmten der Werte wiederbekommen? Die Suche in einem Baum terminiert, sobald der erste übereinstimmende Wert gefunden wurde.
Zum Vergrößern anklicken....

Wer redet den von 2 values mit dem gleichen key??? Davon war nie die rede... Es sollen einfach nur die keys nach einem bestimmten wert sortiert werden... 1 key hat 1 value daran ändert sich nichts...
In dem Bsp. oben steht doch alles oder ist was unklar Oo...

Aber ich denke der Comparator oben müsste gehen mal paar tests dafür schreiben...
 
Zuletzt bearbeitet von einem Moderator:
Du hast hier entweder ein grundsätzliches Problem, oder Deine Frage missverständlich formuliert:

Ein Map egal welcher Art (HashMap, TreeMap, etc.) kann nur einen Wert für einen Key beinhalten.
Keine Map erlaubt zwei oder mehr Werte für einen Key mit dem selben Wert.
Besteht ein Key in der Map schon, wird der Wert grundsätzlich überschrieben!

Schau mal bei den Google-Guava-Klassen nach (guava-libraries - Project Hosting on Google Code). Die haben eine TreeMultiMap Klasse.
Ich glaube die kann das was Du möchtest...

Gruß, aumaster
 
Zuletzt bearbeitet:
Also wenn ich SirWayne richtig verstehe, dann will er eine Map deren Schlüssel (genau wie bei der HashMap) nach [c]hashCode()[/c] und [c]equals()[/c] verglichen werden. Die Map soll zusätzlich aber eine SortedMap sein, die das EntrySet mit Hilfe eines Comparators sortiert. Im Sinne des Comparators können Keys doppelt vorkommen, aus Sicht von [c]hashCode()[/c] und [c]equals()[/c] sind sie aber einzigartig.

Beispielsweise soll ein [c]Comparator<String>[/c] den Inhalt lediglich nach dem ersten Buchstaben sortieren:
Java: 
new Comparator<String>() {
  @Override
  public int compare(String s1, String s2) {
    return s1.length() == 0 ? (s2.length() == 0 ? 0 : -1) : (s2.length() == 0 ? 1 : s2.charAt(0) - s1.charAt(0));
  }
}

Wenn man in die Map diese Werte einfügt:
Java: 
map.put("BCA", value);
map.put("BAC", value);
map.put("ABC", value);

… dann sind "BCA" und "BAC" im Sinne des Comparators gleich. Das KeySet soll aber so aussehen: [c]{ "ABC", "BCA", "BAC" }[/c].

Ebenius
 
So, jetzt hab ich eben darüber nachgedacht. Eine fertige Map in diesem Sinne gibt's meines Wissens nicht. Die Lösung kann aber nicht allzu schwer sein. Eine TreeMap mit einem Comparator (der den sortierenden Comparator benutzt und nur bei Gleichheit weitere Unterschiede betrachtet) sollte da eigentlich aushelfen. Etwas in der Art (ungetestet):
Java: 
public class MySortedMap<K, V> extends TreeMap<K, V> {

  /** Serial version UID */
  private static final long serialVersionUID = 1L;

  public MySortedMap(final Comparator<? super K> comparator) {
    super(new Comparator<K>() {

      public int compare(K o1, K o2) {
        int result = comparator.compare(o1, o2);

        if (result == 0 && o1 != o2 && o1 != null && o2 != null) {
          int hash1 = o1.hashCode();
          int hash2 = o2.hashCode();
          if (hash1 == hash2 && !o1.equals(o2)) {
            hash1 = System.identityHashCode(o1);
            hash2 = System.identityHashCode(o2);
          }
          result = hash1 < hash2 ? -1 : hash1 == hash2 ? 0 : 1;
        }

        return result;
      }
    });
  }
}
Ebenius
 
Zuletzt bearbeitet:
SlaterB hat gesagt.:
ein Comparator bestimmt bei TreeMap und anderen NICHT über das einfügen, allein equals,
Zum Vergrößern anklicken....
Falsch.
Java: 
final Map<String, String> map =
  new TreeMap<String, String>(new Comparator<String>() {
    
    public int compare(String s1, String s2) {
      return 0;
    }
  });
map.put("A", null);
map.put("B", "VALUE");
System.out.println(map);
Ausgabe:
Code: 
{A=VALUE}
Das kann auch gar nicht anders sein, da die TreeMap mit Hilfe des Comparators den binären Baum aufbaut. Wenn der Comparator 0 zurück liefert, dann kann die TreeMap sich schlecht per Zufall für einen Ast entscheiden.

Ebenius
 
Ebenius hat gesagt.:
Also wenn ich SirWayne richtig verstehe, dann will er eine Map deren Schlüssel (genau wie bei der HashMap) nach [c]hashCode()[/c] und [c]equals()[/c] verglichen werden. Die Map soll zusätzlich aber eine SortedMap sein, die das EntrySet mit Hilfe eines Comparators sortiert. Im Sinne des Comparators können Keys doppelt vorkommen, aus Sicht von [c]hashCode()[/c] und [c]equals()[/c] sind sie aber einzigartig.

Beispielsweise soll ein [c]Comparator<String>[/c] den Inhalt lediglich nach dem ersten Buchstaben sortieren:
Java: 
new Comparator<String>() {
  @Override
  public int compare(String s1, String s2) {
    return s1.length() == 0 ? (s2.length() == 0 ? 0 : -1) : (s2.length() == 0 ? 1 : s2.charAt(0) - s1.charAt(0));
  }
}

Wenn man in die Map diese Werte einfügt:
Java: 
map.put("BCA", value);
map.put("BAC", value);
map.put("ABC", value);

… dann sind "BCA" und "BAC" im Sinne des Comparators gleich. Das KeySet soll aber so aussehen: [c]{ "ABC", "BCA", "BAC" }[/c].

Ebenius
Zum Vergrößern anklicken....


Danke einer der mich versteht ^^...
 
Ebenius hat gesagt.:
Das kann auch gar nicht anders sein, da die TreeMap mit Hilfe des Comparators den binären Baum aufbaut. Wenn der Comparator 0 zurück liefert, dann kann die TreeMap sich schlecht per Zufall für einen Ast entscheiden.

Ebenius
Zum Vergrößern anklicken....

Richtig darum sagte ich ja bei wenn der Comparator 0 zurück liefert wird die Value akutalisiert!
Aber darum müsst der oben genannte Comparator auch mit einer TreeMap funktionieren, da er bei gleichheit 0 zurückliefert(also nicht einfügen nur aktualisieren) und ansonsten den gewünschten Wert vergleicht und wenn dieser 0 ist diesen auf -1 ändern, damit der key hinten angheängt wird 😉

EDIT:
Java: 
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
import java.util.Map.Entry;


public class TreeMapDemo {
	
	public static void main(String[] args) {
		
		MyKey myKey1 = new MyKey();
		myKey1.layer = 1;
		MyKey myKey2 = new MyKey();
		myKey2.layer = 4;
		MyKey myKey3 = new MyKey();
		myKey3.layer = 1;
		MyKey myKey4 = new MyKey();
		myKey4.layer = 7;
		MyKey myKey5 = new MyKey();
		myKey5.layer = 3;
		
		Map<MyKey, String> map = new TreeMap<MyKey, String>(new MyComparator());
		map.put(myKey1, "dd");
		map.put(myKey2, "ff");
		map.put(myKey3, "ee");
		map.put(myKey4, "gg");
		map.put(myKey5, "aa");
		
		map.put(myKey1, "zz");

		for(Entry<MyKey, String> entry : map.entrySet()){
			System.out.println("Layer: " +entry.getKey().layer +"\t Value: " + entry.getValue());
		}
	}
	
	public static class MyKey{
		public Integer layer;	
	}
	
	private static class MyComparator implements Comparator<MyKey> {
		 
        @Override
        public int compare(MyKey o1, MyKey o2) {
            if(o1.equals(o2)) return 0;
            Integer i1 = o1.layer;
            Integer i2 = o2.layer;
            int result = i1.compareTo(i2);
            
            if(result == 0){
                result = -1;
            }
            
            return result;
        }
 
    }

}
 
Zuletzt bearbeitet von einem Moderator:
Ebenius hat gesagt.:
So, jetzt hab ich eben darüber nachgedacht. Eine fertige Map in diesem Sinne gibt's meines Wissens nicht. Die Lösung kann aber nicht allzu schwer sein. Eine TreeMap mit einem Comparator (der den sortierenden Comparator benutzt und nur bei Gleichheit weitere Unterschiede betrachtet) sollte da eigentlich aushelfen.
Zum Vergrößern anklicken....

Zugegeben, hab den Code jetzt nicht nachvollzogen, aber ganz "pessimistisch" betrachtet vermute ich, dass jeder Versuch, so etwas zu erreichen, an dem "if and only if" aus der Erklärung zu "consistent with equals" von Comparator (Java Platform SE 6) scheitern wird. Aber mal sehen, wie ich darüber denke, wenn ich meinen Koffeinspiegel auf ein erträgliches Maß gebracht habe ...
 
@Marco, Du beziehst Dich darauf?
The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.
Zum Vergrößern anklicken....
Das definiert nur, wann man die Sortierreihenfolge eines Comparator als "kompatibel zu [c]equals()[/c]" bezeichnet. Die meisten Comparators sind nicht kompatibel zu [c]equals()[/c]. Bestes Beispiel: String.CASE_INSENSITIVE_ORDER.

Ebenius
 
SirWayne hat gesagt.:
Versteh noch nicht ganz warum extra auf den hashcode geht und ein equals wie bei mir nicht reicht^^...
Zum Vergrößern anklicken....
Das geht auch ohne [c]hashCode()[/c], kein Problem. Ich wollte nur nahe an der HashMap bleiben. Wichtig ist vor allem, dass der Vergleich zweier (im Sinne von [c]equals()[/c]) ungleicher Argumente immer zum selben Rückgabewert führt. Deswegen der Identity-Hash.

Bei [c]0[/c] dann [c]-1[/c] zurück zu geben macht den Comparator aber instabil und das macht Deinen Baum kaputt. Bei einem Comparator muss immer gelten: Wenn [c]comparator.compare(a,b) > 0[/c] dann [c]comparator.compare(b,a) < 0[/c].

Ebenius
 
Ebenius hat gesagt.:
Das geht auch ohne [c]hashCode()[/c], kein Problem. Ich wollte nur nahe an der HashMap bleiben. Wichtig ist vor allem, dass der Vergleich zweier (im Sinne von [c]equals()[/c]) ungleicher Argumente immer zum selben Rückgabewert führt. Deswegen der Identity-Hash.
Zum Vergrößern anklicken....
Okay alles klar

Ebenius hat gesagt.:
Bei [c]0[/c] dann [c]-1[/c] zurück zu geben macht den Comparator aber instabil und das macht Deinen Baum kaputt. Bei einem Comparator muss immer gelten: Wenn [c]comparator.compare(a,b) > 0[/c] dann [c]comparator.compare(b,a) < 0[/c].
Zum Vergrößern anklicken....

Okay das hast du nochmal extra nachgeprüft
Code: 
result = hash1 < hash2 ? -1 : hash1 == hash2 ? 0 : 1;
hab ich nicht dran gedacht
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Was ist schneller: direkte Sortierung oder indirekt ueber eine SortedMap..?
Antworten: 10
Frage zu SortedMap: Warum kann ich Item zweimal einfügen?
Antworten: 3
SortedMap: Andere Sortierreichenfolge?
Antworten: 8
Alternative zu SortedMap?
Antworten: 8
Reihenfolge einer SortedMap/TreeMap umkehren
Antworten: 3

Zurück
Oben