Frage zu Datentyp

[schmiddy123]

Hallo,

ich habe Daten, die ich in einem Int-Array speichere (z.B. [0,1,1,0,2,0,0,1]). Zu jedem solchem Array gibt es einen Int-Wert, ich will jetzt möglichst effizient für jedes Array diesen Wert speichern. Also ich habe z.B.

[0,1,1,0,2,0,0,1] : 10
[1,1,1,1,1,0,0,1] : 5
[2,1,1,2,2,2,2,1] : 14

Ich habe mir gedacht ich mache es mittels einer Hashmap, damit ich leicht auf die Zahl zugreifen kann, die zu einem bestimmten Array gehört.

Wenn ich aber folgendes mache:

hashmap.put("array als key", "zahl als value");

und dann

hashmap.get("array");

dann kriege ich nie den Wert für ein Array raus, auch wenn dieses schon enthalten ist. Ich denke das Problem ist, dass das Array als Objekt darin gespeichert ist, und das neue Array ein anderes Objekt ist, das dann nicht als Schlüssel erkannt wird.
Im Moment schreibe ich das Array in einen String um und speichere diesen dann als Schlüssel, damit funktioniert es. Ich will aber auf die zeitaufwendige Umwandlung verzichten.

Hat jemand einen Tip? Das ganze sollte leider mit Java 1.4 funktionieren....

Kurzfassung meines Problems: ich habe Integer-Arrays denen eine Zahl zugeordnet ist, und will möglichst schnell die zugeordnete Zahl für ein Array abfragen können.

Grüsse, Chris

 

[Wildcard]

Wieso denn als String? Ein Array ist ein Objekt, also kannst du's als Key nehmen.
Die Frage ist eher was du als Value übergibst, denn in Java 1.4 kann man eben nicht einfach so primitive Datentypen in eine Map packen.

 

[schmiddy123]

Aber wenn ich folgendes mache:

int[] x = {1,1,1};

hashmap.put(x, 15);

int[] y = {1,1,1};

hashmap.get(y);

dann kriege ich null zurück, ich denke weil für ihn y noch nicht in der Hashmap enthalten ist.... Es scheint also doch nicht direkt mit Arrays als Key zu gehen?? Oder kriege ich null weil er mit dem int als value nicht umgehen kann??

 

[Wildcard]

Erstens würde das unter JAva 1.4 gar nicht kompilieren, und zweitens sind x und y unterschiedliche Objekt.
y ist ein komplett neues Array das zufällig die gleichen Werte hat.

 

[schmiddy123]

Genau! Das ist gerade mein Problem!

x und y sind unterschiedliche Arrays, die aber die gleichen Werte haben. Und wegen den gleichen Werten ist ihnen auch die gleiche Zahl zugewiesen. Deshalb will ich sie in der Hashmap speichern und wenn ich ein Array krieg, das ich schonmal hatte, will ich die zugeordnete Zahl nicht neu berechnen sondern einfach aus der hashmap herauslesen.

Und jetzt suche ich eben nach einem Weg das effizient (und wenns geht ohne Strings) zu machen.

 

[SlaterB]

die Aufgabe ist aus einem vorhandenen Objekt einen Key zu bestimmen,

wie soll Java deiner Meinung nach vorgehen?
die einzelnen Zahlen addieren? deren Hashcodes addieren?
die Reihenfolge beachten oder nicht?
da gibts keinen einfachen Weg,

manche wollen für zwei Arrays gleichen Inhalts nur dann den gleichen Key wenn es wirklich dasselbe Objekt ist,
du möchtest den gleichen Key, wenn der Inhalt der gleiche ist,

abgesehen von obigen Problemen muss man sich hier zwischen zwei fundamentalen Varianten entscheiden und da ist die, die der unterschiedlichen Keys für jedes Array die einfachere

leider ist ein Array ein besonderer Typ in Jave, so dass du (glaube ich) auch nicht die hashcode()-Operation überschreiben kannst,

da bleiben dir nur drei Möglichkeiten:
1.
von Anfang an auf Arrays verzichen, z.B. ArrayList stattdessen,
2.
vor der Suche in einer Hashmap den Key selber berechen/ ändern,
z.B. indem du einen String daraus machst oder irgendein anderes Objekt, dass du stattdessen als Key verwendest
(alternativ: einen Integer berechnen mit Hilfe einer Hashfunktion, siehe erst mal google falls dir das nichts sagt)
3.
die Hashmap überschreiben, so dass dort der Key anders berechnet wird (z.B. wie bei 2. mit einer eigenen Hashfunktion)

