Hash-Algorithmus

[minzel]

Hallo, habe da mal eine Frage anderer Art:

	private int mod_hash128 (String str, int i) {
		if(i<=0) return 0;
		System.out.println( (int) str.charAt(i-1) * p(128,str.length() + (i*-1)) );
		return mod_hash128(str,--i);
	}
	
	private int p(int x, int y){
		  return (y==0) ? 1 : x * p(x, y-1); 
	}

Dieser Code gibt 3 Zahlen aus. Die mit jeweils der, an stelle, multiplizierten Potenz 128 aus.
Soweit kommen die richtigen Ergebnisse

=> (int) n * 128^2 + (int) o * 128^1 + (int) w * 128^0

Das Wort "now" soll hier mittels Modalelm-Hashing dargestellt werden. Mein Problem ist dabei, das ich irgendwie auf dem Schlauch stehe und nicht weiß wie ich in der Rekursiven Methode die "sysout" - Werte zusammen addieren kann und als Rückgabewert zurück geben kann, ohne dabei noch eine Variable hinzuzunehmen. (Da es dann ja keine Rekusrive Methode mehr ist sondern mehr eine Aufzählung (Iterator).

Hoff jemand weiß Rat.

 

[SlaterB]

  private static int mod_hash128(String str, int i) {
        if (i <= 0) {
            return 0;
        }
        int x = (int) ( str.charAt(i - 1) * Math.pow(128, str.length() - i) );
        return x + mod_hash128(str, --i);
    }

 

[minzel]

hmz, man macht sich das leben ja sonst nicht schwer ...
dank dir ganz doll!

 

[Ark]

Math.pow(128, str.length() - i)

Ich hoffe, ich zeige jetzt, dass ich in Mathe aufgepasst habe. ^^

// Hier steht das Zeichen ^ für "hoch".

(a^b)^c
=a^(b*c)

128^x
=(2^7)^x
=2^(7*x)
=1<<7*x

Math.pow(128, str.length() - i)
=1 << 7*(str.length() -i)

So, das sollte funzen und dabei wesentlich genauer und schneller sein (evtl. long benutzen).

MfG
Ark

 

[byte]

Wäre mal interessant zu wissen, wie die native pow() rechnet, um entscheiden zu können, ob das wirklich schneller ist. Ansonsten ist das aber ein guter Ansatz. Nur die Geschwindigkeit wird wohl eh bei den String-Operationen flöten gehn.

 

[minzel]

Muss mich wohl entschuldigen Mich hat vor ein paar Tagen die Grippe erwischt und sehe jetzt erst das im 1. Lösungsvorschlag das Math.pow(); enthalten ist. Natürlich soll es ohne dem gehen.
Ich Arbeite mich zur Zeit in Hashing ein und will optional alle Methoden selber schreiben. Natürlich solange es im Rahmen bleibt wie bei der Potenz-Methode.

Nur stutz ich eben bei dem Post von Ark.Was ist das?

 

[SlaterB]

2 = ..00000010 in Bits
4 = ..00000100 in Bits

die Bitdarstellung ist automatisch da, mit 2 multiplizieren entspricht dort einfach eine Verschiebung aller Bits um 1 nach links, was sehr schnell zu machen ist,
und ähnliche Tricks

 

[Ark]

@minzel: Nur verstehe ich etwas bei Deinem Algorithmus nicht. 1<<7*x erzeugt bereits bei x=5 eine Zahl, die 36 Bits benötigt, ein int ist allerdings nur 32 Bit breit … ???:L

Ark

EDIT: Na ja, String.hashCode() arbeitet zwar ähnlich, aber trotzdem … seltsam …

 

[minzel]

Also, mit int arbeite ich nicht wirklich. In dem Beispiel ganz oben geht es darum anhand Modularem-Hashing auf der Basis von 128 ein String zu kodieren. Raus kommt dabei ein Schlüssel in Form einer Zahl.

Das einzigste was ich dort gemacht habe ist. Ein Char nach int zu konvertieren. Was man, wie ich bereits gesehen habe sogar ganz weglassen könnte.

Glaub wir reden aneinaner vorbei, oder?

 

[byte]

Wenns um effiziente hashCode() Implementierung geht, ist dieser Link zu empfehlen. Gibt mittlerweile schon viele Java Bücher, die auf diese Lösung von Joshua Bloch hinweisen (siehe Thinking in Java, 4th Edition). Eclipse in der Version 3.2 bietet sogar Möglichkeiten, die hashCode() nach dem Schema automatisch zu implementieren (Source -> Generate hashCode() and equals()...).