: Bloom filter is a data structure for testing whether an element is a member of a set. An empty Bloom filter is a bit array of m bits, all set to 0.

There are also given k different (hash) functions hi , 1 i k, each of which maps (or hashes) some set element to one of the m array positions. To add an element s, the bits with positions h1(s), h2(s), . . . , hk(s) are set to 1. To test whether an element x belongs to a set, we first compute positions h1(x), h2(x), . . . , hk(x).

If any of the bits at these positions is 0, the element x does not belong to the set. Otherwise, x belongs to the set.

You should implement the Bloom filter. You can follow the following instructions: - In our case, the elements are strings. - In our case, the array consists of logic values true and false. - in the class Naloga you should implement the constructor Naloga(int velikost, int k). The parameter velikost defines the size of the array, while the parameter k defines the number of (hash) functions. 1 - In the class Naloga you should implement the following methods:

(i) clear(), which sets all values in the array to false;

(ii) add(String input), which gets a string and adds it to the set;

(iii) contains(String input), which gets a string and tests whether it belongs to the set. The method returns true, if the string belongs to the set, and false otherwise.

- You do not need to implement hash functions. For this purpose, there is already implemented the method createHashes(byte[] data, int hashes). You should only take care that you first encode/translate the string you would like to map with a (hash) function to a sequences of bytes using the method getBytes(). The method createHashes for a given string, encoded as byte[] data, and an integer hashes, representing the number of (hash) functions, returns an array of length hashes that represents the positions in the array.

import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.util.Arrays; import java.util.BitSet;

import org.omg.CosNaming.NamingContextExtPackage.AddressHelper;

public class Naloga { boolean[] podatki; String hashName = "MD5"; final MessageDigest digestFunc; int k; int velikost; public Naloga(int velikost, int k) { MessageDigest tmp; try { tmp = java.security.MessageDigest.getInstance(hashName); } catch (NoSuchAlgorithmException e) { tmp = null; } digestFunc = tmp; } public void clear() { throw new UnsupportedOperationException("need to implement"); } public void add(String input) { throw new UnsupportedOperationException("need to implement"); } public boolean contains(String input) { throw new UnsupportedOperationException("need to implement"); } public int[] createHashes(byte[] data, int hashes) { int[] result = new int[hashes];

int k = 0; while (k < hashes) { byte[] digest; digest = digestFunc.digest(data); for (int i = 0, j = 0; i < digest.length && k < hashes; i+=2, j++) { result[j] = Math.abs(((int)digest[i] << 8) | ((int)digest[i+1] & 0xFF))%velikost; k++; } } return result; } }