Algorithmen und Datenstrukturen · Senior · Frage 9 von 75
Was kann ein Bloom-Filter über einen Schlüssel sagen?
- 1„Sicher nicht vorhanden“ oder „vielleicht vorhanden“
- 2„Sicher vorhanden“ oder „vielleicht nicht vorhanden“
- 3Die genaue Zahl, wie oft er eingefügt wurde
Antwort zeigen
Richtige Antwort: „Sicher nicht vorhanden“ oder „vielleicht vorhanden“
Erklärung
Er setzt pro Schlüssel k Bits mit k Hashfunktionen. Ist ein Bit 0, wurde der Schlüssel nie hinzugefügt; sind alle 1, kann es ein falsch Positiver sein. Er liefert nie falsch Negative und braucht wenige Bits pro Schlüssel, deshalb nutzen Datenbanken ihn, um Plattenzugriffe zu sparen.