Last active
August 29, 2015 14:17
-
-
Save lizhongz/3a970a5da0e856bf4b3e to your computer and use it in GitHub Desktop.
A simple bloom filter written for learning Cassandra
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
This code is written for learning Cassandra's key-value storage, | |
where Bloom Filter is used to check the existence of a key in a replica. | |
*/ | |
package main | |
import "fmt" | |
import "math" | |
/* | |
Hash calculates the posion of a given key in bitmap. | |
the hash function: (key^2 + key^3) * i mod m, where | |
- i is the ith hash function | |
- m is bitmap size. e.g. m=64, the bitmap is 64 bits | |
*/ | |
func Hash(key float64, i float64, m float64) int64 { | |
val := int64((math.Pow(key, 2) + math.Pow(key, 3)) * i) % int64(m) | |
return val | |
} | |
/* | |
Hash_a calculates the posion of a given key in bitmap. | |
the hash function: (key^2 + key^3) * i mod m, where | |
- i is the ith hash function | |
- m is bitmap size. e.g. m=64, the bitmap is 64 bits | |
*/ | |
func Hash_a(key float64, i float64, m float64) int64 { | |
val := int64(key * i) % int64(m) | |
return val | |
} | |
func main() { | |
// An example of using Bloom Filter | |
m := 64.0 | |
keys := []float64{1975, 1985, 1995, 2005, 2015} | |
for _, k := range keys { | |
pos1 := Hash_a(k, 1, m) | |
pos2 := Hash_a(k, 2, m) | |
fmt.Printf("key %f's positions: %d, %d\n", k, pos1, pos2) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment