Java/src/main/java/com/search/BloomFilter.java at Development · iDev-git/Java · GitHub

Repository navigation

History

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

package com.search;

import java.io.Serializable;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.function.Function;

/**

* A simple implementation of Bloom filter.

* <p>

* Bloom filter have a chance of being wrong.

* <p>

* The Bloom filter assert that elements that do not exist must not exist,

* if assert an element exists, but not necessarily.

* <p>

* The accuracy rate depends on capacity and hash functions.

public class BloomFilter implements Serializable {

private static final long serialVersionUID = -4466610350741278658L;

private static final int LONG_SHIFT = 6;

private static final int LONG_MASK = 63;

/**

* hash functions

private final List<Function<String, Integer>> hashFunctions;

private final long[] table;

private final int tableMask;

private int size;

/**

* @param capacity the filter capacity

* @param hashFunctions hash functions

* @see Builder must be build by {@link Builder}.

private BloomFilter(int capacity, List<Function<String, Integer>> hashFunctions) {

this.hashFunctions = hashFunctions;

int cap = nextPowerOf2(capacity);

tableMask = (cap << LONG_SHIFT) - 1;

table = new long[cap];

}

public static Builder builder(int capacity) {

if (capacity < 1) {

throw new IllegalStateException("capacity must be > 0");

}

return new Builder(capacity);

}

/**

* Add an element to the Bloom filter.

public void add(String element) {

checkNotNull(element, "element");

for (Function<String, Integer> hashFunction : hashFunctions) {

int key = hashFunction.apply(element) & tableMask;

table[key >>> LONG_SHIFT] |= (1 << (key & LONG_MASK));

}

size++;

}

/**

* @return true if the element exists, otherwise false.

public boolean contains(String element) {

if (element == null) {

return false;

}

for (Function<String, Integer> hashFunction : hashFunctions) {

int key = hashFunction.apply(element) & tableMask;

if ((table[key >>> LONG_SHIFT] & (1 << (key & LONG_MASK))) == 0) {

return false;

}

return true;

}

public List<Function<String, Integer>> getHashFunctions() {

return hashFunctions;

}

public int size() {

return size;

}

private static void checkNotNull(String element, String msg) {

if (element == null) {

throw new NullPointerException(msg + " must be not null");

}

private static int nextPowerOf2(int i) {

int n = i - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= 0x40000000) ? 0x40000000 : n + 1;

}

/**

* We need a list of unmodifiable hash functions.

public static class Builder {

private int capacity;

private List<Function<String, Integer>> hashFunctions = new ArrayList<>();

private Builder(int capacity) {

this.capacity = capacity;

}

public Builder addHashFunction(Function<String, Integer> function) {

hashFunctions.add(function);

return this;

}

public BloomFilter build() {

if (hashFunctions.isEmpty()) {

addDefaultHashFunction();

}

return new BloomFilter(capacity, Collections.unmodifiableList(hashFunctions));

}

/**

* I provides several default hash functions

private void addDefaultHashFunction() {

// Java String Hash Function

hashFunctions.add(String::hashCode);

// SDBM Hash Function

hashFunctions.add(key -> {

if (key == null || key.isEmpty()) {

return 0;

}

int hash = 0;

for (int i = 0; i < key.length(); i++) {

hash = key.charAt(i) + (hash << 6) + (hash << 16) - hash;

}

hash &= 0x7ffffff;

return hash;

});

// Robert Sedgwicks Hash Function

hashFunctions.add(key -> {

if (key == null || key.isEmpty()) {

return 0;

}

int hash = 0;

int magic = 63689;

for (int i = 0; i < key.length(); i++) {

hash = hash * magic + key.charAt(i);

magic *= 378551;

}

return hash;

});

// Arash Partow Hash Function

hashFunctions.add(key -> {

if (key == null || key.isEmpty()) {

return 0;

}

int hash = 0;

for (int i = 0; i < key.length(); i++) {

char ch = key.charAt(i);

if ((i & 1) == 0) {

hash ^= ((hash << 7) ^ ch ^ (hash >> 3));

} else {

hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));

}

return hash;

});

}

Java/src/main/java/com/search/BloomFilter.java at Development · iDev-git/Java · GitHub

Repository navigation

Expand file tree

Breadcrumbs

BloomFilter.java

Latest commit

History

Breadcrumbs

BloomFilter.java

File metadata and controls