-
Notifications
You must be signed in to change notification settings - Fork 5k
/
BloomFilterTests.swift
76 lines (50 loc) · 1.62 KB
/
BloomFilterTests.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
import XCTest
/* 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.characters {
hash = ((hash << 5) &+ hash) &+ char.hashValue
}
return Int(hash)
}
func sdbm(_ x: String) -> Int {
var hash = 0
for char in x.characters {
hash = char.hashValue &+ (hash << 6) &+ (hash << 16) &- hash
}
return Int(hash)
}
class BloomFilterTests: XCTestCase {
func testSingleHashFunction() {
let bloom = BloomFilter<String>(hashFunctions: [djb2])
bloom.insert("Hello world!")
let result_good = bloom.query("Hello world!")
let result_bad = bloom.query("Hello world")
XCTAssertTrue(result_good)
XCTAssertFalse(result_bad)
}
func testEmptyFilter() {
let bloom = BloomFilter<String>(hashFunctions: [djb2])
let empty = bloom.isEmpty()
XCTAssertTrue(empty)
}
func testMultipleHashFunctions() {
let bloom = BloomFilter<String>(hashFunctions: [djb2, sdbm])
bloom.insert("Hello world!")
let result_good = bloom.query("Hello world!")
let result_bad = bloom.query("Hello world")
XCTAssertTrue(result_good)
XCTAssertFalse(result_bad)
}
func testFalsePositive() {
let bloom = BloomFilter<String>(size: 5, hashFunctions: [djb2, sdbm])
bloom.insert(["hello", "elloh", "llohe", "lohel", "ohell"])
print("Inserted")
let query = bloom.query("This wasn't inserted!")
// This is true even though we did not insert the value in the Bloom filter;
// the Bloom filter is capable of producing false positives but NOT
// false negatives.
XCTAssertTrue(query)
}
}