aus einer bestimmten Sichtweise sind 1, und 2. und 3. das gleiche, nur dass der Ort der Logik ein wenig verlagert wird,

das Grundprinzip ist nun mal
Objekt, Key, Map,

bisher benutzt du ein Standardobjekt Array mit einem Standardkey hashcode (mit Standardinhalt irgendwas) und eine Standardmap die auf diesen Standardkey des Standardobjekts zugreift

je nachdem was du machst kannst du manche Schritte verändern,

den Inhalt das Standardkey hashcode ersetzen geht beim Array nicht, bei ArrayList sehr wohl (1.),

den Zugriff der Standardmap auf das Standardobjekt Array ersetzt du durch ein eigenes Objekt in 2.

bleibts bei Standardobjekt Array, dann kannst du mit einer eigenen Map (3.) den nciht zu ändernen Standardkey einfach ignorieren und dir einen anderen Key zusammenbauen (z.B. Array-Elemente anschauen)

klingt verwirrend, ist aber interessant

 

[Wildcard]

Mal anders gefragt:
Was willst du, im größeren Kontext, denn überhaupt machen?
Vieleicht gibt's da eine bessere Möglichkeit.

 

[sayang]

Num mal so in den Raum geworfen. Was ist wenn du ein eigenes Objekt erzeugst, in dem sowohl dein int[] als auch deine zahl gespeichert ist... z. B. so

public class IntArrayMitZahl {
  private int[] intArray;
  private int zahl;

  public IntArrayMitZahl(int[] a) {
    intArray = a;
    berechneZahl();
  }

  public IntArrayMitZahl(int[] a, int z) {
    intArray = a;
    zahl = z;
  }

  private berechneZahl() {
    zahl = ... //... hier aus dem Array die Zahl berechnen
  }

  public int[] getIntArray() {
    return intArray;
  }

  public void setIntArray(int[] a) {
    intArray = a;
  }

  public int getZahl() {
    return zahl;
  }

  public void setZahl(int z) {
    zahl = z;
  }
}

Lg
sayang

 

[schmiddy123]

Erstmal Danke für die Antworten:

@SlaterB: Das hat mir schonmal einiges weitergeholfen! Ich habe bisher noch nie genau darpber nachgedacht, wie bei der HM die keys eigentlich behandelt werden. Vielleicht schreibe ich wirklich eine Funktion, die aus dem Array-Inhalt einenKey erstellt, der verwendet werden kann. mal schauen wie das am schnellsten geht.

@wildcard: worum es genau geht, ist sehr lang zu erklären. ich durchlaufe aber eine lange Berechnung, bei der die int-arrays eine bestimmte genetische Struktur beschreiben. zu dieser Struktur berechne ich einen Wert, eben diesen den ich speichern will, was sehr aufwendig ist, weshalb ich es für jede Struktur nur einmal machen will. Die verschiedenen Strukturen können nämlich mehrmals vorkommen und da wäre es ineffizient bei einer bereits aufgetretenen diesen Wert erneut zu berechnen.

@sayang: Danke, aber mir geht es weniger darum die Zahl zum Array zu speichern, sondern schnell die Zahl zu einem Array irgendwo rauszuholen. ich glaube auf diese Weise bringt es mir leider nicht so viel. Ich denke auch nicht, dass so ein Objekt von der Hashmap direkt als key verwendet werden könnte, selbst wenn, ich kann das Objekt nicht erstellen ohne die Zahl und die will ich ja rausholen und nicht berechnen.....

Falls es noch weitere Vorschläge gibt, nur her damit!! ;-)

 

[SlaterB]

> Ich denke auch nicht, dass so ein Objekt von der Hashmap direkt
> als key verwendet werden könnte,
> selbst wenn, ich kann das Objekt nicht erstellen ohne die Zahl und
>die will ich ja rausholen und nicht berechnen.....

das ginge schon, das ist in etwa das gleiche wie den String zusammenzubauen (Möglichkeit 2),
du musst nun nur noch die hashcode-Operation des eigenen Datentyps überschreiben
und dort den charakteristischen Key zurückgeben, der wahrscheinlich nicht nur die Summe, sondern auch die Reihenfolge berücksichtigen muss,

