Gibt es so eine SortedMap?

[Gast2]

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:

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

 

[SlaterB]

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?

 

[Gast2]

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?

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...

 

[Gast2]

Also des war mal meine 1. idee

	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;
		}

	}

 

[SlaterB]

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)

 

[ice-breaker]

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.

 

[Gast2]

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

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...

 

[Gast2]

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.

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...

 

[aumaster]

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

 

[Ebenius]

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:

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:

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

 

[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):

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

 

[Ebenius]

ein Comparator bestimmt bei TreeMap und anderen NICHT über das einfügen, allein equals,

Falsch.

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:

{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

 

[Gast2]

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:

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:

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

Danke einer der mich versteht ^^...

 

[Gast2]

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

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:

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;
        }
 
    }

}

 

[Marco13]

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.

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 ...

 

[Gast2]

[…] Etwas in der Art (ungetestet): […]

Werd ich mal versuchen =)

Also mit meinem Beispiel oben klappt das auch sehr gut...
Versteh noch nicht ganz warum extra auf den hashcode geht und ein equals wie bei mir nicht reicht^^...

 

[Ebenius]

@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.

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

 

[Ebenius]

Versteh noch nicht ganz warum extra auf den hashcode geht und ein equals wie bei mir nicht reicht^^...

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

 

[Gast2]

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.

Okay alles klar

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

Okay das hast du nochmal extra nachgeprüft

result = hash1 < hash2 ? -1 : hash1 == hash2 ? 0 : 1;

hab ich nicht dran gedacht

 

[Ebenius]

Gibt's dann jetzt noch ne Frage? Hab ich was überlesen?

Ebenius

 

[Gast2]

Gibt's dann jetzt noch ne Frage? Hab ich was überlesen?

Ebenius

nö passt alles

 

[Gast2]

*delete*