ip adressen hash berechnen

ne, das nicht, aber vllt. gibt es ja einen besonders guten.

ipsec

Welcher Einsatzzweck? IP-Adressen sind 32bit-Werte, für Hashtabellen o.ä. kann man also auch einfach den Wert selbst als Hash nehmen.

Edit: gilt natürlich nur für IPv4-Adressen.

EOP

ipsec schrieb:

Welcher Einsatzzweck? IP-Adressen sind 32bit-Werte, für Hashtabellen o.ä. kann man also auch einfach den Wert selbst als Hash nehmen.

Das war auch mein erster Gedanke als ich das heute Mittag las.

volkard

EOP schrieb:

ipsec schrieb:

Welcher Einsatzzweck? IP-Adressen sind 32bit-Werte, für Hashtabellen o.ä. kann man also auch einfach den Wert selbst als Hash nehmen.

Das war auch mein erster Gedanke als ich das heute Mittag las.

Meiner nicht. Ich dachte sofort an Knuths Multiplikation mit dem goldenen Schnitt.

Bei IP-Adressen ohne den Trick fürchte ich, daß folgender Effekt geschieht:
Viele Unternehmen reservieren sich 256 Adressen (oder eine andere Zweierpotenz). Und belegen zunächst davon 1,2,3 und so. Und viele Hashtables haben als natürliche Tabellengröße eine Zweierpotenz. Damit kommt es zu einer schlimmen Interferenz und Adressen mit 1,2,3 im Subnetz kollidieren dauernd. Und das wollen wir doch alle nicht.

Andererseits ist IP4 inzwischen so voll, daß wohl kaum noch eine Häufung vorne in Subnetzen ist. Und bei IP6 ist eh Zufälligkeit zu erwarten.

Ich würde die bis zu 8 Takte für die Multiplikation opfern, um auf der sicheren Seite zu sein. Wenn das Projekt läuft, kann man ja immernoch am laufenden System ausmessen, daß es ohne auch nicht spürbar mehr Kollissionen hat.

EOP

volkard schrieb:

EOP schrieb:

ipsec schrieb:

Welcher Einsatzzweck? IP-Adressen sind 32bit-Werte, für Hashtabellen o.ä. kann man also auch einfach den Wert selbst als Hash nehmen.

Das war auch mein erster Gedanke als ich das heute Mittag las.

Meiner nicht. Ich dachte sofort an Knuths Multiplikation mit dem goldenen Schnitt.

Deshalb bist du auch Mod.

Ich denke aber, daß der OP gar nicht auf so kritischen Feinheiten abzielen wollte.
IP -> inet_addr( IP ) und ab in ne std::map sollte ausreichen falls er nicht den ganzen IP4-space abbilden/durchsuchen will.

volkard schrieb:

Ich würde die bis zu 8 Takte für die Multiplikation opfern, um auf der sicheren Seite zu sein. Wenn das Projekt läuft, kann man ja immernoch am laufenden System ausmessen, daß es ohne auch nicht spürbar mehr Kollissionen hat.

Wenn's wirklich nur um IPv4 geht, würde ein Suchbaum mit der IP-Adresse als Suchschlüssel auch völlig ausreichen. Dann hat man (bei unterschiedlichen Adressen) garantiert keine Kollision.

volkard schrieb:

Viele Unternehmen reservieren sich 256 Adressen (oder eine andere Zweierpotenz). Und belegen zunächst davon 1,2,3 und so. Und viele Hashtables haben als natürliche Tabellengröße eine Zweierpotenz. Damit kommt es zu einer schlimmen Interferenz und Adressen mit 1,2,3 im Subnetz kollidieren dauernd.

Kannst du das mal genauer erklären? Kapier ich irgendwie nicht.

Für ein ordentliches IP Hack schneidet man die IP Adresse zuerst mit einem scharfen Messer in 16bit große Stücke. Anschliesend gibt man die Stücke in den XOR-Mixer. Das IP Hack kühl lagern bis es verwendet wird.

mezzo mix

hashnoob schrieb:

volkard schrieb:

Viele Unternehmen reservieren sich 256 Adressen (oder eine andere Zweierpotenz). Und belegen zunächst davon 1,2,3 und so. Und viele Hashtables haben als natürliche Tabellengröße eine Zweierpotenz. Damit kommt es zu einer schlimmen Interferenz und Adressen mit 1,2,3 im Subnetz kollidieren dauernd.

Kannst du das mal genauer erklären? Kapier ich irgendwie nicht.

subnetze koennen nur in der groesse von 2er potenzen vergeben werden. und dann wird gerne einfach bei eins angefangen und hochgezaehlt.

1.1.1.0/24 bedeutet du darfst die null durch eine zahl von 1 bis 254 frei waehlen.
1.1.2.0/24 siehe oben
es wird gerne von 1 hochgezaehlt.
oder sind die kollisionen an sich dein verstaendnissproblem?

mezzo mix schrieb:

oder sind die kollisionen an sich dein verstaendnissproblem?

Ja, genau.

Hashes sind doch so gut wie eindeutig?! Auch wenn sich nur eine Ziffer unterscheidet, nicht?
Was soll da kollidieren?