# unsortierte HashMap



## dadom110 (11. Januar 2008)

Guten Tag Zusammen,

Ist etwas länger geworden, darum habe ich mal aufgeteilt. Meine Frage steht ganz unten unter [ZIEL], wer meine Beweggründe nachvollziehen will darf weiter lesen 

[Hintergrund]
Ich habe eine HashMap (TreeMap, HashTable...eigentlich egal was ich da nehme). Diese HashTable beinhaltet als Key einen "String", als Value ein Objekt. Nun würde ich gerne eine sortierte Ausgabe der Objekte durchführen, ! anhand eines Objekt-Attributs !

[Versuch]
Ich bin davon ausgegangen, das eine TreeMap nach Keys sortiert. Eine HashMap nicht. Leider musste ich feststellen das dem nicht so ist, kleines mini Beispiel


```
HashMap<String, Integer> unsortedHashMap=new HashMap<String, Integer>();
	
		unsortedHashMap.put("2:2:2", new Integer(100));
		unsortedHashMap.put("4:4:4",new Integer(500));
		unsortedHashMap.put("1:1:1",new Integer(100));
		unsortedHashMap.put("3:3:3",new Integer(1000));
		
		System.out.println("UNSORTED");
		for(String key:unsortedHashMap.keySet()) {
			//System.out.println(key + " --Eisen-- " + unsortedHashMap.get(key).getEisen());
			System.out.println(key) ;
		}
```

liefert mir (leider) ein System.Out das nach keys sortiert ist, und nicht, wie ich erwartet hatte, genau in der Reihenfolge wie die EIngabe erfolgt ist  .
Ich hatte nämlich vor die (nach meinem Wissenstand) unsortierte HashMap durchzugehen, den Key und den zu sortierenden Wert in eine (sortierte?) TreeMap zu schreiben, und das ganze dann wieder in eine HashMap des alten Formates zurück zu führen, etwas so:

HashMap<String,Objekt>

