Programming Praxis: Hash Table With Open Addressing

Today’s Programming Praxis task was to create a hash table using open addressing to resolve collisions and that supports deletion.

The following, simple Haskell implementation of a hash table has a static size and supports deletion by using the scheme suggested in the task, i.e. to mark empty cells as Nil or Deleted. By doing this we can detect cells that previously had an item there and thus continue searching in cases where a deletion in the middle of a sequence of items with the same hash has occurred.

To avoid an infinite loop when inserting into a full table or deleting from a table filled with Deleted cells, both insert and delete’s helper functions are passed an end parameter that indicates when all elements have been looped over.

{-# Language RankNTypes #-}

import Data.Hashable
import Data.Vector (Vector, (//), (!), fromList)
import qualified Data.Vector as V

type HashFunction = (Hashable a) => a -> Int

-- A hash table has a vector of cells, a size and a hash function
data HT a = HT
  { vector :: Vector (Item a)
  , size   :: Int
  , h      :: HashFunction
  }

instance (Show a) => Show (HT a) where
  show (HT v s _) = show (v,s)

-- A cell is nil, deleted or contains an item
data Item a = Nil | Deleted | Item a
  deriving (Show, Eq)

-- Creates a new hash table of the given size with the given hash function
createNewHT :: (Hashable a) => Int -> HashFunction -> HT a
createNewHT size h = HT (V.replicate size Nil) size h

-- Insert an item into the hash table. Searches from h(item) until a
-- Deleted/Nil cell is found and inserts the item there.
-- The “end” parameter to “doInsert” is set to the position before where we
-- start the search to avoid an infinite loop when the table is full.
insert :: (Hashable a) => HT a -> a -> HT a
insert (HT v s h) item = HT (doInsert v (h item) (h item `mod` s-1)) s h
  where doInsert v' h' end
          | end == h' = error "Insert on full table"
          | otherwise  = case v' ! (h' `mod` s) of
                              Item _ -> doInsert v' ((h'+1) `mod` s) end
                              _      -> v' // [(h' `mod` s,Item item)]

-- Delete an item. Linear scan from h(item), if Nil is found, we do nothing, if
-- Delete is found, we continue looking. If an Item is found and it is the same,
-- we delete it. The “end” parameter to “doDelete” is set to the position
-- before where we start the search to avoid an infinite loop when the table is
-- full of Deleted cells.
delete :: (Hashable a, Eq a) => HT a -> a -> HT a
delete (HT v s h) item = HT (doDelete v (h item) (h item `mod` s-1)) s h
  where doDelete v' h' end
          | end == h' = v' -- went through whole table without finding element
          | otherwise = case v' ! (h' `mod` s) of
                             Nil     -> v'
                             Deleted -> doDelete v' ((h'+1) `mod` s) end
                             Item i  -> if i == item
                                           then v' // [(h' `mod` s, Deleted)]
                                           else doDelete v' ((h'+1) `mod` s) end
                                           --
-- Some basic tests
main :: IO ()
main = do
  -- insert and delete
  let a = createNewHT 5 hash :: HT Int
  let a' = ((((a `insert` 3) `insert` 8) `insert` 13 ) `delete` 3) `delete` 13
  print $ vector a' == fromList [Deleted,Nil,Nil,Deleted,Item 8]

  -- delete item from empty table
  let b = createNewHT 2 hash :: HT Int
  let b' = ((((b `insert` 1) `insert` 2) `delete` 1) `delete` 2) `delete` 3
  print $ vector b' == fromList [Deleted,Deleted]