Главная » Haskell » Модуль HashTable

0

содержит реализацию расширяемых хеш-таблиц, которые описаны в работе [12]. Использование:

import  Data.HashTable

Главным алгебраическим типом данных для представления хеш-таблиц является тип HashTable.

Тип: HashTable

Описание: тип для представления хеш-таблиц, которые можно модифицировать.

Определение:

data  HashTable key  val

=  HashTable  {

cmp        :: !(key ->  key  ->  Bool), hash_fn  :: !(key ->  Int32),

tab          :: !(IORef (HT key  val))

}

Функция: new

Описание: создаёт новую хеш-таблицу. В качестве входных параметров передаются две функции, первая из которых определяет свойство равенства на ключах,

а вторая  — хеш-функцию для ключей. Для этих двух функций безусловно должно выполняться правило: eq A  B  => hash A  == hash  B.

Определение:

new :: (key  ->  key  ->  Bool)   ->  (key  ->  Int32) ->  IO (HashTable  key  val) new cmpr hash = do recordNew

let mask = tABLE_MIN  1

bkts’ < newMutArray  (0,mask)   [] bkts    < freezeArray bkts’

let kcnt  = 0

ht = HT  {buckets = bkts, kcount  = kcnt, bmask  = mask} table < newIORef ht

return (HashTable  {tab = table, hash_fn  = hash,  cmp = cmpr})

Функция: insert

Описание: заносит новую пару (значение, ключ) в заданную хеш-таблицу. Необходимо отметить, что эта функция не удаляет  старое значение для вносимого ключа  (если таковое имеется). Это  сделано  ради увеличения эффективности функции. Функция lookup возвращает значение по ключу, которое внесено в хештаблицу  последним. Для замены значений необходимо пользоваться  функцией update.

Определение:

insert :: HashTable key  val   ->  key  ->  val  ->  IO () insert ht key  val   =  updatingBucket  CanInsert

(\bucket ->  ((key, val):bucket, 1, ())) ht  key

Функция: delete

Описание: удаляет запись из хеш-таблицы по заданному ключу.

Определение:

delete :: HashTable key  val   ->  key  ->  IO ()

delete ht@HashTable{cmp  = eq}  key  = updatingBucket  Can’tInsert

(deleteBucket (eq  key)) ht  key

Функция: lookup

Описание: по заданному ключу возвращает значение из хеш-таблицы.

Определение:

lookup  :: HashTable key  val   ->  key  ->  IO  (Maybe val)

lookup  ht@HashTable{cmp  = eq}  key  = do recordLookup  (_,_,  bucket) < findBucket  ht key

let firstHit (k, v) r | eq key  k   =  Just  v

|  otherwise = r return (foldr  firstHit Nothing  bucket)

Функция: update

Описание: записывает новую пару (значение, ключ) в заданную хеш-таблицу. Если записываемый ключ уже имеется в хеш-таблице, происходит перезаписывание значения. Эта функции менее эффективна, чем функция insert, однако, более эффективна, чем связка функций delete и insert для перезаписи значения. Определение:

update  :: HashTable key  val   ->  key  ->  val   ->  IO Bool

update  ht@HashTable{cmp  = eq}  key  val   = updatingBucket  CanInsert (\bucket  ->  let (bucket’, dels, _)  =  deleteBucket (eq  key)  bucket

in  ((key,val):bucket’, 1 + dels, dels  /=  0))

ht key

Функция: fromList

Описание: преобразует список пар вида (значение, ключ) в хеш-таблицу.

Определение:

fromList :: (Eq  key)  => (key  ->  Int32) ->  [(key,val)] ->  IO  (HashTable  key  val) fromList hash list = do table < new (==)  hash

sequence_ [ insert table k  v  | (k,  v)  < list ] return table

Функция: toList

Описание:    преобразует   заданную    хеш-таблицу   в    список     пар     вида (значение, ключ).

Определение:

toList :: HashTable key  val   ->  IO  [(key,val)] toList = mapReduce  id  concat

Функция: longestChain

Описание:   возвращает  самую   длинную    последовательность    пар    вида (значение, ключ)  для  заданной таблицы, при  этом   ключ  в  данной последовательности всегда  одинаков.  Данная   функция   может   использоваться для определения того, хороша ли хеширующая функция для работы с данными. Если  возвращённая  последовательность  сравнительно велика (например, 14

элементов или  больше), то  необходимо использовать другую   хеширующую функцию.

Определение:

longestChain :: HashTable key  val   ->  IO  [(key,val)] longestChain = mapReduce  id  (maximumBy  lengthCmp)

where

lengthCmp (_:x)(_:y) = lengthCmp x  y

lengthCmp []

[]

= EQ

lengthCmp []

_

= LT

lengthCmp _

[]

= GT

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии