Hash - Primzahl

[darkmasta]

Hallo!

In der letzten technische Informatikvorlesung behandelten wir Hash-tables.

Als hashfunktion die modulo. der Professor meinte, dass als Divisor eine Primzahl verwendet werden soll, da damit weniger kollisionen auftreten.

Das kann ich mir nicht vorstellen, daher wollte ich das mit einem Programm überprüfen. damit entstand aber nicht das zu erwatete ergebniss: verteilung war bei primzahl/nichtprimzahl gleich

Code:

import java.util.Random;
import java.util.*;
/*
 * verteilung.java
 *
 * Created on 8. Mai 2008, 13:17
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

/**
 *
 * @author kj
 */
public class verteilung {
    
    /** Creates a new instance of verteilung */
    public verteilung() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application lo
        int i,f;
        int[] a= new int [50];
        int z=50;
        int[] b= new int [53];
        int x=53;
        // 0 - 49999
        for (i=0;i<1000*z;i++){
            f=(int) ( (int)(Math.random()*1000*z)  % z);
            a[f]+=1;
        }
        Arrays.sort(a,0,50);
       
        for (i=0;i<1000*x;i++){
            f=(int) ( (int)(Math.random()*1000*x)  % x);
            b[f]+=1;
        }
        Arrays.sort(b,0,53);
        
        for(i=0; i < 50;i++){
            System.out.println(a[i]+ "   " +b[i]);
        }
        System.out.println("   "+b[50]);
        System.out.println("   "+b[51]);
        System.out.println("   "+b[52]);
    }
    
}

ist das Programm falsch?
kennt jemand einen mathematischen Hintergrund??

Hab meinen Infoprofessor darauf angesprochen, dieser hat das auch noch nie überprüft und weiß auch keine Antwort! o_o

mfg
J.K.

[dead_orc]

Ich verstehe kein Wort.
Das Programm ist mir irgendwie zu konfus.

Ich weiß nicht genau, ob das deine Frage beantwortet, aber ich hoffe es einfach mal: Im Bezug auf die Multiplikationschiffre, bei der auch eine Modulorechnung benutzt wird ([Klartextbuchstabe * Schlüssel] % Alphabetlänge = Cryptobuchstabe), ist es sinnvoll eine Primzahl als Schlüssel zu benutzen, weil Schlüssel und Alphabetlänge teilerfremd sein müssen - was bei einer Primzahl bei fast allen Zahlen gegeben ist. Andernfalls lässt sich kein multiplikatives Inverses finden, mit der die Verschlüsselung umgekehrt werden kann. Ein Hash soll zwar nicht umgekehrt werden - weshalb man auch kein multiplikatives Inverses braucht - aber IIRC wird dadurch auch die Eindeutigkeit der Projektion (der verschlüsselten Botschaft) nicht sichergestellt.

[darkmasta]

sry, ich glaub ich hab mich unklar ausgedrückt:

es geht nicht um verschlüsselung, da sind primzahlen klar:

es geht um die ... ähm ... "transformierung" von einem großen wertebereich in einen kleinen, um die suche schneller zu gestalten, natürlich treten dabei kollisioen (gleiche werte) auf. um diese aber möglichst gleichmäßig zu verteilen sind primzahlen hilfreich. diese methode ist auch in fachbüchern angegeben, leider keine erklärung.

[Kiru]

Eventuell macht folgendes Probleme...

f=(int) ( (int)(Math.random()*1000*z) % z);

Dabei erzeugt Math.random eine pseudozufällige double-Zahl.

(x*y)%y=x ist natürlich immer der Fall. Klar, wenn man etwas mit y multipliziert und es danach wieder durch y dividiert, kann es keinen Rest geben, solange x ein ganzzahliger Wert ist. (und y natürlich auch)

Bsp: 3,1416*1000=3141,6
Als Rest ergeben sich die Nachkommastellen ab der 4ten,denn:
3141z+0,6z=3141,6 z

Das casten auf (int) hackt da noch ein wenig bei ab, was die Nachkommastellen etwas verfälscht, aber ich denke trotzdem, dass hier das z bei der Implementierung ganz egal ist. ((x*z) %z benutzt man eben um z.B. Nachkommastellen von x zu erhalten)

So, ich hoffe ich hab mich nun hier nicht noch bei irgendwas verhauen^^

[MagicMagor]

Ich glaube ich habe eine Ahnung was der mathematische Hintergrund davon ist, danach hattest du ja gefragt.

Grundsätzlich liefert die Modulo-Funktion ja den ganzzahligen Rest bei einer Division zweier ganzen Zahlen.
Dadurch läßt sich jede ganze Zahl durch modulo p auf ihren Rest abbilden. (p ist dein Divisor, im Prinzip eine zufällig gewählte ganze Zahl).

Wenn p jetzt eine Primzahl ist, hat deine Menge von Restklassen (bzw. die Reste, auf die du jede ganze Zahl abbildest) einige nette Eigenschaften, genau genommen bildet Z faktorisiert durch p dann einen Körper.
Die wichtigste Eigenschaft ist hierbei zum einen die Nullteilerfreiheit, wenn a*b = 0 gilt muss a oder b = 0 sein. Ist p keine Primzahl so ist dies nicht der Fall.
(Bspw bei Z modulo 6 gilt: 2*3 = 0 da 2*3 = 6 ist welches geteilt durch 6 den Rest 0 hat.)
Auch weiß man, das bei einem Körper die multiplikativ Inversen zu jeder Zahl ungleich 0 existieren und eindeutig sind. Dadurch kann man Gleichungen sehr viel einfacher lösen.

Ich denke diese Eigenschaften spielen bei der Verschlüsselung eine wichtige Rolle, weswegen man als Divisor eine Primzahl nimmt.