# Tiny associative array (alist-like)
**URL:** https://discourse.julialang.org/t/tiny-associative-array-alist-like/57937
**Category:** New to Julia
**Tags:** data\_structures
**Created:** [March 25, 2021, 3:22pm UTC](https://discourse.julialang.org/t/tiny-associative-array-alist-like/57937 "2021-03-25T15:22:40Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@circonflexe](https://discourse.julialang.org/u/circonflexe)
#### Post date: [March 25, 2021, 3:22pm UTC](https://discourse.julialang.org/t/tiny-associative-array-alist-like/57937/1 "2021-03-25T15:22:40Z")
So I need a data structure implementing a tiny associative array from integers to another type `T` (which type is not completely clear, but assume lists of integers, implemented as `Vector{Int}`, for now. Or it could be strings.) The number of (key, value) pairs will be very small (usually 2 and almost never more than 10), so using complex types with hashing (`Dict`) or trees (`SortedDict`) is likely not too efficient (I actually use `Dict` right now and a large part of my time is spent hashing keys).
So stdlib contains `SparseArrays`, which implements a `SparseVector` type using a list of keys and a list of values: this is space- and time-efficient and would be perfect for my usage. However, `getindex(::SparseVector, non_existent_key)` returns `zero(T)`, which in my case is an error.
Of course, I could wrap `Vector{Int}` inside a struct `ZeroableVector <: AbstractVector` such that `zero(ZeroableVector)` returns `[]`, but this seems a bit too ad-hoc; more precisely, since `setindex!(::SparseVector, ...)` calls `iszero`, I would also need to add a method to that function, which would conflict with the legitimate method inherited from `AbstractVector`.
So:
1. is there a relatively standard structure implementing a tiny associative array? (e.g. a spiritual successor to [GitHub - andyferris/AssociativeArray.jl](https://github.com/andyferris/AssociativeArray.jl) ?) something like LISP’s alists?
2. otherwise: did somebody already tweak `SparseVector` for something resembling this? (e.g. by overwriting `get`, adding a `haskey` method, etc.)?
---
### Author:  [@rdeits](https://discourse.julialang.org/u/rdeits)
#### Post date: [March 25, 2021, 4:28pm UTC](https://discourse.julialang.org/t/tiny-associative-array-alist-like/57937/2 "2021-03-25T16:28:10Z")
I’m not aware of an existing implementation, but I think you could implement your own in a pretty efficient way. If you’re willing to pay the O(N) lookup cost, it could be as simple as:
```julia
struct SmallMap{K, V} <: AbstractDict{K, V}
keys::Vector{K}
vals::Vector{V}
SmallMap{K, V}() where {K, V} = new{K, V}(K[], V[])
end
function Base.getindex(m::SmallMap, key)
for (i, k) in enumerate(m.keys)
if k == key
return m.vals[i]
end
end
throw(KeyError(key))
end
function Base.setindex!(m::SmallMap, value, key)
for (i, k) in enumerate(m.keys)
if k == key
m.vals[i] = value
return m
end
end
push!(m.keys, key)
push!(m.vals, value)
return m
end
function Base.iterate(m::SmallMap, i=1)
if i > length(m.keys)
return nothing
else
return (m.keys[i] => m.vals[i], i + 1)
end
end
Base.length(m::SmallMap) = length(m.keys)
```
Usage:
```julia
julia> m = SmallMap{String, Int}()
SmallMap{String, Int64}()
julia> m["hello"] = 1
1
julia> m["world"] = 2
2
julia> m
SmallMap{String, Int64} with 2 entries:
"hello" => 1
"world" => 2
```
---
### Author:  [@chris-b1](https://discourse.julialang.org/u/chris-b1)
#### Post date: [March 25, 2021, 4:28pm UTC](https://discourse.julialang.org/t/tiny-associative-array-alist-like/57937/3 "2021-03-25T16:28:17Z")
You might try the `ArrayDictionary` from Dictionaries.jl, also by @andyferris.
> **[GitHub - andyferris/Dictionaries.jl: An alternative interface for...](https://github.com/andyferris/Dictionaries.jl#other-dictionary-types)**
>
> An alternative interface for dictionaries in Julia, for improved productivity and performance - GitHub - andyferris/Dictionaries.jl: An alternative interface for dictionaries in Julia, for improved...
There’s been some discussion of that package on Discourse e.g.
> [@\[ANN\] Dictionaries.jl 0.3.0 - now using ordered collections by default](https://discourse.julialang.org/t/ann-dictionaries-jl-0-3-0-now-using-ordered-collections-by-default/41249):
>
> I’d like to announce the release of Dictionaries.jl v0.3.0. The headline changes are that dictionaries and indices now have a well-defined order (just like in OrderedCollections.jl) and that HashDictionary has been renamed to Dictionary for brevity and to better match Base. The creation of a brand new hash-based dictionary has been a tonne of work, and I’m glad to be finally releasing it. It’s design is inspired by the ordered hash dictionary released in CPython 3.6. I believe it is well teste…
---
### Author:  [@circonflexe](https://discourse.julialang.org/u/circonflexe)
#### Post date: [March 25, 2021, 8:38pm UTC](https://discourse.julialang.org/t/tiny-associative-array-alist-like/57937/4 "2021-03-25T20:38:49Z")
(_O(N)_ is not much of a problem given my values of _N_ indeed…)
Yes, this is more-or-less what I did (also I realized that writing the type was not much longer than my post here; I wrote almost the same as what you did, plus `keys()`, `values()` , `haskey`, a generic constructor, and that’s it.) Thanks for the answer!
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [March 26, 2021, 12:58pm UTC](https://discourse.julialang.org/t/tiny-associative-array-alist-like/57937/5 "2021-03-26T12:58:21Z")
> [@circonflexe](#):
>
> ( _O(N)_ is not much of a problem given my values of _N_ indeed…)
You could also sort key-value pairs, and use `searchsortedfirst` etc for a lookup, which is _O(log(N))_, plus, of course, the one-time cost of sorting — whether it is worth it depends on your application.