das ganze macht in einer Verbindung mit der Hashmap natürlich nur Sinn,
wenn diese Berechnung deulich schneller ist als die Berechnung der eigentlich gesuchten Zahl,

aber eins muss dir klar sein: du brauchst irgendwas, was von jedem einzelnen Element des Arrays abhängt,

auch bei einem String ist es nicht einfacher, da muss die Hashfunktion genauso jeden Buchstaben einzeln anschauen und bei der Berechnung miteinbeziehen,

eine Ein-Schritt-Lösung ist von der Logik her unmöglich,

--------

das schnellstmögliche wäre wohl die Speicherung aller Zielwerte in einem riesigen Array,
so dass die Inhalte jedes Einzelarrays als Pfad darin genutzt werden können

int[] array = new int[3][3][3][3][3][3][3][3];


key = [0,1,1,0,2,0,0,1] -> array[key[0]][key[1]]... = array[0][1][1][0][2][0][0][1];

auch hier muss jedes Element einzeln gelesen und benutzt werden


------------

das gleiche etwas sparsamer:
int[] array = new int[3^8];

int index = key[0]*3^0 +key[1]*3^1+key[2]*3^2+..
// gleichzeitig auch eine mögliche Hashfunktion für eine Hashmap!

int zahl = array[index]

klappt natürlich nur in sehr engen Grenzen, auch mit long

 

[NurEinGast]

java.util.Arrays hat hashCode-Methoden für Arrays: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html
Du könntest z. B. nicht das Array selbst, sondern

Integer.valueOf(Arrays.hashCode(deinArray))

als Key verwenden. Ich habe zwar keine Ahnung, ob das funktioniert, aber spontan würde ich es schon sagen.

 

[sayang]

@sayang: Danke, aber mir geht es weniger darum die Zahl zum Array zu speichern, sondern schnell die Zahl zu einem Array irgendwo rauszuholen. ich glaube auf diese Weise bringt es mir leider nicht so viel. Ich denke auch nicht, dass so ein Objekt von der Hashmap direkt als key verwendet werden könnte, selbst wenn, ich kann das Objekt nicht erstellen ohne die Zahl und die will ich ja rausholen und nicht berechnen.....

Aber du könntest doch die Zahl aus diesem Objekt (siehe meinen Post weiter oben) als Key benutzen... oder check ich hier etwas nicht so ganz :?

IntArrayMitZahl foo = new IntArrayMitZahl(deinIntArray[]);
hashmap.put(foo.put(new Integer(foo.getZahl()), foo);

Lg
sayang

 

[schmiddy123]

@nureingast: dein vorschlag ist sehr gut!! Das funktioniert und ist schonmal einiges schneller als meine alte Version! Was mich wundert, mit mehrdimensionalen Arrays scheint die Hashfunktion nicht klarzukommen. Da gibt es bei zwei mehrdimensionalen Arrays mit gleichem Inhalt zwei verschiedene Hashwerte. Weiß jemand woran es liegt? Aber man kann es ja notfalls in eindimensionale umschreiben.

@sayang: wenn ich die Zahl aus dem Objekt als Key verwende, kann ich ja nur rausfinden welches Array zu welcher Zahl gehört, ich will aber die Zahl zum Array rausholen, da die Zahl sehr aufwendig zu berechnen ist.

 

[Wildcard]

@nureingast: dein vorschlag ist sehr gut!! Das funktioniert und ist schonmal einiges schneller als meine alte Version! Was mich wundert, mit mehrdimensionalen Arrays scheint die Hashfunktion nicht klarzukommen. Da gibt es bei zwei mehrdimensionalen Arrays mit gleichem Inhalt zwei verschiedene Hashwerte. Weiß jemand woran es liegt? Aber man kann es ja notfalls in eindimensionale umschreiben.

Wie dir die API verraten hätte, liegt das daran, das diese Methode hashCode auf jedem Element des Arrays aufruft.
Daher hast du das gleiche Problem wieder

 

[NurEinGast]

Was mich wundert, mit mehrdimensionalen Arrays scheint die Hashfunktion nicht klarzukommen. Da gibt es bei zwei mehrdimensionalen Arrays mit gleichem Inhalt zwei verschiedene Hashwerte.

Bisher ging ich davon aus, dass es nur um eindimensionale Arrays geht. Bei Mehrdinemsionalen könntest Du mal deepHashCode(Object[] a) aus der Arrays-Klasse versuchen.