Mehrdimensionale Hashtabellen in java?

[Patrick]

Hallo NG

Ich würde in java gerne eine Art mehrdimensionale Hashtabelle anlegen
(so wie in php) oder sonst eine Datenstruktur, bei der ich auf die
Elemente mit doppeltem String-Index (oder Object-Index) zugreifen kann.

Stelle mir sowas vor:

Object get(String idx1,String idx2)

void put(String idx1, String idx2, Object o)

Meines Wissens gibt es in java keine dafür vorgesehene Datenstruktur.
Hat jenamd eine Idee wie ich mir möglichst einfach und performant eine
solche erstellen kann?

Besten Dank im Voraus

[Sascha Broich]

Post by Patrick
Hallo NG
Ich würde in java gerne eine Art mehrdimensionale Hashtabelle anlegen
(so wie in php) oder sonst eine Datenstruktur, bei der ich auf die
Elemente mit doppeltem String-Index (oder Object-Index) zugreifen kann.
Object get(String idx1,String idx2)
void put(String idx1, String idx2, Object o)
Meines Wissens gibt es in java keine dafür vorgesehene Datenstruktur.
Hat jenamd eine Idee wie ich mir möglichst einfach und performant eine
solche erstellen kann?

public class DoubleIndexMap<K1,K2,V>
{
HashMap<K1,HashMap<K2,V>> delegate=new HashMap<K1, HashMap<K2,V>>();

public void put(K1 key1, K2 key2, V value)
{
HashMap<K2, V> map=delegate.get(key1);
if(map==null)
{
map=new HashMap<K2,V>();
delegate.put(key1,map);
}
map.put(key2,o);
}

public V get(K1 key1,K2 key2)
{
HashMap<K2, V> map=delegate.get(key1);
if(map==null) return null;
else return map.get(key2);
}
}

Sascha Broich

[Patrick]

Danke Dir vielmals Sascha für die extrem rasche und hilfreiche
Antwort... das heisst also selber machen.

Wundere micht nur etwas über die Syntax mit < und > sowie über
delegate.. Ist das java 1.5 oder von Dir verwendete Pseudo-Code-Syntax?

Post by Sascha Broich
HashMap<K1,HashMap<K2,V>> delegate=new HashMap<K1, HashMap<K2,V>>();

Merci und schönen Tag noch

[Sascha Broich]

Post by Patrick
Danke Dir vielmals Sascha für die extrem rasche und hilfreiche
Antwort... das heisst also selber machen.

Vielleicht gibts bei Jakarta <http://jakarta.apache.org/> sowas.
Ja. MultiKeyMap scheint das zu können:
A Map implementation that uses multiple keys to map the value.
<http://jakarta.apache.org/commons/collections/apidocs-COLLECTIONS_3_1/org/apache/commons/collections/map/MultiKeyMap.html>

Post by Patrick
Wundere micht nur etwas über die Syntax mit < und > sowie über
delegate.. Ist das java 1.5 oder von Dir verwendete Pseudo-Code-Syntax?

Post by Sascha Broich
HashMap<K1,HashMap<K2,V>> delegate=new HashMap<K1, HashMap<K2,V>>();

Ja, ist 1.5 mit Generics.
delegate weil an die HashMap delegiert wird, ist aber Ansichtssache, wie
man das bezeichnet.

Sascha Broich

[Nico Seessle]

Post by Patrick
Wundere micht nur etwas über die Syntax mit < und > sowie über
delegate.. Ist das java 1.5 oder von Dir verwendete Pseudo-Code-Syntax?

Post by Sascha Broich
HashMap<K1,HashMap<K2,V>> delegate=new HashMap<K1, HashMap<K2,V>>();

Die Syntax mit "<" und ">" sind Generics aus Java 5. In "altem" Java
sieht es dann halt so aus:

public class DoubleIndexMap {
private HashMap delegate = new HashMap();

public void put(Object key1, Object key2, Object value) {
HashMap map = (HashMap) delegate.get(key1);
if (map == null) {
map = new HashMap();
delegate.put(key1, map);
}
map.put(key2, value);
}

public Object get(Object key1, Object key2) {
HashMap map = (HashMap) delegate.get(key1);
if (map == null)
return null;
else
return map.get(key2);
}
}

