# Gibt es so eine SortedMap?



## Gast2 (8. Jun 2010)

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 (8. Jun 2010)

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 (8. Jun 2010)

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



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 (8. Jun 2010)

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 (8. Jun 2010)

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 (8. Jun 2010)

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 (8. Jun 2010)

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



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 (8. Jun 2010)

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.



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 (9. Jun 2010)

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 (9. Jun 2010)

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 (9. Jun 2010)

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 (9. Jun 2010)

SlaterB hat gesagt.:


> 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 (9. Jun 2010)

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




Danke einer der mich versteht ^^...


----------



## Gast2 (9. Jun 2010)

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



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 (9. Jun 2010)

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.



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 (9. Jun 2010)

Ebenius hat gesagt.:


> […] 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 (9. Jun 2010)

@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 (9. Jun 2010)

SirWayne hat gesagt.:


> 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 (9. Jun 2010)

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.


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



Okay das hast du nochmal extra nachgeprüft  
	
	
	
	





```
result = hash1 < hash2 ? -1 : hash1 == hash2 ? 0 : 1;
```
hab ich nicht dran gedacht


----------



## Ebenius (9. Jun 2010)

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

Ebenius


----------



## Gast2 (9. Jun 2010)

Ebenius hat gesagt.:


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



nö passt alles


----------



## Gast2 (5. Jul 2010)

*delete*


----------

