1 package net.obsearch.index.bucket;
2
3 import java.io.Serializable;
4 import java.util.BitSet;
5 import java.util.Collection;
6 import java.util.Iterator;
7 import java.util.Random;
8 import java.util.Set;
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 public class SimpleBloomFilter<E> implements Set<E>, Serializable {
28 private static final long serialVersionUID = 3527833617516722215L;
29 protected int k;
30 BitSet bitSet;
31 int bitArraySize, expectedElements;
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 public SimpleBloomFilter(int bitArraySize, int expectedElements) {
48 this.bitArraySize = bitArraySize;
49 this.expectedElements = expectedElements;
50 this.k = (int) Math.ceil((bitArraySize / expectedElements)
51 * Math.log(2.0));
52 bitSet = new BitSet(bitArraySize);
53 }
54
55
56
57
58
59
60
61
62 public double expectedFalsePositiveProbability() {
63 return Math.pow((1 - Math.exp(-k * (double) expectedElements
64 / (double) bitArraySize)), k);
65 }
66
67
68
69
70
71
72 public boolean add(E o) {
73 Random r = new Random(o.hashCode());
74 for (int x = 0; x < k; x++) {
75 bitSet.set(r.nextInt(bitArraySize), true);
76 }
77 return false;
78 }
79
80
81
82
83 public boolean addAll(Collection<? extends E> c) {
84 for (E o : c) {
85 add(o);
86 }
87 return false;
88 }
89
90
91
92
93 public void clear() {
94 for (int x = 0; x < bitSet.length(); x++) {
95 bitSet.set(x, false);
96 }
97 }
98
99
100
101
102
103
104 public boolean contains(Object o) {
105 Random r = new Random(o.hashCode());
106 for (int x = 0; x < k; x++) {
107 if (!bitSet.get(r.nextInt(bitArraySize)))
108 return false;
109 }
110 return true;
111 }
112
113 public boolean containsAll(Collection<?> c) {
114 for (Object o : c) {
115 if (!contains(o))
116 return false;
117 }
118 return true;
119 }
120
121
122
123
124 public boolean isEmpty() {
125 throw new UnsupportedOperationException();
126 }
127
128
129
130
131 public Iterator<E> iterator() {
132 throw new UnsupportedOperationException();
133 }
134
135
136
137
138 public boolean remove(Object o) {
139 throw new UnsupportedOperationException();
140 }
141
142
143
144
145 public boolean removeAll(Collection<?> c) {
146 throw new UnsupportedOperationException();
147 }
148
149
150
151
152 public boolean retainAll(Collection<?> c) {
153 throw new UnsupportedOperationException();
154 }
155
156
157
158
159 public int size() {
160 throw new UnsupportedOperationException();
161 }
162
163
164
165
166 public Object[] toArray() {
167 throw new UnsupportedOperationException();
168 }
169
170
171
172
173 public <T> T[] toArray(T[] a) {
174 throw new UnsupportedOperationException();
175 }
176 }