CompressHashDisplace.jl

Installation

julia> ] add CompressHashDisplace

Usage

using BenchmarkTools
using CompressHashDisplace

DICTIONARY = "/usr/share/dict/words"
dict = Dict{String, Int}()

for (line, word) in enumerate(readlines(DICTIONARY))
    dict[word] = line
end

frozen_dict = FrozenDict(dict)
frozen_dict["hello"] # 50196

frozen_unsafe_dict = FrozenUnsafeDict(dict)
frozen_unsafe_dict["hello"] # 50196

word = "hello"
@btime $dict[$word]               # 76.615 ns (0 allocations: 0 bytes)
@btime $frozen_dict[$word]        # 60.028 ns (0 allocations: 0 bytes)
@btime $frozen_unsafe_dict[$word] # 22.124 ns (0 allocations: 0 bytes)

Main difference between FrozenDict and FrozenUnsafeDict is that FrozenUnsafeDict do not validate input key

frozen_dict["foo"]         # KeyError: key "foo" not found
frozen_unsafe_dice["foo"]  # 59716, i.e. some random value

Methods

CompressHashDisplace.FrozenUnsafeDict โ€” Method
FrozenUnsafeDict(dict)

Computes a perfect hash table using given dict. FrozenUnsafeDict do not hold key values, and wouldn't do any validations during lookup procedure.

source