Data.Bytes.HashMap

Implementation of static hash map data structure.

Documentation

data Map v

A static perfect hash table where the keys are byte arrays. This table cannot be updated after its creation, but all lookups have guaranteed O(1) worst-case cost. It consumes linear space. This is an excellent candidate for use with compact regions.

Instances

Functor Map

Defined in Data.Bytes.HashMap.Internal

Methods

fmap :: (a -> b) -> Map a -> Map b

(<$) :: a -> Map b -> Map a

Foldable Map

Defined in Data.Bytes.HashMap.Internal

Methods

fold :: Monoid m => Map m -> m

foldMap :: Monoid m => (a -> m) -> Map a -> m

foldr :: (a -> b -> b) -> b -> Map a -> b

foldr' :: (a -> b -> b) -> b -> Map a -> b

foldl :: (b -> a -> b) -> b -> Map a -> b

foldl' :: (b -> a -> b) -> b -> Map a -> b

foldr1 :: (a -> a -> a) -> Map a -> a

foldl1 :: (a -> a -> a) -> Map a -> a

toList :: Map a -> [a]

null :: Map a -> Bool

length :: Map a -> Int

elem :: Eq a => a -> Map a -> Bool

maximum :: Ord a => Map a -> a

minimum :: Ord a => Map a -> a

sum :: Num a => Map a -> a

product :: Num a => Map a -> a

Traversable Map

Defined in Data.Bytes.HashMap.Internal

Methods

traverse :: Applicative f => (a -> f b) -> Map a -> f (Map b)

sequenceA :: Applicative f => Map (f a) -> f (Map a)

mapM :: Monad m => (a -> m b) -> Map a -> m (Map b)

sequence :: Monad m => Map (m a) -> m (Map a)

lookup :: Bytes -> Map v -> Maybe v

Returns the value associated with the key in the map.

fromList :: CryptHandle -> [(Bytes, v)] -> IO (Map v)

Build a static hash map. This may be used on input that comes from an adversarial user. It always produces a perfect hash map.

fromTrustedList :: [(Bytes, v)] -> Map v

Build a map from keys that are known at compile time. All keys must be 64 bytes or less. This uses a built-in source of entropy and is entirely deterministic. An adversarial user could feed this function keys that cause it to error out rather than completing.

fromListWith

Arguments

:: CryptHandle

Source of randomness

-> (v -> v -> v)

-> [(Bytes, v)]

-> IO (Map v)

Used for testing

data HashMapException

Constructors

HashMapException !Int [Bytes] [[(Word, Bytes)]]

Instances

Eq HashMapException

Defined in Data.Bytes.HashMap

Methods

(==) :: HashMapException -> HashMapException -> Bool

(/=) :: HashMapException -> HashMapException -> Bool

Show HashMapException

Defined in Data.Bytes.HashMap

Methods

showsPrec :: Int -> HashMapException -> ShowS

show :: HashMapException -> String

showList :: [HashMapException] -> ShowS

Exception HashMapException

Defined in Data.Bytes.HashMap

Methods

toException :: HashMapException -> SomeException

fromException :: SomeException -> Maybe HashMapException

displayException :: HashMapException -> String

distribution :: Map v -> [(Int, Int)]

For each slot, gives the number of keys that hash to it after the first hash function has been applied.

distinctEntropies :: Map v -> Int

The number of non-matching entropies being used.