# Programming Praxis: Ordered Hash Tables

2 Aug, 2013

Today’s Programming Praxis problem was to create a hash table with linear probing, but where the buckets are ordered. This is easily done by using the `insert`

, `delete`

and `find`

functions from `Data.List`

.

This means that inserts take longer, but that lookups (even unsuccessful ones) can – on average – terminate half-way through the list.

```
import Prelude hiding (lookup)
import qualified Data.Vector as V
import Data.Hashable (Hashable, hash)
import qualified Data.List as L (delete, find, insert)
import Data.Maybe (isJust, isNothing)
data HT a = HT (V.Vector [a]) deriving Show
empty :: (Hashable a, Ord a) => Int -> HT a
empty size = HT (V.replicate size [])
insert :: (Hashable a, Ord a) => HT a -> a -> HT a
insert (HT bs) e = let pos = hash e `mod` V.length bs
bucket = L.insert e $ bs V.! pos
in HT (V.update bs (V.singleton (pos,bucket)))
delete :: (Hashable a, Ord a) => HT a -> a -> HT a
delete (HT bs) e = let pos = hash e `mod` V.length bs
bucket = L.delete e $ bs V.! pos
in HT (V.update bs (V.singleton (pos, bucket)))
lookup :: (Hashable a, Ord a) => HT a -> a -> Maybe a
lookup (HT bs) e = let pos = hash e `mod` V.length bs
bucket = bs V.! pos
in L.find (==e) bucket
main :: IO ()
main = do
-- some simple tests
let ht = foldr (flip insert) (empty 10 :: HT Int) [0..99]
print . isNothing $ lookup ht 100
print . isJust $ lookup ht 50
print . isNothing $ lookup (delete ht 50) 50
print . all isNothing $ map (lookup (foldr (flip delete) ht [0..99])) [0..99]
```