Hash-Bereiche erstellen die gleichverteilt sind..?

[sirbender]

Hi,

ich erinnere mich dass man z.B. aus einem byte[] Hashes in Java erstellen kann. In einem naechsten Schritt wuerde ich gerne etwas mit den Hashes anstellen was jedoch nicht so wichtig sein soll. Was wichtig ist, ist dass ich die Hashes in Bins sortieren will. Sagen wird 10 Bins. Jedem Bin ist ein Thread zugeordnet der solbald Hashes vorliegen diese herrausnimmt und etwas damit macht. Die Hash-Bereiche fuer jedes Bin sollten so gewaehlt werden, dass in jedes Bin ca. gleich viele Hashes einsortiert werden und somit jeder Thread ungefaehr gleich viel zu tun hat.

1. Kann mit jemand eine Hash-Generierungsmethode vorschlagen. Eventuell Codebeispiel.
2. Wie kann ich diese Bins bzw. Hash-Bereiche erstellen. Wenn die Hashes aus einer Ziffer bestuenden (0-9) waere es einfach. Aber ich denke mal Hashes sind komplizierter und vielleicht nicht so einfach in Bereiche aufzuteilen die dann 'gleich verteilt' sind?

Danke,
sb

 

[SlaterB]

sei n Anzahl der Bins,
dann bilde die Summe über alle bytes[] im Array (oder nur der ersten x Elemente) und moduliere durch n, fertig

Beispiel: n = 10, ganz sparsam nur aufs erste byte
byte[] a = {133, 45, 65,23} -> 133 % 10 = 3
byte[] b = {-34, 65, 23} -> -34 % 10 = 6 (in Java -4, vorher ne hohe Zahl drauaddieren um sicher zu gehen)

könnte schon reichen, je nach Anforderung kannst du es komplizierter machen,
wenn das erste byte nicht zufällig genug ist dann wie gesagt Summe aller bytes,

wenn ärgerlicherweise die letzte Ziffer immer konstant sein sollte und die Anzahl bytes auch, dann ist modulo nicht so gut,
dann eben die Quersumme der Summe und dieses modulo n, wobei dann darauf achten ob n nicht viel zu hoch ist, und nur die niedrigen Bereiche drankommen,
na jetzt rate ich, für schwieriges gibts auch sicher irgendwo geeignetes
Hash function - Wikipedia, the free encyclopedia

> Wenn die Hashes aus einer Ziffer bestuenden (0-9) waere es einfach.
> Aber ich denke mal Hashes sind komplizierter und vielleicht nicht so einfach in Bereiche aufzuteilen die dann 'gleich verteilt' sind?

doch doch, jede gute Hashfunktion sollte in ihrem Bereich komplett zufällig sein, wenn nur 0 bis x mit x < n, dann nicht zu gebrauchen,
ansonsten kannst du immer % n oder ähnliches rechnen
(edit: und ziemlich spät fällt mir da immer ein Haken ein: Verteilung 0-9 gegeben, benötigt ist 0-6, also % 7, dann wären Wert 0, 1 und 2 doppelt so häufig vertreten wie die anderen)

so wie die Summe aller Bytes bzw. auch nur das erste Byte für sich pauschal erstmal ein normal-ordentlicher kürzerer Hash ist, wenn denn komplett zufällig, und % n komprimiert nur in kleineren Bereich

