Ziel-C: Fowler-Noll-Vo (FNV) Hash-Implementierung

Ich habe einen HTTP-Connector in meinem iPhone-Projekt und Abfragen müssen einen Parameter aus dem Benutzernamen mit dem Fowler-Noll-Vo (FNV) Hash haben.Ziel-C: Fowler-Noll-Vo (FNV) Hash-Implementierung

ich eine Java-Implementierung haben zu diesem Zeitpunkt arbeiten, dies ist der Code:

long fnv_prime = 0x811C9DC5; 
long hash = 0; 

for(int i = 0; i < str.length(); i++) 
{ 
    hash *= fnv_prime; 
    hash ^= str.charAt(i); 
}

Jetzt auf dem iPhone Seite, habe ich dies:

int64_t fnv_prime = 0x811C9DC5; 
int64_T hash = 0; 

for (int i=0; i < [myString length]; i++) 
{ 
    hash *= fnv_prime; 
    hash ^= [myString characterAtIndex:i]; 
}

Dieses Skript mir nicht geben Das gleiche Ergebnis hat das Java.

In erster Schleife, bekomme ich diese:

hash = 0

hash = 100 (erster Buchstabe ist "d")

hash = 1865261300 (für hash = 100 und fnv_prime = - 2128831035 wie in Java)

Wer sieht etwas, das mir fehlt?

Vielen Dank im Voraus für die Hilfe!

Quelle

2010-05-18 Dough

In Java diese Zeile:

long fnv_prime = 0x811C9DC5;

in fnv_prime den numerischen Wert -2128831035, ergeben wird, da die Konstante als int interpretiert wird, das ein 32-Bit-Wert mit Vorzeichen in Java ist. Dieser Wert wird dann vorzeichenerweitert, wenn er in eine long geschrieben wird.

Umgekehrt in dem Objective-C-Code:

int64_t fnv_prime = 0x811C9DC5;

die 0x811C9DC5 wird als unsigned int Konstante interpretiert, mit numerischem Wert 2166136261. Dieser Wert (weil es in einem 32-Bit-int paßt nicht) wird dann in fnv_prime geschrieben, und es gibt kein Zeichen zu erweitern, da der Wert für den C-Compiler positiv ist.

Sie erhalten also eindeutige Werte für fnv_prime, die Ihre eindeutigen Ergebnisse erklären.

Dies kann durch Hinzufügen eines „L“ Suffix, wie dies in Java zu korrigieren:

long fnv_prime = 0x811C9DC5L;

, die zwingen die Java-Compiler zu interpretieren die Konstante als long, mit dem gleichen numerischen Wert als das, was man bekommt mit dem Objective-C-Code.

Quelle

2010-05-18 11:20:11

In Java wie in Obj-C bekomme ich den gleichen Wert für prime = -2128831035 In Java, wenn ich "0x811C9DC5L" setze bekomme ich Wert = 2166136261 – Dough

Sie sollten -2128831035 in Obj-C nicht erhalten. Sind Sie sicher, dass dies kein Artefakt dafür ist, wie Sie diesen Wert drucken? (d. h., haben Sie "% lld" oder "% d" in Ihrem "printf()" verwendet?) –

Und ein Hinweis, dass -2128831035 nicht der richtige Zahlenwert ist: es ist nicht prim! -2128831035 = - (3 * 5 * 17 * 101 * 82657) –

Sind die Zeichen in Java und Objective-c identisch? NSString gibt Ihnen Unichars.

Quelle

2010-05-18 10:59:29

Danke für Ihre Antwort! Char, in Java de Objective-Cn gibt den ASCII-Wert des Zeichens zurück. Für exemple: a = 97 b = 98 c = 99 d = 100 und so weiter! – Dough

@dough: Es verwendet definitiv kein ASCII, obwohl die ersten 127 Zeichen die gleichen Zahlenwerte haben können. Was bekommst du als Übung, wenn du den Buchstaben "fl" druckst? Und was ist der ASCII-Wert von 'fl'? –

'fl' ist kein Zeichen, es ist zwei: f und l! – Dough

Es ist ein Unterschied in der Vorzeichenerweiterung, die den 32-Bit-Wert 0x811C9DC5 einem 64-Bit-Var zuweist.

Quelle

2010-05-18 11:36:49

Es ist eigentlich. –

Übrigens ist 0x811C9DC5 nicht ein FNV-Prime (es ist nicht einmal Prime); es ist die 32-Bit-FNV- "Offset-Basis". Sie erhalten falsche Hash-Werte, wenn Sie diesen Wert (und mehr Hash-Kollisionen) verwenden. Der korrekte Wert für die 32-Bit-FNV-Primzahl ist 0x1000193.Siehe http://www.isthe.com/chongo/tech/comp/fnv/index.html

Quelle

2012-12-01 09:31:57 Rich

Ziel-C: Fowler-Noll-Vo (FNV) Hash-Implementierung

Antwort

Verwandte Themen