-
Notifications
You must be signed in to change notification settings - Fork 5k
/
Contents.swift
82 lines (62 loc) · 2.06 KB
/
Contents.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//: Playground - noun: a place where people can play
public class BloomFilter<T> {
fileprivate var array: [Bool]
private var hashFunctions: [(T) -> Int]
public init(size: Int = 1024, hashFunctions: [(T) -> Int]) {
self.array = [Bool](repeating: false, count: size)
self.hashFunctions = hashFunctions
}
private func computeHashes(_ value: T) -> [Int] {
return hashFunctions.map { hashFunc in abs(hashFunc(value) % array.count) }
}
public func insert(_ element: T) {
for hashValue in computeHashes(element) {
array[hashValue] = true
}
}
public func insert(_ values: [T]) {
for value in values {
insert(value)
}
}
public func query(_ value: T) -> Bool {
let hashValues = computeHashes(value)
// Map hashes to indices in the Bloom Filter
let results = hashValues.map { hashValue in array[hashValue] }
// All values must be 'true' for the query to return true
// This does NOT imply that the value is in the Bloom filter,
// only that it may be. If the query returns false, however,
// you can be certain that the value was not added.
let exists = results.reduce(true, { $0 && $1 })
return exists
}
public func isEmpty() -> Bool {
// As soon as the reduction hits a 'true' value, the && condition will fail.
return array.reduce(true) { prev, next in prev && !next }
}
}
/* Two hash functions, adapted from http://www.cse.yorku.ca/~oz/hash.html */
func djb2(x: String) -> Int {
var hash = 5381
for char in x {
hash = ((hash << 5) &+ hash) &+ char.hashValue
}
return Int(hash)
}
func sdbm(x: String) -> Int {
var hash = 0
for char in x {
hash = char.hashValue &+ (hash << 6) &+ (hash << 16) &- hash
}
return Int(hash)
}
/* A simple test */
let bloom = BloomFilter<String>(size: 17, hashFunctions: [djb2, sdbm])
bloom.insert("Hello world!")
print(bloom.array)
bloom.query("Hello world!") // true
bloom.query("Hello WORLD") // false
bloom.insert("Bloom Filterz")
print(bloom.array)
bloom.query("Bloom Filterz") // true
bloom.query("Hello WORLD") // true