1

我在布隆过滤器中实现了一个简单的哈希过程。如何使用冲突实现相同的过程？

这是我已经实现的Haskell代码：</p> 

module testbloom where 
data HashTable = HashTable { location :: Int,  value :: [Int] } 
data HashFunction = HashFunction { hashfunction :: HashTable -> Int -> Int } 
data BloomFilter = BloomFilter { hashF :: [HashFunction], table :: HashTable } 

hashtable :: Int -> HashTable 
hashtable loc = HashTable { location = loc, value = replicate loc 0 } 

setbloom :: BloomFilter 
setbloom = BloomFilter { hashF = [defaultfunction], table = hashtable 32 } 

defaultfunction :: HashFunction 
defaultfunction = HashFunction { hashfunction = function } 

function :: HashTable -> Int -> Int 
function va t = t `mod` ( location va ) 

hash :: HashFunction -> HashTable -> Int -> Int 
hash func hash t = ( hashfunction func ) hash t 

replacebit :: [Int] -> Int -> Int -> [Int] 
replacebit hashtable posit v = a ++ (v:tail ax) 
        where (a,ax) = splitAt posit hashtable  

setToOne :: Int -> HashTable -> HashTable 
setToOne t hashtable = hashtable { value = values } 
         where values = replacebit (value hashtable) t 1 

fill :: BloomFilter -> [Int] -> BloomFilter 
fill bf t = bf {table = tables} 
  where tables = foldr setToOne initialbloom $ concat [ [ hash f initialbloom v  | v <- t] | f <- fns ] 
         initialbloom = table setbloom 
         fns = hashF setbloom 

judge:: BloomFilter -> Int -> Bool 
judge setbloom v  
  | vs == [1]   = True 
  | otherwise   = False 
  where vs = [(value bs) !! pos | pos <- positions] 
        positions = [ hash hf bs v | hf <- hashF setbloom] 
        bs = table setbloom  

bloom :: [Int] -> Int -> Bool 
bloom vs v = judge (fill setbloom vs) v 

test :: [Int] -> [Int] 
test vs = value $ table $ fill setbloom vs

如何将其转换为冲突语言，感谢您的帮助。

4

0 回答 0