Java String verwendet

    /**
     * Returns a hash code for this string. The hash code for a
     * <code>String</code> object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using <code>int</code> arithmetic, where <code>s[i]</code> is the
     * <i>i</i>th character of the string, <code>n</code> is the length of
     * the string, and <code>^</code> indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    public int hashCode() {
	int h = hash;
	if (h == 0) {
	    int off = offset;
	    char val[] = value;
	    int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

 

[Marco13]

Soweit ich mich erinnere, ist das nicht allgemein möglich. Es gibt ja keine "für jeden Fall perfekte" Hashfunktion. Man könnte jetzt sagen: "Joa, mach jeweils 4 bytes zu einem int und verXORe die dann (vielleicht noch mit irgendeiner primzahl reingemischt)" - das dürfte schon "gute" Ergebnisse liefern, aber: Wenn man 100 Elemente auf 10 Stellen abbilden will, und die gleichverteilt sein sollen, dann liegen in jedem bin 10 Elemente - es könnte also auch sein, dass man 10 Elemente in den Hash legt, das "zufällig" genau die 10 sind, die alle im gleichen Bin landen.

Der Beschreibung nach klingt das IMHO, als könnte da eine gemeinsame BlockingQueue für alle Threads geeigneter sein: Wenn etwas in der Queue liegt, holt sich der Thread, der gerade Zeit hat, etwas heraus (und ansonsten wartet er). Damit kann man sehr leicht 10 Threads "beschäftigt halten". Wenn es nur um eine gleichmäßige Verteilung an sich geht, könnte man (entweder brute force, oder mit irgendwas heap-artigem im Hintergrund) etwas machen, was darauf rausläuft, dass immer ein Element in das Bin gelegt wird, das im Moment die wenigsten Elemente enthält.

 

[sirbender]

Die Summe koennte ich ja auch aus dem Hash selbst bilden, oder? Ich muss mir das mit dem Modulo mal anschauen...aber ich denke mal mit der Methode kann man dann auch einfach eindeutige Bereiche fuer 3, 12, 37 oder 337 Bins erstellen?

Danke,
sb

 

[SlaterB]

hab oben edit eingefügt:

doch doch, jede gute Hashfunktion sollte in ihrem Bereich komplett zufällig sein, wenn nur 0 bis x mit x < n, dann nicht zu gebrauchen,
ansonsten kannst du immer % n oder ähnliches rechnen
(edit: und ziemlich spät fällt mir da immer ein Haken ein: Verteilung 0-9 gegeben, benötigt ist 0-6, also % 7, dann wären Wert 0, 1 und 2 doppelt so häufig vertreten wie die anderen)

das muss man im Grunde überall beachten und macht es dann doch nicht mehr so leicht wenn man extreme Gleichverteilung möchte,
ein positives byte hat einen Wertebereich von 0-127, dort % 10 berechtet haben die 8 und 9 eine ca. 8% geringere Wahrscheinlichkeit als 0-7

public class Test {
    public static void main(String[] args)  {
        test(100);
        test(128);
    }

    private static void test(int max)  {
        int[] k = new int[10];
        Random r = new Random();
        for (int i = 0; i < 1000000; i++)   {
            int b = r.nextInt(max);
            k[b % 10]++;
        }
        System.out.println(Arrays.toString(k));
    }
}

Ausgabe:

[100544, 100125, 99941, 99777, 99643, 100385, 99733, 100057, 100095, 99700]
-> Zufallszahl 0-99, alle Ziffern etwa gleich um 100.000

[100907, 101734, 101472, 101818, 102050, 101566, 101537, 101782, 93546, 93588]
-> Zufallszahl 0-127, die letzten beiden deutlich kleiner

------

wenn man viele bytes aufaddiert wird der Fehler % 10 marginal,
wenn dagegen n auf 300 steigt dann wirds wieder spannender..

dagegen gibts auch ein Mittel, mal sehen ob es mir wieder einfällt oder es jemand anders postet oder bei Wiki schon steht

edit: bei der Zufallszahlermittlung und Abbildung auf einen kleineren Bereich kann man einfach zu hohe Zufallszahlen ignorieren,
bei 0-127 also neue Zufallszahlen >= 120 verwerfen und nur solche unter 120 nehmen, die % 10 wären dann gleichverteilt,
für Hash mit fest gegebenen Zahlen ist das nicht so hilfreich..

 

[sirbender]

Soweit ich mich erinnere, ist das nicht allgemein möglich. Es gibt ja keine "für jeden Fall perfekte" Hashfunktion. Man könnte jetzt sagen: "Joa, mach jeweils 4 bytes zu einem int und verXORe die dann (vielleicht noch mit irgendeiner primzahl reingemischt)" - das dürfte schon "gute" Ergebnisse liefern, aber: Wenn man 100 Elemente auf 10 Stellen abbilden will, und die gleichverteilt sein sollen, dann liegen in jedem bin 10 Elemente - es könnte also auch sein, dass man 10 Elemente in den Hash legt, das "zufällig" genau die 10 sind, die alle im gleichen Bin landen.

Hmmm...ich weiss nicht ob ich genau kapiert habe was du damit meinst. Warum sind die nicht gleichverteilt?

Der Beschreibung nach klingt das IMHO, als könnte da eine gemeinsame BlockingQueue für alle Threads geeigneter sein: Wenn etwas in der Queue liegt, holt sich der Thread, der gerade Zeit hat, etwas heraus (und ansonsten wartet er). Damit kann man sehr leicht 10 Threads "beschäftigt halten". Wenn es nur um eine gleichmäßige Verteilung an sich geht, könnte man (entweder brute force, oder mit irgendwas heap-artigem im Hintergrund) etwas machen, was darauf rausläuft, dass immer ein Element in das Bin gelegt wird, das im Moment die wenigsten Elemente enthält.

Danke erstmal fuer die Antwort. Ich habe eigentlich gar keine Threads oder einen Threadpool. Das war nur ein Beispiel um das Problem leichter verstaendlich zu machen.

Das Problem ist das ich:
1. diese genaue Zuordnung zu einem bestimmten Bin fuer einen gegebenen Hash brauche und
2. das die Hashes sehr ebenmaessig gefuellt sein muessen. Ganz kleine Abweichungen sind glaube ich ok.

Vielleicht kann ja jemand eine Methode nenen die dieses Problem am ehesten loest. Ich koennte dann ein paar Tests machen und schauen ob es fuer meine Zwecke ausreicht.

 

[SlaterB]

es sollte wohl heißen 'wenn man 60x würfelt (Hash teilweise genauso zufällig) erhält man nicht genau 10x eine 1, 10x eine 2 usw. sondern je nach Zufall auch 60x dieselbe Zahl'

wenn du also ein Einträge so verteilen willst, dass überall gleich viele sind, dann mach das einen Eintrag nach dem anderen,
nicht abhängig von einer Hashfunktion mit unbekannten Ausgang

 

[Marco13]

Jein - das Problem ist ja sozusagen, dass der Hashwert eben NICHT zufällig ist. Egal, wie man die Hashfunktion definiert, um 100 Elemente gleichmäßig auf 10 Bins zu verteilen: Es gibt immer 10 Elemente, die im gleichen Bin landen, und wenn man nun zufällig gerade diese 10 Elemente behandeln muss, landen sie im gleichen Bin. Wie "gut" eine Hashfunktion in diesem Sinne ist, hängt also nicht nur von der Hashfunktion, sondern auch gleichermaßen von den zu hashenden Daten ab. Oder als Plakativbeispiel:

for (int i=0; i<100; i++)
{
    byte data[] = new byte[123]; // Enthält nur Nullen...
    int magicHashIndex = computeHash(data);
    store(magicHashIndex, data);
}

Wie muss die "computeHash"-Methode aussehen, damit in diesem Beispiel genau 10 verschiedene indizes rauskommen? (Es würde schon reichen, wenn du sagen könntest, wie sie aussehen müßte, damit ZWEI verschiedene indizes rauskommen ohne ein System.identityHashCode(data) geht da nicht viel...)

EDIT: So als Nachtrag: Wenn man von Anfang an ALLE datensätze hätte, könnte man da natürlich was machen - aber dann würde man für die Implementierung dieser HashMap wohl sowas wie eine HashMap verwenden (klingt absurd, könnte aber Sinn machen - je nachdem, worum es da genau geht...)

 

[sirbender]

Ok. Ich glaube wir reden aneinander vorbei.

1. Ich moechte eine standardtisierte Hashmethode nutzen die auch z.B. bei Javascript verfuegbar ist. Ich will nicht meine eigene Hashmethode stricken. Auch sollte sie auch nur bei leicht unterschiedlichen (z.B. swap von 2 Elementen) byte[] unterschiedliche Hashes erzeugen. Bei identischen byte[] soll aber immer der gleiche Hash erzeugt werden.

2. Nehmen wir an ein Hash besteht aus einer Zahl mit 5 Ziffern, also: 01234, 43210, 94387, usw. Da waere die Einteilung in 10 Bins sehr simpel. Bin 1 kriegt Hashes von 0000 bis 10000, usw.
Ich nehme mal stark an dass bei byte[] die mit Zufallszahlen gefuellt werden dann auch die Verteilung der Hashes auf die Bins recht gleichmaessig waere, oder? Oder wuerde die Hashfunktion bestimmt Wertebereiche, also Bins bevorzugen?


Danke,
sb