String-Länge: gespeichert oder errechnet?
lima-city → Forum → Programmiersprachen → Java
anwendungsbereich
aufruf
beste laufzeit
datenstruktur
freie bibliotheken
http
index
kollision
lang string
laufzeit
operation
optimierung
speichern
standard
string
szenarium
tip
unterschiedlichsten zwecke
url
vorgeschichte
-
Hallo
Kurz zur Vorgeschichte: Ich bin immer auf Optimierung aus und versuche Zeit und Resourcen zu sparen wo es nur geht. Daher kommt meine Frage.
Ich will eine eigene HashMap implementieren und muss in dieser Strings speichern. Ich will nicht bei jeder Anfrage den Hash-Wert des Strings errechnen müssen und hab mir überlegt ob ich nicht die Länge als Hash-Schlüssel nehme um den String in der Datenstruktur zu speichern.
Wird die Länge im String gespeichert und mit getLength(); einfach zurück gegeben oder wird beim Aufruf von getLength(); die Größe jedes mal neu berechnet? -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Afaik neu berechnet. Der String kann sich ja ändern.
-
Schau mal hier: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/lang/String.java
Ist zwar noch von einem 6er JDK, ich denke aber kaum, dass das geändert wurde. Wie man da sieht, ist die Funktion length einfach ein return count, somit ist das sehr schnell. Das Argument, dass sich der String ändern könnte, zieht nicht wirklich, denn 1. kann man ja bei der Änderung die Länge speichern und 2. sind Java strings soweit ich weiß immutable, kann aber auch sein, dass ich mich irre. -
du hast recht. strings in java SIND immutable
-
Außerdem halte ich es nicht für sehr effizient die Länge als Hash-Schlüssel zu verwenden. In vielen Anwendungsbereichen Hat man viele Strings gleicher Länge was die Laufzeit der Operationen der Hashmap sehr verschlechtert da viele Strings die gleiche Länge haben, und es somit zu vielen Kollisionen kommt. Bei der Hashfunktion solltest du dich besser doch an die Standards halten, da diese die beste Laufzeit garantieren (sonst wären sie ja nicht Standards).
MFG Christoph:)
PS: Ja, Strings sind immutable und die länge ist ein Attribut des Strings. -
So pauschal kann man das mit den Standards nicht sagen. Es gibt immer Szenarien, in denen Alternativen sinnvoll sein können.
Aber Stringlänge als Hashcode halte ich auch für keine gute Idee, außer es gibt damit wirklich entsprechend wenige Kollisionen.
-
Vielleicht noch ein Tip um das Ganze hier abzurunden, schaut euch auch andere freie Bibliotheken an, da gibt es viele Implementierungen für die unterschiedlichsten Zwecke und die sind dann definitv auch effizient umgesetzt.
http://commons.apache.org/proper/commons-collections/javadocs/api-release/index.html
http://docs.guava-libraries.googlecode.com/git/javadoc/index.html -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage