A Priori hat eine Primzahlgrösse keine Vorteile, es hängt von den verwendeten Hashfunktionen ab.
Aufgabe einer guten Hashfunktion ist es, die vorhandenen Daten möglichst gleichmässig auf die Hashtabelle aufzuteilen, damit nicht an manchen Hashfunktionswerten viele Datensätze hängen und an anderen keine. Es gibt Algorithmen, die für eine optimale Verteilung primzahl-grosse Tabellen brauchen (ist schon lange her, dass ich mich bei meinem Studium am Rande damit beschäftigt habe). Wenn aber keine derartige Hashfunktion verwendet wird, kann u.U. eine unrunde Hashtabellengrösse sogar Nachteile hinsichtlich der gleichmässigen Verteilung bringen.
edit: Ich glaube, mich zu erinnern, dass das aber nur ein Thema ist, wenn eine "Familie" von Hashfunktionen verwendet wird, um die Erzeugung von Listen zu vermeiden: Bei einer Kollision wird nicht an dem Knoten eine Liste gebildet, sondern mit Hilfe von weiteren Hashfunktionen nach einem freien Platz in der Hashtabelle gesucht. Solche "Hashfunktionsfamilien" brauchen oft primzahlgrosse Tabellen, um zu verhindern, dass "Ballungen" von Werten entstehen, die sich negativ auf die Performance auswirken.
edit 2: Weil mich das Thema Hashtabellen zufällig gerade auch betrifft, habe ich ein bisschen nachgeforscht und einen ganz interessanten Link:
http://www.partow.net/programming/hashfunctions/ [
OT: warum mir der Editor die
URL-Tags nicht anbietet, versteh ich nicht] gefunden. Es zahlt sich aus, sich das anzuschauen, wenn man in das Thema einsteigen will.