"delegate" ist nur ein Variablen-Name und hat keine "magische" Bedeutung.

Nico

[Sven Köhler]

Post by Sascha Broich
HashMap<K2, V> map=delegate.get(key1);
if(map==null)
{
map=new HashMap<K2,V>();
delegate.put(key1,map);
}
map.put(key2,o);

Und genau hier fange ich immer an, die Map-API zu hassen. Warum geht nicht:

Map.Entry<K1,HashMap> entry = delegate.createOrGetEntry(key1);
HashMap<K2,V> m = entry.getValue();
if (m == null)
{
m = new HashMap<K2,V>();
entry.setValue(m);
}
m.put(key2, o);

[Sascha Broich]

Post by Sven Köhler
Map.Entry<K1,HashMap> entry = delegate.createOrGetEntry(key1);

Weil das dann nur mit Reflection und Standard-Konstruktor funktionieren
würde. Mal abgesehen davon, daß der Standard-Konstruktor nicht garantiert
ist, bekommst du auch noch ein massives Zeit-Problem durch Reflection.


Sascha Broich

[Ingo R. Homann]

Hi,

Post by Sascha Broich

Post by Sven Köhler
Map.Entry<K1,HashMap> entry = delegate.createOrGetEntry(key1);

Weil das dann nur mit Reflection und Standard-Konstruktor funktionieren
würde. Mal abgesehen davon, daß der Standard-Konstruktor nicht garantiert
ist, bekommst du auch noch ein massives Zeit-Problem durch Reflection.

Dann halt

delegate.getEntryOrDefault(key1,new IrgendeinEntry());

Ciao,
Ingo

[Stefan Matthias Aust]

Post by Ingo R. Homann
delegate.getEntryOrDefault(key1,new IrgendeinEntry());

Schlechte Idee: Das erzeugt ja bei jedem Aufruf ein Exemplar von
"IrgendeinEntry", egal, ob das gebraucht wird oder nicht. Könnte man in
Java Argumente lazy auswerten, wäre es eine Option. Weniger schlecht wäre da

class HashMapWithDefault<K,V> {
HashMapWithDefault(V defaultEntry) {
this.defaultEntry = defaultEntry;
}
V getEntryOrDefault(K key) {
if(...) {
...
}
return defaultEntry.clone();
}
}

Die typische Smalltalk-Collection-Bibliothek kennt neben #at: (was dem
get() entspricht und #at:put: (was dem put() in Java entspricht) auch
ein #at:ifAbsent: sowie #at:ifAbsentPut:. Damit kann man dann

at: key1 and: key2
^(delegate at: key1 ifAbsent: [^nil]) at: key2 ifAbsent: [nil]

at: key1 and: key2 put: value
^(delegate at: key1 ifAbsentPut: [Dictionary new])
at: key2 put: value

formulieren (Ausdrücke in [] werden erst auf Anforderung ausgewertet).

Besser (weil schneller) (egal ob Java oder Smalltalk) erschiene mir
aber, lieber mit einem Objekt, das aus allen Keys gebildet wird und
einer normalen Map zu arbeiten.

[Ingo R. Homann]

Hi SMA,

Post by Stefan Matthias Aust

Post by Ingo R. Homann
delegate.getEntryOrDefault(key1,new IrgendeinEntry());

Schlechte Idee: Das erzeugt ja bei jedem Aufruf ein Exemplar von
"IrgendeinEntry", egal, ob das gebraucht wird oder nicht.

Autsch, stimmt natürlich.

Post by Stefan Matthias Aust
...
Besser (weil schneller) (egal ob Java oder Smalltalk) erschiene mir
aber, lieber mit einem Objekt, das aus allen Keys gebildet wird und
einer normalen Map zu arbeiten.

Das schrieb ich ja auch schon. Sind wir uns also mal wieder einig! :-)

Ciao,
Ingo

[Sven Köhler]

Post by Ingo R. Homann

Post by Sascha Broich

Post by Sven Köhler
Map.Entry<K1,HashMap> entry = delegate.createOrGetEntry(key1);

Weil das dann nur mit Reflection und Standard-Konstruktor funktionieren
würde. Mal abgesehen davon, daß der Standard-Konstruktor nicht garantiert
ist, bekommst du auch noch ein massives Zeit-Problem durch Reflection.