>> TreeMap <Long,String>  (Long ist ein Wert aus dem Objekt zur sortierung, der String der Key aus der vorranggehenden HashMap

>> HashMap<String,Objekt>  (mit der Reihenfolge die die Treemap vorgibt)

aber die HashMap scheint bei meinem kleinen Beispielprogramm auch zu sortieren, was sie eben nicht soll, da ich den Inhalt ja im Grunde schon "selber" sortiert habe.

**********
[ZIEL]
Kurz und knapp:
Ich will eine HashMap, die NICHT nach key-Werten sortiert!
**********

grüße
D


----------



## Thomas Darimont (11. Januar 2008)

Hallo,

das die Keys aus deiner Hashmap der einfüge Reihenfolge entsprechen bzw. richtig sortiert sind ist Zufall, bzw. kommt durch "günstige" hash-Werte zustande.

HashMap -> Hierbei werden die Elemente intern entsprechend ihren Hash Werten in sogenannten "Buckets" Körben  verwaltet. Die zuordnung eines Elements zu einem Bucket kann sich beim hinzufügen / entfernen(?) eines Elements ändern. Beim iterieren über die keys einer HashMap wird dann über jedes Bucket iteriert und die entsprechenden Elemente ausgegeben. 

LinkedHashMap -> Hierbei werden die Elemente über eine verkettete Liste verknüpft. Hierbei bleibt bei den Keys die Einfügereihenfolge erhalten.

TreeMap -> Ist eine SortedMap. Hier werden die Elemente intern entsprechend ihrer Sortierung (entweder sie die Keys Comparable, oder man gibt der TreeMap einen Comparator mit) in einem Rot-Schwarz-Baum abgelegt und können ihrer natürlichen Reihenfolge nach angesprochen werden.

(Der Vollständigkeit halber sollte man noch erwähnen, dass es natürlich noch weitere standard Map Implementierungen gibt.
Hashtable -> Verhalten wie HashMap jedoch Thread-Safe (bei mehreren gleichzeitigen Lesern und einem Schreiber)
IdentityHashMap-> verwendet intern den System.identityHashCode(...) des Keys als Key
WeakHashMap -> kapselt die Keys der Map als WeakReferences und hält die Elemente somit nur so lange wie noch starke Referenzen auf die jeweiligen Keys bestehen.
Zusätzlich gibts noch weitere Implementierungen:
ConcurrentHashMap -> Schnellere Variante einer HashTable (die nicht von Hashtable abgeleitet ist)
ConcurrentSkipListMap -> Schnelle Variante einer SortedMap, wird intern durch eine probabilistische Datenstruktur.
EnumMap -> Spezielle Map wo die Keys Enum-Werte sind.
und und und...
)



```
/**
 * 
 */
package de.tutorials;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author Thomas.Darimont
 * 
 */
public class MapExample {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Map<String, String> mapWithUnsortedKeys = new HashMap<String, String>();
        Map<String, String> mapWithSortedKeys = new TreeMap<String, String>();
        Map<String, String> mapWithInsertionOrderedKeys = new LinkedHashMap<String, String>();

        mapWithUnsortedKeys.put("a", "a");
        mapWithSortedKeys.put("a", "a");
        mapWithInsertionOrderedKeys.put("a", "a");

        mapWithUnsortedKeys.put("c", "c");
        mapWithSortedKeys.put("c", "c");
        mapWithInsertionOrderedKeys.put("c", "c");

        mapWithUnsortedKeys.put("b", "b");
        mapWithSortedKeys.put("b", "b");
        mapWithInsertionOrderedKeys.put("b", "b");

        System.out.println("Unsorted keys: ");
        for (String key : mapWithUnsortedKeys.keySet()) {
            System.out.println(key);
        }

        System.out.println("####################");

        System.out.println("Sorted keys: ");
        for (String key : mapWithSortedKeys.keySet()) {
            System.out.println(key);
        }

        System.out.println("####################");

        System.out.println("Insertion Ordered keys: ");
        for (String key : mapWithInsertionOrderedKeys.keySet()) {
            System.out.println(key);
        }
    }
}
```

Ausgabe:

```
Unsorted keys: 
b
c
a
####################
Sorted keys: 
a
b
c
####################
Insertion Ordered keys: 
a
c
b
```

Gruß Tom


----------



## dadom110 (11. Januar 2008)

Hallo Zusammen,

danke an Thomas (wie immer) eine sehr ausfürliche Antwort, die mir sehr weiter geholfen hat. Ein kleineres Problem habe ich noch. Er sortiert in der TreeMap aufsteigen, weil ich das ganze absteigen realisiert haben will, habe ich mir ein Comperator geschrieben:


```
public class LongComparer implements Comparator {

	@Override
	public int compare(Object o1, Object o2) {
		return (Long)o1>(Long)o2? -1:1;
	}

}
```

Das "lustige" ist, wenn ich das in meinem kleinen TestProgramm laufen lasse, erzielt das Programm das gewünschte ergebniss (absteigend sortiert). Mein eigentlicher Einsatzzweck ist aber JSP, bzw. implementiert in einer JavaBean, und da bekomme ich eine "komische" NullPointer Exception, sobald ich der TreeMap die Klasse zuweise. 

TreeMap<Long, String> sortingTreeMap = new TreeMap<Long, String>(new LongComparer());

Stimmt da was an der Comperarer nicht, oder zickt mein Application Server nur mal wieder nur rum?

grüße
Dom


----------



## zeja (11. Januar 2008)

Comparator ist übrigens auch generisch. Um nicht casten zu müssen kannst du also
Comparator<Long> schreiben.


----------



## Thomas Darimont (11. Januar 2008)

Hallo,

..so zum Beispiel:

```
/**
 * 
 */
package de.tutorials;

import java.util.Comparator;
import java.util.TreeSet;

/**
 * @author Thomas.Darimont
 * 
 */
public class LongComparatorExample {

    /**
     * @param args
     */
    public static void main(String[] args) {
        final TreeSet<Long> longs = new TreeSet<Long>();
        longs.add(5L);
        longs.add(1L);
        longs.add(3L);
        System.out.println(longs);

        System.out.println(new TreeSet<Long>(new Comparator<Long>() {
            @Override
            public int compare(Long first, Long second) {
                return -first.compareTo(second);
            }
        }) {
            {
                addAll(longs);
            }
        });

    }

}
```

Ausgabe:

```
[1, 3, 5]
[5, 3, 1]
```


Gruß Tom


----------



## Booyeoo (11. Dezember 2009)

Guten Tag,

auch wenn dieser Beitrag schon 2 Jahre alt ist, sollte es dennoch nicht möglich sein diese Methode zu basteln um TreeMaps sortiert auszugeben.

public void printHashKeys(TreeMap hm){
 System.out.println("Sorted keys: ");
        for (String key : (hm.keySet()) {
            System.out.println(key);
        }
}

Bekomme leider die Fehlermeldung in der for Zeile angezeigt
Object nicht kompatibel zu String (NetBeans IDE 6.8beta).
Kann den keySet leider auch nicht einfach mit toString() oder mit einem (String)-cast gefügig machen.
Wie könnte ich dem entgegenwirken oder meine Map anders sortiert ausgeben?

Grüße und Danke


----------



## dadom110 (12. Dezember 2009)

HuHu...

zwar hat das bisher noch nicht viel mit Sortierung zu tuen, aber TreeMap ist ein generischer Typ, NetBeans sollte eigentlich bei deiner Methode schon eine Info ausgeben (zumindest tut es Eclipse das).

Eine Treemap ist allgemein ja eine Implementierung der Schlüssel-Wert-Datenhaltung, dabei spielt es erst mal keine Rolle von welchem Datentyp der Key und der Value ist, damit ist das ganze Grundlegend immer ein "Object". Wenn du weisst was du in der Map ablegen willst darfst du ihm das über Generics auch mitteilen:

Hier mal eine WerteListe: String >>> String


Booyeoo hat gesagt.:


> public void printHashKeys(TreeMap<String,String> hm){



und damit bekommt dein "hm.keySet()" keine Liste von Objekten sondern eine Liste von Strings.

Viele Grüße
Dom


----------



## Booyeoo (13. Dezember 2009)

Ich schäme mich richtig...

Danke für den Hinweis, jedenfalls wollte ich es auch dynamisch haben, weil ich auch solche Typen an die Methode übergeben wollte wie <String,TreeMap<String,Float>>..
Müsste dann ja einmal eine Methode mit <String,Integer> machen und einmal <String,TreeMap<String,Float>>... das wollte der nicht... (...same erasure... was auch immer das heißen mag)

Das ganze klappt aber nun doch, wenn ich bei der Übergabe der Parameter die obige Struktur nochmal nach TreeMap caste.


```
{
(....)
printTreeMap((TreeMap) hmmProb); // <-- Aufruf
}                                            

public void printTreeMap(TreeMap tm){
    Set set = tm.entrySet();

    Iterator i = set.iterator();
    while(i.hasNext()){
       Map.Entry me = (Map.Entry)i.next();
       if (me.getKey().equals("\n")){
           System.out.println("\\n" + " : " + me.getValue() );
           taHMMOutput.setText(taHMMOutput.getText()+("\\n" + ": " + me.getValue()+" | "));
       }
       else{
        System.out.println(me.getKey() + " : " + me.getValue() );
        taHMMOutput.setText(taHMMOutput.getText()+(me.getKey() + ": " + me.getValue()+" | "));
       }
    }
}
```


----------

