kompakte Datenstruktur wie set

Question

Ich bin auf der Suche nach einer bestimmten Datenstruktur, aber ich vergaß seinen Namen. wenn ich den Namen wusste, dass es trivial sein, ich würde es nur in Wikipedia nachschlagen:)

im Grunde ist es wie ein Satz - außer Sie es nicht laufen können

.

Sie setzen einige Werte in es, sagen wir 80k Postleitzahlen.

, dann können Sie testen, ob eine bestimmte Zeichenfolge definitiv Code nicht ein Reißverschluss ist, aber Sie werden schließlich Fehlalarme auslösen, wenn Sie zu viele Postleitzahlen einfügen.

der Speicherverbrauch dieser Struktur ist ziemlich klein.

was ist sein Name, und gibt es eine Implementierung in Java?

Answer 1

Ich glaube, Sie suchen nach einem Bloom Filter .

Hier ist eine Java-Implementierung .

Answer 2

Ich glaube, Sie bedeuten eine Bloom filtern . Hier ein basiert auf Java BitSet.