{"@context":"https://w3id.org/codemeta/3.0","@type":"SoftwareSourceCode","identifier":"pkg:hackage/hashtables","name":"hashtables","description":"This package provides a couple of different implementations of mutable hash\ntables in the ST monad, as well as a typeclass abstracting their common\noperations, and a set of wrappers to use the hash tables in the IO monad.\n\nQUICK START: documentation for the hash table operations is provided in the\nData.HashTable.Class module, and the IO wrappers (which most users will\nprobably prefer) are located in the Data.HashTable.IO module.\n\nThis package currently contains three hash table implementations:\n\nData.HashTable.ST.Cuckoo contains an implementation of \"cuckoo\nhashing\" as introduced by Pagh and Rodler in 2001 (see\nhttp://en.wikipedia.org/wiki/Cuckoo_hashing). Cuckoo hashing has\nworst-case O(1) lookups and can reach a high \"load factor\", in which\nthe table can perform acceptably well even when approaching 90% full.\nRandomized testing shows this implementation of cuckoo hashing to be\nslightly faster on insert and slightly slower on lookup than\nData.HashTable.ST.Basic, while being more space efficient by about a\nhalf-word per key-value mapping. Cuckoo hashing, like the basic hash\ntable implementation using linear probing, can suffer from long delays\nwhen the table is resized.\n\nData.HashTable.ST.Basic contains a basic open-addressing hash table\nusing linear probing as the collision strategy. On a pure speed basis it\nshould currently be the fastest available Haskell hash table\nimplementation for lookups, although it has a higher memory overhead\nthan the other tables and can suffer from long delays when the table is\nresized because all of the elements in the table need to be rehashed.\n\nData.HashTable.ST.Linear contains a linear hash table (see\nhttp://en.wikipedia.org/wiki/Linear_hashing), which trades some insert\nand lookup performance for higher space efficiency and much shorter\ndelays when expanding the table. In most cases, benchmarks show this\ntable to be currently slightly faster than Data.HashTable from the\nHaskell base library.\n\nIt is recommended to create a concrete type alias in your code when using this\npackage, i.e.:\n\nFirstly, this makes it easy to switch to a different hash table implementation,\nand secondly, using a concrete type rather than leaving your functions abstract\nin the HashTable class should allow GHC to optimize away the typeclass\ndictionaries.\n\nThis package accepts a couple of different cabal flags:\n\nunsafe-tricks, default ON. If this flag is enabled, we use some\nunsafe GHC-specific tricks to save indirections (namely unsafeCoerce#\nand reallyUnsafePtrEquality#. These techniques rely on assumptions\nabout the behaviour of the GHC runtime system and, although they've been\ntested and should be safe under normal conditions, are slightly\ndangerous. Caveat emptor. In particular, these techniques are\nincompatible with HPC code coverage reports.\n\nsse42, default OFF. If this flag is enabled, we use some SSE 4.2\ninstructions (see http://en.wikipedia.org/wiki/SSE4, first available on\nIntel Core 2 processors) to speed up cache-line searches for cuckoo\nhashing.\n\nbounds-checking, default OFF. If this flag is enabled, array accesses\nare bounds-checked.\n\ndebug, default OFF. If turned on, we'll rudely spew debug output to\nstdout.\n\nportable, default OFF. If this flag is enabled, we use only pure\nHaskell code and try not to use unportable GHC extensions. Turning this\nflag on forces unsafe-tricks and sse42 OFF.\n\nPlease send bug reports to\nhttps://github.com/gregorycollins/hashtables/issues.","version":"1.4.2","softwareVersion":"1.4.2","license":"https://spdx.org/licenses/BSD-3-Clause","codeRepository":"https://github.com/gregorycollins/hashtables","issueTracker":"https://github.com/gregorycollins/hashtables/issues","url":"http://github.com/gregorycollins/hashtables","keywords":["bsd3","data","library","Propose Tags"],"programmingLanguage":{"@type":"ComputerLanguage","name":"Haskell"},"maintainer":[{"@type":"Person","name":"GregoryCollins"},{"@type":"Person","name":"ErikDeCastroLopo"},{"@type":"Person","name":"mgmeier"}],"author":[{"@type":"Person","name":"GregoryCollins"},{"@type":"Person","name":"ErikDeCastroLopo"},{"@type":"Person","name":"mgmeier"}],"copyrightHolder":[{"@type":"Person","name":"GregoryCollins"},{"@type":"Person","name":"ErikDeCastroLopo"},{"@type":"Person","name":"mgmeier"}],"dateCreated":"2011-06-11","dateModified":"2025-01-23","datePublished":"2025-01-23","copyrightYear":2011,"downloadUrl":"https://hackage.haskell.org/package/hashtables-1.4.2/hashtables-1.4.2.tar.gz","applicationCategory":"hackage","runtimePlatform":"hackage","developmentStatus":"active","sameAs":["https://hackage.haskell.org/package/hashtables"],"https://www.w3.org/ns/activitystreams#likes":132,"https://forgefed.org/ns#forks":36}