welche Konstruktor= Map.Entry ist ein interface, und natürlich habe ich
angenommen, das ein Entry mit dem value null erzeugt wird.

Post by Ingo R. Homann
Dann halt
delegate.getEntryOrDefault(key1,new IrgendeinEntry());

was habt ihr gegen ein Entry, was per default mit dem value null
erstellt wird?

[Sascha Broich]

Post by Sven Köhler

Post by Ingo R. Homann

Post by Sascha Broich

Post by Sven Köhler
Map.Entry<K1,HashMap> entry = delegate.createOrGetEntry(key1);

Weil das dann nur mit Reflection und Standard-Konstruktor funktionieren
würde. Mal abgesehen davon, daß der Standard-Konstruktor nicht garantiert
ist, bekommst du auch noch ein massives Zeit-Problem durch Reflection.

welche Konstruktor= Map.Entry ist ein interface, und natürlich habe ich
angenommen, das ein Entry mit dem value null erzeugt wird.

Wenn sowieso ein null-Entry rauskommt, dann ist es nicht besser als mein
ursprünglicher Vorschlag.

Post by Sven Köhler

Post by Ingo R. Homann
Dann halt
delegate.getEntryOrDefault(key1,new IrgendeinEntry());

was habt ihr gegen ein Entry, was per default mit dem value null
erstellt wird?

Es stellt keine Verbesserung dar.


Sascha Broich

[Sven Köhler]

Post by Sascha Broich
Wenn sowieso ein null-Entry rauskommt, dann ist es nicht besser als mein
ursprünglicher Vorschlag.

Man bekommt nicht eine null-Referenz, sondern eine Referenz auf ein
Entry-Objekt, dessen getValue()-methode null liefert.

[Sascha Broich]

Post by Sven Köhler

Post by Sascha Broich
Wenn sowieso ein null-Entry rauskommt, dann ist es nicht besser als mein
ursprünglicher Vorschlag.

Man bekommt nicht eine null-Referenz, sondern eine Referenz auf ein
Entry-Objekt, dessen getValue()-methode null liefert.

Damit hast du

public void put(K1 key1,K2 key2, V value)
{
HashMap<K2,V> map=delegate.get(key1);
if(map==null)
{
map=new HashMap<K2,V>();
delegate.put(key1,map);
}
map.put(key2,value);
}

zu

public void put(K1 key1,K2 key2, V value)
{
Map.Entry<K2,V> entry=delegate.getOrCreate(key1);
if(entry.getValue()==null)
{
entry.setValue(new HashMap<K2,V>(); // Wenn das überhaupt geht
}
entry.getValue().put(key2,value);
}

umgewandelt.


Sascha Broich

[Sven Köhler]

Post by Sascha Broich
Damit hast du
public void put(K1 key1,K2 key2, V value)
{
HashMap<K2,V> map=delegate.get(key1);
if(map==null)
{
map=new HashMap<K2,V>();
delegate.put(key1,map);
}
map.put(key2,value);
}
zu
public void put(K1 key1,K2 key2, V value)
{
Map.Entry<K2,V> entry=delegate.getOrCreate(key1);
if(entry.getValue()==null)
{
entry.setValue(new HashMap<K2,V>(); // Wenn das überhaupt geht
}
entry.getValue().put(key2,value);
}
umgewandelt.

richtig, und damit hab ich ein put() auruf - und damit einmal
HashMap-durchsuchen - gespart.

[Sascha Broich]

Post by Sven Köhler

Post by Sascha Broich
Damit hast du
public void put(K1 key1,K2 key2, V value)
{
HashMap<K2,V> map=delegate.get(key1);
if(map==null)
{
map=new HashMap<K2,V>();
delegate.put(key1,map);
}
map.put(key2,value);
}
zu
public void put(K1 key1,K2 key2, V value)
{
Map.Entry<K2,V> entry=delegate.getOrCreate(key1);
if(entry.getValue()==null)
{
entry.setValue(new HashMap<K2,V>(); // Wenn das überhaupt geht
}
entry.getValue().put(key2,value);
}
umgewandelt.

richtig, und damit hab ich ein put() auruf - und damit einmal
HashMap-durchsuchen - gespart.

Und wie soll dein Map.Entry erzeugt werden und an die richtige Stelle
kommen?


Sascha Broich

[Sven Köhler]

Post by Sascha Broich

Post by Sven Köhler

Post by Sascha Broich
public void put(K1 key1,K2 key2, V value)
{
Map.Entry<K2,V> entry=delegate.getOrCreate(key1);
if(entry.getValue()==null)
{
entry.setValue(new HashMap<K2,V>(); // Wenn das überhaupt geht
}
entry.getValue().put(key2,value);
}
umgewandelt.

richtig, und damit hab ich ein put() auruf - und damit einmal
HashMap-durchsuchen - gespart.

Und wie soll dein Map.Entry erzeugt werden und an die richtige Stelle
kommen?

der Key iss bekannt. das reicht einer HashMap üblichweise. Das Value des
Entrys iss der HashMap völlig egal. BTW: Map.Entry.setValue() gibt's
auch jetzt schon.

[Hendrik Müller]

Post by Patrick
Hallo NG
Ich würde in java gerne eine Art mehrdimensionale Hashtabelle anlegen
(so wie in php) oder sonst eine Datenstruktur, bei der ich auf die
Elemente mit doppeltem String-Index (oder Object-Index) zugreifen kann.
Object get(String idx1,String idx2)
void put(String idx1, String idx2, Object o)
Meines Wissens gibt es in java keine dafür vorgesehene Datenstruktur.
Hat jenamd eine Idee wie ich mir möglichst einfach und performant eine
solche erstellen kann?
Besten Dank im Voraus

Ich habe keine Ahnung von PHP. Aber was fuer einen Vorteil bietet
eine zweidimensionale Hashtabelle gegenueber einer normalen.

[Patrick]

Also um was für eine Datenstruktur es sich letztendlich handelt ist
nicht wichtig, wichtig ist dass ich über den genannten Doppelindex
zugreifen kann und dass die Perormance stimmt.

LG

[Ingo R. Homann]

Hi,

Post by Patrick
Also um was für eine Datenstruktur es sich letztendlich handelt ist
nicht wichtig, wichtig ist dass ich über den genannten Doppelindex
zugreifen kann und dass die Perormance stimmt.
LG

Alternative zu der Map-in-Map wäre einfach ein Kombinierter Schlüssel.
In der einfachsten Variante einfach etwas wie index1+"|"+index2 oder
eben eine Key-Klasse, die das sauber kapselt (für den Fall, dass Du kein
"Sonderzeichen" als Trenner "übrig" hast.)

Ciao,
Ingo

[Martin Heibel]

Post by Ingo R. Homann
Alternative zu der Map-in-Map wäre einfach ein Kombinierter Schlüssel.
In der einfachsten Variante einfach etwas wie index1+"|"+index2 oder
eben eine Key-Klasse, die das sauber kapselt (für den Fall, dass Du kein
"Sonderzeichen" als Trenner "übrig" hast.)

Da es nicht gerade trivial ist, dann eine korrekte und sinnvolle
Hash-Methode zu schreiben, würde ich das niemandem vorschlagen, der eine
Frage mit "wie in php" stellt.

M.

[Ingo R. Homann]

Hi,

Post by Martin Heibel

Post by Ingo R. Homann
Alternative zu der Map-in-Map wäre einfach ein Kombinierter Schlüssel.
In der einfachsten Variante einfach etwas wie index1+"|"+index2 oder
eben eine Key-Klasse, die das sauber kapselt (für den Fall, dass Du kein
"Sonderzeichen" als Trenner "übrig" hast.)

Da es nicht gerade trivial ist, dann eine korrekte und sinnvolle
Hash-Methode zu schreiben, würde ich das niemandem vorschlagen, der eine
Frage mit "wie in php" stellt.

Ich halte das für ziemlich trivial:

return o1.hashCode()+o2.hashCode();

Ciao,
Ingo

PS: Je nach Anwendung kann es natürlich bessere Hashfunktionen geben,
aber ich bezweifele, dass PHP die dann auch automatisch findet!

[Paul Ebermann]

"Ingo R. Homann" skribis:
[...]

Post by Ingo R. Homann
PS: Je nach Anwendung kann es natürlich bessere Hashfunktionen geben,
aber ich bezweifele, dass PHP die dann auch automatisch findet!

Bei PHP handelt es sich in diesem Fall um
verschachtelte Hash-Tabellen.

Und als Schlüssel kommen sowieso nur ints und Strings
in Frage, wodurch die Variante "eigene Schlüssel-Objekte"
nicht in Frage kommt.


Paul

[Achim Peters]

Post by Patrick
Ich würde in java gerne eine Art mehrdimensionale Hashtabelle anlegen
(so wie in php) oder sonst eine Datenstruktur, bei der ich auf die
Elemente mit doppeltem String-Index (oder Object-Index) zugreifen kann.
Object get(String idx1,String idx2)
void put(String idx1, String idx2, Object o)
Meines Wissens gibt es in java keine dafür vorgesehene Datenstruktur.
Hat jenamd eine Idee wie ich mir möglichst einfach und performant eine
solche erstellen kann?

Du könntest Dir eine Datenstruktur für zwei Strings / Objekte bauen, die
equals() und hashCode() geeignet implementiert, und dann eine ganz
normale HashMap benutzen.

HashMap#put(new DoubleString(idx1, idx2), o)
HashMap#get(new DoubleString(idx1, idx2))

Bye
Achim

[Martin Heibel]

Post by Achim Peters
Du könntest Dir eine Datenstruktur für zwei Strings / Objekte bauen, die
equals() und hashCode() geeignet implementiert, und dann eine ganz
normale HashMap benutzen.
HashMap#put(new DoubleString(idx1, idx2), o)
HashMap#get(new DoubleString(idx1, idx2))

Na, dann wiederhole ich mich mal: die Hash-Methode ist dabei nicht ganz
trivial - das ist gefährlich.

M.

[Achim Peters]

Post by Martin Heibel

Post by Achim Peters
Du könntest Dir eine Datenstruktur für zwei Strings / Objekte bauen, die
equals() und hashCode() geeignet implementiert, und dann eine ganz
normale HashMap benutzen.
HashMap#put(new DoubleString(idx1, idx2), o)
HashMap#get(new DoubleString(idx1, idx2))

Na, dann wiederhole ich mich mal: die Hash-Methode ist dabei nicht ganz
trivial - das ist gefährlich.

Na ja, in den Specs und Skripten wird immer auf zig Seiten über die
Vorzüge von dieser oder jener Methode geschrieben, und am Ende
implementiert doch jeder mod(p) ... ;-)

Bye
Achim

[Magnus Benjes]

Post by Patrick
Ich würde in java gerne eine Art mehrdimensionale Hashtabelle anlegen
(so wie in php) oder sonst eine Datenstruktur, bei der ich auf die
Elemente mit doppeltem String-Index (oder Object-Index) zugreifen kann.
Object get(String idx1,String idx2)
void put(String idx1, String idx2, Object o)
Meines Wissens gibt es in java keine dafür vorgesehene Datenstruktur.
Hat jenamd eine Idee wie ich mir möglichst einfach und performant eine
solche erstellen kann?

Wie wäre es mit einer normalen Hashtabelle und einem speziellen Schlüssel:

Object gefunden = map.get(new StringPaar(idx1,idx2));
map.put(new StringPaar(idx1,idx2), irgendwas);

public class StringPaar implements Comparable, Cloneable{
public final String a;
public final String b;

public StringPaar(String a, String b){
this.a = a;
this.b = b;
}
public boolean equals(Object obj){
if(obj == null || !(obj instanceof StringPaar))
return false;
StringPaar stringPaar = (StringPaar)obj;
return a.equals(stringPaar.a) && b.equals(stringPaar.b);
}
public int hashCode(){
return a.hashCode() + b.hashCode();
}
public String toString(){
return a + "," + b;
}
public int compareTo(Object obj){
StringPaar stringPaar = (StringPaar)obj;
int diff = a.compareTo(stringPaar.a);
if(diff != 0)
return diff;
else
return b.compareTo(stringPaar.b);
}
public Object clone(){
try{
return super.clone();
}
catch(CloneNotSupportedException ex){
return null;
}
}
}