Repository: JuliaCollections/DataStructures.jl
Pull request #501 (2019-05-14 08:52:29)

RobinDict 
I call this `RobinDict`, which implements [Robinhood Hashing technique](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf) .

- [x] Write `delete`/`erase` operation for `RobinDict`
- [x] Add tests
- [x] Write docstrings
- [x] Benchmarking the code
- [x] Documentation


Patch:
diff --git a/Project.toml b/Project.toml
index d9a716e..5dcd6a0 100644
--- a/Project.toml
+++ b/Project.toml
@@ -1,6 +1,6 @@
 name = "DataStructures"
 uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
-version = "0.14.1"
+version = "0.14.0"
 
 [deps]
 InteractiveUtils = "b77e0a4c-d291-57a0-90e8-8db25a27a240"
diff --git a/docs/src/index.md b/docs/src/index.md
index 1cb4cbc..16e3a10 100644
--- a/docs/src/index.md
+++ b/docs/src/index.md
@@ -13,6 +13,7 @@ This package implements a variety of data structures, including
 -   Binary Heap
 -   Mutable Binary Heap
 -   Ordered Dicts and Sets
+-   RobinDict
 -   Dictionaries with Defaults
 -   Trie
 -   Linked List and Mutable Linked List
@@ -34,6 +35,7 @@ Pages = [
     "heaps.md",
     "ordered_containers.md",
     "default_dict.md",
+    "robin_dict.md",
     "trie.md",
     "linked_list.md",
     "mutable_linked_list.md"
diff --git a/docs/src/robin_dict.md b/docs/src/robin_dict.md
new file mode 100644
index 0000000..c17d4eb
--- /dev/null
+++ b/docs/src/robin_dict.md
@@ -0,0 +1,36 @@
+# RobinDict
+
+`RobinDict` provides a standard dictionary, conforming to the AbstractDict protocol, which uses the Robin Hood hashing algorithm with backward-shift deletion to provide improved average performance over Dict.
+
+The interface of `RobinDict` replicates that of `Dict`.
+
+Examples:
+
+```julia
+julia> d = RobinDict{Int, Char}(1 => 'a', 2 => 'b')
+RobinDict{Int64,Char} with 2 entries:
+  2 => 'b'
+  1 => 'a'
+
+julia> d[3] = 'c';
+
+julia> collect(d)
+3-element Array{Pair{Int64,Char},1}:
+ 2 => 'b'
+ 3 => 'c'
+ 1 => 'a'
+
+julia> delete!(d, 2);
+
+julia> d[1]
+'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
+
+julia> d
+RobinDict{Int64,Char} with 2 entries:
+  3 => 'c'
+  1 => 'a'
+
+julia> pop!(d)
+3 => 'c'
+```
+
diff --git a/src/DataStructures.jl b/src/DataStructures.jl
index fe2ca55..47c3ffe 100644
--- a/src/DataStructures.jl
+++ b/src/DataStructures.jl
@@ -55,6 +55,7 @@ module DataStructures
     export orderobject, ordtype, Lt, compare, onlysemitokens
 
     export MultiDict, enumerateall
+    export RobinDict
 
     export findkey
 
@@ -90,7 +91,7 @@ module DataStructures
     include("sorted_set.jl")
     include("tokens2.jl")
     include("container_loops.jl")
-
+    include("robin_dict.jl")
     export
         CircularBuffer,
         capacity,
diff --git a/src/circular_buffer.jl b/src/circular_buffer.jl
index 0efa4b2..8e9e63a 100644
--- a/src/circular_buffer.jl
+++ b/src/circular_buffer.jl
@@ -16,8 +16,6 @@ mutable struct CircularBuffer{T} <: AbstractVector{T}
     CircularBuffer{T}(capacity::Int) where {T} = new{T}(capacity, 1, 0, Vector{T}(undef, capacity))
 end
 
-CircularBuffer(capacity) = CircularBuffer{Any}(capacity)
-
 """
     empty!(cb)
 
@@ -60,7 +58,7 @@ end
 """
     cb[i] = data
 
-Store data to the `i`-th element of `CircularBuffer`.
+Store data to the i-th element of CircularBuffer.
 """
 @inline Base.@propagate_inbounds function Base.setindex!(cb::CircularBuffer, data, i::Int)
     cb.buffer[_buffer_index_checked(cb, i)] = data
@@ -100,7 +98,7 @@ end
 """
     popfirst!(cb)
 
-Remove the element from the front of the `CircularBuffer`.
+Remove the first item (at the back) from CircularBuffer.
 """
 function popfirst!(cb::CircularBuffer)
     if cb.length == 0
diff --git a/src/robin_dict.jl b/src/robin_dict.jl
new file mode 100644
index 0000000..4581f4e
--- /dev/null
+++ b/src/robin_dict.jl
@@ -0,0 +1,611 @@
+import Base: setindex!, sizehint!, empty!, isempty, length, copy, empty,
+             getindex, getkey, haskey, iterate, @propagate_inbounds,
+             pop!, delete!, get, get!, isbitstype, in, hashindex, isbitsunion,
+             isiterable, dict_with_eltype, KeySet, Callable, _tablesz, filter!
+
+# the load factor after which the dictionary `rehash` happens
+const ROBIN_DICT_LOAD_FACTOR = 0.70
+
+"""
+    RobinDict([itr])
+
+`RobinDict{K,V}()` constructs a hash table with keys of type `K` and values of type `V`.
+Keys are compared with [`isequal`](@ref) and hashed with [`hash`](@ref).
+Given a single iterable argument, constructs a [`RobinDict`](@ref) whose key-value pairs
+are taken from 2-tuples `(key,value)` generated by the argument.
+
+# Examples
+```jldoctest
+julia> RobinDict([("A", 1), ("B", 2)])
+RobinDict{String,Int64} with 2 entries:
+  "B" => 2
+  "A" => 1
+```
+
+Alternatively, a sequence of pair arguments may be passed.
+
+```jldoctest
+julia> RobinDict("A"=>1, "B"=>2)
+RobinDict{String,Int64} with 2 entries:
+  "B" => 2
+  "A" => 1
+```
+"""
+mutable struct RobinDict{K,V} <: AbstractDict{K,V}
+    hashes::Vector{UInt32}
+    keys::Array{K,1}
+    vals::Array{V,1}
+    count::Int
+    idxfloor::Int
+end
+
+function RobinDict{K, V}() where {K, V}
+    n = 16
+    RobinDict{K, V}(zeros(UInt32, n), Vector{K}(undef, n), Vector{V}(undef, n), 0, 0)
+end
+
+function RobinDict{K, V}(d::RobinDict{K, V}) where {K, V}
+    RobinDict{K, V}(copy(d.hashes), copy(d.keys), copy(d.vals), d.count, d.idxfloor)
+end
+
+function RobinDict{K,V}(kv) where V where K
+    h = RobinDict{K,V}()
+    for (k,v) in kv
+        h[k] = v
+    end
+    return h
+end
+RobinDict{K,V}(p::Pair) where {K,V} = setindex!(RobinDict{K,V}(), p.second, p.first)
+function RobinDict{K,V}(ps::Pair...) where V where K
+    h = RobinDict{K,V}()
+    sizehint!(h, length(ps))
+    for p in ps
+        h[p.first] = p.second
+    end
+    return h
+end
+
+RobinDict() = RobinDict{Any,Any}()
+RobinDict(kv::Tuple{}) = RobinDict()
+copy(d::RobinDict) = RobinDict(d)
+empty(d::RobinDict, ::Type{K}, ::Type{V}) where {K, V} = RobinDict{K, V}()
+
+RobinDict(ps::Pair{K,V}...) where {K,V} = RobinDict{K,V}(ps)
+RobinDict(ps::Pair...)                  = RobinDict(ps)
+
+RobinDict(d::AbstractDict{K, V}) where {K, V} = RobinDict{K, V}(d)
+
+function RobinDict(kv)
+    try
+        return dict_with_eltype((K, V) -> RobinDict{K, V}, kv, eltype(kv))
+    catch e
+        if !isiterable(typeof(kv)) || !all(x -> isa(x, Union{Tuple,Pair}), kv)
+            !all(x->isa(x,Union{Tuple,Pair}),kv)
+            throw(ArgumentError("RobinDict(kv): kv needs to be an iterator of tuples or pairs"))
+        else
+            rethrow(e)
+        end
+    end
+end
+
+hash_key(key) = (hash(key)%UInt32) | 0x80000000
+desired_index(hash, sz) = (hash & (sz - 1)) + 1
+
+function calculate_distance(h::RobinDict{K, V}, index) where {K, V} 
+    @assert isslotfilled(h, index)
+    sz = length(h.keys)
+    @inbounds index_init = desired_index(h.hashes[index], sz)
+    return (index - index_init + sz) & (sz - 1)
+end
+
+# insert algorithm
+function rh_insert!(h::RobinDict{K, V}, key::K, val::V) where {K, V}
+    # table full
+    @assert h.count != length(h.keys)
+    
+    ckey, cval, chash = key, val, hash_key(key)
+    sz = length(h.keys)
+    index_init = desired_index(chash, sz)
+
+    index_curr = index_init
+    probe_distance = 0
+    probe_current = 0
+    @inbounds while true
+        if (isslotempty(h, index_curr)) || (isslotfilled(h, index_curr) && isequal(h.keys[index_curr], ckey))
+            break
+        end
+        probe_distance = calculate_distance(h, index_curr)
+
+        if probe_current > probe_distance
+            h.vals[index_curr], cval = cval, h.vals[index_curr]
+            h.keys[index_curr], ckey = ckey, h.keys[index_curr]
+            h.hashes[index_curr], chash = chash, h.hashes[index_curr]
+            probe_current = probe_distance
+        end
+        probe_current += 1
+        index_curr = (index_curr & (sz - 1)) + 1
+    end
+    
+    @inbounds if isslotfilled(h, index_curr) && isequal(h.keys[index_curr], ckey)
+        h.vals[index_curr] = cval
+        return index_curr
+    end
+
+    @inbounds if isslotempty(h, index_curr)
+        h.count += 1
+    end
+
+    @inbounds h.vals[index_curr] = cval
+    @inbounds h.keys[index_curr] = ckey
+    @inbounds h.hashes[index_curr] = chash
+    
+    @assert probe_current >= 0
+    
+    if h.idxfloor == 0
+        h.idxfloor = index_curr
+    else
+        h.idxfloor = min(h.idxfloor, index_curr)
+    end
+    return index_curr
+end
+
+function rh_insert_for_rehash!(h_new::RobinDict{K, V}, key::K, val::V, hash::UInt32) where {K, V}
+    # table full
+    @assert h_new.count != length(h_new.keys)
+    
+    ckey, cval, chash = key, val, hash
+    sz = length(h_new.keys)
+    index_init = desired_index(chash, sz)
+
+    index_curr = index_init
+    probe_distance = 0
+    probe_current = 0
+    @inbounds while true
+        if (isslotempty(h_new, index_curr))
+            break
+        end
+        probe_distance = calculate_distance(h_new, index_curr)
+
+        if probe_current > probe_distance
+            h_new.vals[index_curr], cval = cval, h_new.vals[index_curr]
+            h_new.keys[index_curr], ckey = ckey, h_new.keys[index_curr]
+            h_new.hashes[index_curr], chash = chash, h_new.hashes[index_curr]
+            probe_current = probe_distance
+        end
+        probe_current += 1
+        index_curr = (index_curr & (sz - 1)) + 1
+    end
+
+    @inbounds if isslotempty(h_new, index_curr)
+        h_new.count += 1
+    end
+
+    @inbounds h_new.vals[index_curr] = cval
+    @inbounds h_new.keys[index_curr] = ckey
+    @inbounds h_new.hashes[index_curr] = chash
+    
+    @assert probe_current >= 0
+    
+    if h_new.idxfloor == 0
+        h_new.idxfloor = index_curr
+    else
+        h_new.idxfloor = min(h_new.idxfloor, index_curr)
+    end
+    return index_curr
+end
+
+#rehash! algorithm
+function rehash!(h::RobinDict{K,V}, newsz = length(h.keys)) where {K, V}
+    oldk = h.keys
+    oldv = h.vals
+    oldh = h.hashes
+    sz = length(oldk)
+    newsz = _tablesz(newsz)
+    if h.count == 0
+        resize!(h.keys, sz)
+        resize!(h.vals, sz)
+        resize!(h.hashes, newsz)
+        fill!(h.hashes, 0)
+        h.count = 0
+        h.idxfloor = 0
+        return h
+    end
+
+    h.keys = Vector{K}(undef, newsz)
+    h.vals = Vector{V}(undef, newsz)
+    h.hashes = zeros(UInt32,newsz)
+    h.count = 0
+    h.idxfloor = 0
+
+    for i = 1:sz
+        @inbounds if oldh[i] != 0
+            k = oldk[i]
+            v = oldv[i]
+            rh_insert_for_rehash!(h, k, v, oldh[i])
+        end
+    end
+    return h
+end
+
+function sizehint!(d::RobinDict, newsz)
+    newsz = _tablesz(newsz*2)  # *2 for keys and values in same array
+    oldsz = length(d.keys)
+    # grow at least 25%
+    if newsz < (oldsz*5)>>2
+        return d
+    end
+    rehash!(d, newsz)
+end
+
+@propagate_inbounds isslotfilled(h::RobinDict, index) = (h.hashes[index] != 0)
+@propagate_inbounds isslotempty(h::RobinDict, index) = (h.hashes[index] == 0)
+
+
+function setindex!(h::RobinDict{K,V}, v0, key0) where {K, V}
+    key = convert(K, key0)
+    isequal(key, key0) || throw(ArgumentError("$key0 is not a valid key for type $K"))
+    _setindex!(h, key, v0)
+end
+
+function _setindex!(h::RobinDict{K,V}, key::K, v0) where {K, V}
+    v = convert(V, v0)
+    sz = length(h.keys)
+    (h.count > ROBIN_DICT_LOAD_FACTOR * sz) && rehash!(h, sz<<2)
+    index = rh_insert!(h, key, v)
+    @assert index > 0
+    h
+end
+
+isempty(d::RobinDict) = (d.count == 0)
+length(d::RobinDict) = d.count
+
+"""
+    empty!(collection) -> collection
+
+Remove all elements from a `collection`.
+
+# Examples
+```jldoctest
+julia> A = RobinDict("a" => 1, "b" => 2)
+RobinDict{String,Int64} with 2 entries:
+  "b" => 2
+  "a" => 1
+
+julia> empty!(A);
+
+julia> A
+RobinDict{String,Int64} with 0 entries
+```
+"""
+function empty!(h::RobinDict{K,V}) where {K, V}
+    sz = length(h.keys)
+    empty!(h.hashes)
+    empty!(h.keys)
+    empty!(h.vals)
+    resize!(h.keys, sz)
+    resize!(h.vals, sz)
+    resize!(h.hashes, sz)
+    h.count = 0
+    h.idxfloor = 0
+    return h
+end
+ 
+function rh_search(h::RobinDict{K, V}, key::K) where {K, V}
+    sz = length(h.keys)
+    chash = hash_key(key)
+    index = desired_index(chash, sz)
+    cdibs = 0
+    @inbounds while true
+        if isslotempty(h, index)
+            return -1
+        elseif cdibs > calculate_distance(h, index)
+            return -1
+        elseif h.hashes[index] == chash && (h.keys[index] === key || isequal(h.keys[index], key))
+            return index
+        end
+        index = (index & (sz - 1)) + 1
+    end
+end
+
+"""
+    get!(collection, key, default)
+
+Return the value stored for the given key, or if no mapping for the key is present, store
+`key => default`, and return `default`.
+
+# Examples
+```jldoctest
+julia> d = RobinDict("a"=>1, "b"=>2, "c"=>3);
+
+julia> get!(d, "a", 5)
+1
+
+julia> get!(d, "d", 4)
+4
+
+julia> d
+RobinDict{String,Int64} with 4 entries:
+  "c" => 3
+  "b" => 2
+  "a" => 1
+  "d" => 4
+```
+"""
+get!(collection, key, default)
+
+get!(h::RobinDict{K,V}, key0, default) where {K,V} = get!(()->default, h, key0)
+
+"""
+    get!(f::Function, collection, key)
+
+Return the value stored for the given key, or if no mapping for the key is present, store
+`key => f()`, and return `f()`.
+
+This is intended to be called using `do` block syntax:
+```julia
+get!(dict, key) do
+    # default value calculated here
+    time()
+end
+```
+"""
+get!(f::Function, collection, key)
+
+function get!(default::Callable, h::RobinDict{K,V}, key0::K) where {K, V}
+    key = convert(K, key0)
+    return _get!(default, h, key)
+end
+
+function _get!(default::Callable, h::RobinDict{K,V}, key::K) where V where K
+    index = rh_search(h, key)
+    
+    index > 0 && return h.vals[index]
+
+    v = convert(V, default())
+    rh_insert!(h, key, v)
+    return v
+end
+
+function getindex(h::RobinDict{K, V}, key0) where {K, V}
+    key = convert(K, key0)
+    index = rh_search(h, key)
+    @inbounds return (index < 0) ? throw(KeyError(key)) : h.vals[index]
+end
+
+"""
+    get(collection, key, default)
+
+Return the value stored for the given key, or the given default value if no mapping for the
+key is present.
+
+# Examples
+```jldoctest
+julia> d = RobinDict("a"=>1, "b"=>2);
+
+julia> get(d, "a", 3)
+1
+
+julia> get(d, "c", 3)
+3
+```
+"""
+get(collection, key, default)
+
+function get(h::RobinDict{K,V}, key0, default) where {K, V}
+    key = convert(K, key0)
+    index = rh_search(h, key)
+    @inbounds return (index < 0) ? default : h.vals[index]::V
+end
+
+"""
+    get(f::Function, collection, key)
+
+Return the value stored for the given key, or if no mapping for the key is present, return
+`f()`.  Use [`get!`](@ref) to also store the default value in the dictionary.
+
+This is intended to be called using `do` block syntax
+
+```julia
+get(dict, key) do
+    # default value calculated here
+    time()
+end
+```
+"""
+get(::Function, collection, key)
+
+function get(default::Callable, h::RobinDict{K,V}, key0) where {K, V}
+    key = convert(K, key0) 
+    index = rh_search(h, key)
+    @inbounds return (index < 0) ? default() : h.vals[index]::V
+end
+
+"""
+    haskey(collection, key) -> Bool
+
+Determine whether a collection has a mapping for a given `key`.
+
+# Examples
+```jldoctest
+julia> D = RobinDict('a'=>2, 'b'=>3)
+RobinDict{Char,Int64} with 2 entries:
+  'a' => 2
+  'b' => 3
+
+julia> haskey(D, 'a')
+true
+
+julia> haskey(D, 'c')
+false
+```
+"""
+haskey(h::RobinDict, key) = (rh_search(h, key) > 0) 
+in(key, v::KeySet{<:Any, <:RobinDict}) = (rh_search(v.dict, key) >= 0)
+
+"""
+    getkey(collection, key, default)
+
+Return the key matching argument `key` if one exists in `collection`, otherwise return `default`.
+
+# Examples
+```jldoctest
+julia> D = RobinDict('a'=>2, 'b'=>3)
+RobinDict{Char,Int64} with 2 entries:
+  'a' => 2
+  'b' => 3
+
+julia> getkey(D, 'a', 1)
+'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
+
+julia> getkey(D, 'd', 'a')
+'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
+```
+"""
+function getkey(h::RobinDict{K,V}, key0, default) where {K, V}
+    key = convert(K, key0) 
+    index = rh_search(h, key)
+    @inbounds return (index < 0) ? default : h.keys[index]::K
+end
+
+# backward shift deletion by not keeping any tombstones
+function rh_delete!(h::RobinDict{K, V}, index) where {K, V}
+    @assert index > 0
+
+    # this assumes that there is a key/value present in the dictionary at index
+    index0 = index
+    sz = length(h.keys)
+    @inbounds while true
+        index0 = (index0 & (sz - 1)) + 1
+        if isslotempty(h, index0) || calculate_distance(h, index0) == 0
+            break
+        end
+    end
+    #index0 represents the position before which we have to shift backwards 
+    
+    # the backwards shifting algorithm
+    curr = index
+    next = (index & (sz - 1)) + 1
+    
+    @inbounds while next != index0
+        h.vals[curr] = h.vals[next]
+        h.keys[curr] = h.keys[next]
+        h.hashes[curr] = h.hashes[next]
+        curr = next
+        next = (next & (sz-1)) + 1
+    end
+    
+    #curr is at the last position, reset back to normal
+    isbitstype(K) || isbitsunion(K) || ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.keys, curr-1)
+    isbitstype(V) || isbitsunion(V) || ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.vals, curr-1)
+    @inbounds h.hashes[curr] = 0x0
+
+    h.count -= 1
+    # this is necessary because key at idxfloor might get deleted 
+    h.idxfloor = get_next_filled(h, h.idxfloor)
+    return h
+end
+
+function _pop!(h::RobinDict, index)
+    @inbounds val = h.vals[index]
+    rh_delete!(h, index)
+    return val
+end
+
+function pop!(h::RobinDict{K, V}, key0) where {K, V}
+    key = convert(K, key0) 
+    index = rh_search(h, key)
+    return index > 0 ? _pop!(h, index) : throw(KeyError(key))
+end
+
+"""
+    pop!(collection, key[, default])
+
+Delete and return the mapping for `key` if it exists in `collection`, otherwise return
+`default`, or throw an error if `default` is not specified.
+
+# Examples
+```jldoctest
+julia> d = RobinDict("a"=>1, "b"=>2, "c"=>3);
+
+julia> pop!(d, "a")
+1
+
+julia> pop!(d, "d")
+ERROR: KeyError: key "d" not found
+Stacktrace:
+[...]
+
+julia> pop!(d, "e", 4)
+4
+```
+"""
+pop!(collection, key, default)
+
+function pop!(h::RobinDict{K, V}, key0, default) where {K, V}
+    key = convert(K, key0) 
+    index = rh_search(h, key)
+    return index > 0 ? _pop!(h, index) : default
+end
+
+function pop!(h::RobinDict)
+    isempty(h) && throw(ArgumentError("dict must be non-empty"))
+    idx = h.idxfloor
+    @inbounds key = h.keys[idx]
+    @inbounds val = h.vals[idx]
+    rh_delete!(h, idx)
+    key => val
+end
+
+"""
+    delete!(collection, key)
+
+Delete the mapping for the given key in a collection, and return the collection.
+
+# Examples
+```jldoctest
+julia> d = RobinDict("a"=>1, "b"=>2)
+RobinDict{String,Int64} with 2 entries:
+  "b" => 2
+  "a" => 1
+
+julia> delete!(d, "b")
+RobinDict{String,Int64} with 1 entry:
+  "a" => 1
+```
+"""
+function delete!(h::RobinDict{K, V}, key0) where {K, V}
+    key = convert(K, key0) 
+    index = rh_search(h, key)
+    if index > 0
+        rh_delete!(h, index)
+    end
+    return h
+end
+
+function get_idxfloor(h::RobinDict)
+    @inbounds for i = 1:length(h.keys)
+        if isslotfilled(h, i)
+            return i
+        end
+    end
+    return 0
+end
+
+function get_next_filled(h::RobinDict, i)
+    L = length(h.keys)
+    (1 <= i <= L) || return 0
+    for j = i:L
+        @inbounds if isslotfilled(h, j)
+            return  j
+        end
+    end
+    return 0
+end
+
+@propagate_inbounds _iterate(t::RobinDict{K,V}, i) where {K,V} = i == 0 ? nothing : (Pair{K,V}(t.keys[i],t.vals[i]), i == typemax(Int) ? 0 : get_next_filled(t, i+1))
+@propagate_inbounds function iterate(t::RobinDict)
+    _iterate(t, t.idxfloor)
+end
+@propagate_inbounds iterate(t::RobinDict, i) = _iterate(t, get_next_filled(t, i))
+
+filter!(f, d::RobinDict) = Base.filter_in_one_pass!(f, d)
diff --git a/src/sorted_dict.jl b/src/sorted_dict.jl
index 09cb26a..1f34584 100644
--- a/src/sorted_dict.jl
+++ b/src/sorted_dict.jl
@@ -399,7 +399,7 @@ log *n*)
 """
 function get(default_::Union{Function,Type}, m::SortedDict{K,D}, k_) where {K,D}
     i, exactfound = findkey(m.bt, convert(K, k_))
-    return exactfound ? m.bt.data[i].d : default_()
+    return exactfound ? m.bt.data[i].d : convert(D, default_())
 end
 
 get(m::SortedDict, k_, default_) = get(()->default_, m, k_)
@@ -440,7 +440,7 @@ than `k`. Time: O(*c* log *n*)
 """
 function getkey(m::SortedDict{K,D,Ord}, k_, default_) where {K,D,Ord <: Ordering}
     i, exactfound = findkey(m.bt, convert(K, k_))
-    exactfound ? m.bt.data[i].k : default_
+    exactfound ? m.bt.data[i].k : convert(K, default_)
 end
 
 ## Function delete! deletes an item at a given


Test patch:
diff --git a/test/bench_robin_dict.jl b/test/bench_robin_dict.jl
new file mode 100644
index 0000000..52322e9
--- /dev/null
+++ b/test/bench_robin_dict.jl
@@ -0,0 +1,227 @@
+using BenchmarkTools, Random, DataStructures, Printf, Plots, Statistics
+
+include("../src/robin_dict.jl")
+
+function add_entries(h::AbstractDict, entries::Vector{Pair{K, V}}) where {K, V}
+	for (k, v) in entries
+		h[k] = v
+	end
+end
+
+@printf(".\nSample #1 Key => Integer , Size => 10^6 entries\n.\n")
+
+sample1 = rand(Int, 10^6, 2)
+entries1 = Vector{Pair{Int, Int}}()
+sizehint!(entries1, 10^6)
+for i = 1 : 10^6
+	push!(entries1, Pair{Int, Int}(sample1[i, 1], sample1[i, 2]))
+end
+
+@printf("	add_entries for RobinDict()\n")
+@btime add_entries(RobinDict(), entries1)
+
+@printf("	add_entries for Dict()\n")
+@btime add_entries(Dict(), entries1)
+
+@printf("	add_entries for RobinDict{Int, Int}()\n")
+@btime add_entries(RobinDict{Int, Int}(), entries1)
+
+@printf("	add_entries for Dict{Int, Int}()\n")
+@btime add_entries(Dict{Int, Int}(), entries1)
+
+@printf(".\nSample #2 Key => Float32 , Size => 10^6 entries\n.\n")
+
+sample2 = rand(Float32, 10^6, 2)
+entries2 = Vector{Pair{Float32, Float32}}()
+sizehint!(entries2, 10^6)
+for i = 1 : 10^6
+	push!(entries2, Pair{Float32, Float32}(sample1[i, 1], sample1[i, 2]))
+end
+
+@printf("	add_entries for RobinDict()\n")
+@btime add_entries(RobinDict(), entries2)
+
+@printf("	add_entries for Dict()\n")
+@btime add_entries(Dict(), entries2)
+
+@printf("	add_entries for RobinDict{Float32, Float32}()\n")
+@btime add_entries(RobinDict{Float32, Float32}(), entries2)
+
+@printf("	add_entries for Dict{Float32, Float32}()\n")
+@btime add_entries(Dict{Float32, Float32}(), entries2)
+
+
+
+@printf(".\nSample #3 Key => String , Size => 10^6 entries\n.\n")
+
+entries3 = Vector{Pair{String, String}}()
+sizehint!(entries3, 10^6)
+for i = 1 : 10^6
+	push!(entries3, Pair{String, String}(randstring(), randstring()))
+end
+
+@printf("	add_entries for RobinDict()\n")
+@btime add_entries(RobinDict(), entries3)
+
+@printf("	add_entries for Dict()\n")
+@btime add_entries(Dict(), entries3)
+
+@printf("	add_entries for RobinDict{String, String}()\n")
+@btime add_entries(RobinDict{String, String}(), entries3)
+
+@printf("	add_entries for Dict{String, String}()\n")
+@btime add_entries(Dict{String, String}(), entries3)
+
+@printf(".\nSample #4 Key => Integer , Size => 10^7 entries\n.\n")
+
+sample1 = rand(Int, 10^7, 2)
+entries1 = Vector{Pair{Int, Int}}()
+sizehint!(entries1, 10^7)
+for i = 1 : 10^7
+	push!(entries1, Pair{Int, Int}(sample1[i, 1], sample1[i, 2]))
+end
+
+@printf("	add_entries for RobinDict()\n")
+@btime add_entries(RobinDict(), entries1)
+
+@printf("	add_entries for Dict()\n")
+@btime add_entries(Dict(), entries1)
+
+@printf("	add_entries for RobinDict{Int, Int}()\n")
+@btime add_entries(RobinDict{Int, Int}(), entries1)
+
+@printf("	add_entries for Dict{Int, Int}()\n")
+@btime add_entries(Dict{Int, Int}(), entries1)
+
+@printf(".\nSample #5 Key => Integer , Size => 10^5 entries\n.\n")
+
+sample1 = rand(Int, 10^5, 2)
+entries1 = Vector{Pair{Int, Int}}()
+sizehint!(entries1, 10^5)
+for i = 1 : 10^5
+	push!(entries1, Pair{Int, Int}(sample1[i, 1], sample1[i, 2]))
+end
+
+@printf("	add_entries for RobinDict()\n")
+@btime add_entries(RobinDict(), entries1)
+
+@printf("	add_entries for Dict()\n")
+@btime add_entries(Dict(), entries1)
+
+@printf("	add_entries for RobinDict{Int, Int}()\n")
+@btime add_entries(RobinDict{Int, Int}(), entries1)
+
+@printf("	add_entries for Dict{Int, Int}()\n")
+@btime add_entries(Dict{Int, Int}(), entries1)
+
+@printf(".\nSample #6 Key => Float32 , Size => 10^5 entries\n.\n")
+
+sample2 = rand(Float32, 10^5, 2)
+entries2 = Vector{Pair{Float32, Float32}}()
+sizehint!(entries2, 10^5)
+for i = 1 : 10^5
+	push!(entries2, Pair{Float32, Float32}(sample1[i, 1], sample1[i, 2]))
+end
+
+@printf("	add_entries for RobinDict()\n")
+@btime add_entries(RobinDict(), entries2)
+
+@printf("	add_entries for Dict()\n")
+@btime add_entries(Dict(), entries2)
+
+@printf("	add_entries for RobinDict{Float32, Float32}()\n")
+@btime add_entries(RobinDict{Float32, Float32}(), entries2)
+
+@printf("	add_entries for Dict{Float32, Float32}()\n")
+@btime add_entries(Dict{Float32, Float32}(), entries2)
+
+
+
+@printf(".\nSample #7 Key => String , Size => 10^5 entries\n.\n")
+
+entries3 = Vector{Pair{String, String}}()
+sizehint!(entries3, 10^5)
+for i = 1 : 10^5
+	push!(entries3, Pair{String, String}(randstring(), randstring()))
+end
+
+@printf("	add_entries for RobinDict()\n")
+@btime add_entries(RobinDict(), entries3)
+
+@printf("	add_entries for Dict()\n")
+@btime add_entries(Dict(), entries3)
+
+@printf("	add_entries for RobinDict{String, String}()\n")
+@btime add_entries(RobinDict{String, String}(), entries3)
+
+@printf("	add_entries for Dict{String, String}()\n")
+@btime add_entries(Dict{String, String}(), entries3)
+
+
+## Plots
+
+get_load_factor(h::AbstractDict) = (h.count / length(h.keys))
+
+function get_mean_dibs(h::RobinDict)
+	sz = length(h.keys)
+	dibs = zeros(Int8, sz)
+	for i = 1:sz
+		if isslotfilled(h, i)
+			dibs[i] = calculate_distance(h, i)
+		end
+	end
+	mean(dibs)
+end
+
+function get_variance_dibs(h::RobinDict)
+	sz = length(h.keys)
+	dibs = zeros(Int8, sz)
+	for i = 1:sz
+		if isslotfilled(h, i)
+			dibs[i] = calculate_distance(h, i)
+		end
+	end
+	var(dibs)
+end
+
+function plot_helper_add_entries(h::RobinDict, entries::Vector{Pair{K, V}}) where {K, V}
+	num = 0
+	sz = length(entries)
+	sq = floor(sqrt(sz))
+	x = Int[]
+	lf = Float32[]
+	xx = Int[]
+	mean_dibs = Float32[]
+	var_dibs = Float32[]
+	for (k, v) in entries
+		push!(x, num)
+		push!(lf, get_load_factor(h))
+		if (num % sq == 0)
+			push!(mean_dibs, get_mean_dibs(h))
+			push!(var_dibs, get_variance_dibs(h))
+			push!(xx, num)
+		end
+		h[k] = v
+		num += 1
+	end
+	push!(x, num)
+	push!(lf, get_load_factor(h))
+	if (num % sq == 0)
+		push!(mean_dibs, get_mean_dibs(h))
+		push!(var_dibs, get_variance_dibs(h))
+		push!(xx, num)
+	end
+	y = [lf]
+	yy = [mean_dibs var_dibs]
+	png(plot(x, y, label = ["Load Factor"]), "lf_$(Int(sz/1000))K @$(ROBIN_DICT_LOAD_FACTOR) L.F")
+	png(plot(xx, yy, label = ["mean(DIB)", "var(DIB)"]), "dibs_$(Int(sz/1000))K  @$(ROBIN_DICT_LOAD_FACTOR) L.F")
+end
+
+sample1 = rand(Int, 10^6, 2)
+entries1 = Vector{Pair{Int, Int}}()
+sizehint!(entries1, 10^6)
+for i = 1 : 10^6
+	push!(entries1, Pair{Int, Int}(sample1[i, 1], sample1[i, 2]))
+end
+
+plot_helper_add_entries(RobinDict{Int, Int}(), entries1)
\ No newline at end of file
diff --git a/test/runtests.jl b/test/runtests.jl
index df24b9d..23d4b0c 100644
--- a/test/runtests.jl
+++ b/test/runtests.jl
@@ -27,7 +27,8 @@ tests = ["int_set",
          "circular_buffer",
          "sorting",
          "priority_queue", 
-         "fenwick"
+         "fenwick", 
+         "robin_dict"
         ]
 
 if length(ARGS) > 0
diff --git a/test/test_circular_buffer.jl b/test/test_circular_buffer.jl
index 9b3cb78..603859a 100644
--- a/test/test_circular_buffer.jl
+++ b/test/test_circular_buffer.jl
@@ -44,11 +44,6 @@
         end
     end
     
-    @testset "other constructor" begin
-        cb = CircularBuffer(10)
-        @test length(cb) == 0
-        @test typeof(cb) <: CircularBuffer{Any}
-    end
     
     @testset "pushfirst" begin
         cb = CircularBuffer{Int}(5)  # New, empty one for full test coverage
diff --git a/test/test_robin_dict.jl b/test/test_robin_dict.jl
new file mode 100644
index 0000000..82cf7a3
--- /dev/null
+++ b/test/test_robin_dict.jl
@@ -0,0 +1,427 @@
+include("../src/robin_dict.jl")
+
+@testset "Constructors" begin
+    h1 = RobinDict()
+    @test length(h1) == 0
+    @test isempty(h1) == true
+    @test h1.idxfloor == 0
+    @test length(h1.keys) == 16
+    @test length(h1.vals) == 16
+    @test length(h1.hashes) == 16
+    @test eltype(h1) == Pair{Any, Any}
+    @test keytype(h1) == Any
+    @test valtype(h1) == Any
+end
+
+@testset "RobinDict" begin
+    h = RobinDict()
+    for i=1:10000
+        h[i] = i+1
+    end
+    for i=1:10000
+        @test (h[i] == i+1)
+    end
+    for i=1:2:10000
+        delete!(h, i)
+    end
+    for i=1:2:10000
+        h[i] = i+1
+    end
+    for i=1:10000
+        @test (h[i] == i+1)
+    end
+    for i=1:10000
+        delete!(h, i)
+    end
+    @test isempty(h)
+    h[77] = 100
+    @test h[77] == 100
+    for i=1:10000
+        h[i] = i+1
+    end
+    for i=1:2:10000
+        delete!(h, i)
+    end
+    for i=10001:20000
+        h[i] = i+1
+    end
+    for i=2:2:10000
+        @test h[i] == i+1
+    end
+    for i=10000:20000
+        @test h[i] == i+1
+    end
+    h = RobinDict{Any,Any}("a" => 3)
+    @test h["a"] == 3
+    h["a","b"] = 4
+    @test h["a","b"] == h[("a","b")] == 4
+    h["a","b","c"] = 4
+    @test h["a","b","c"] == h[("a","b","c")] == 4
+
+    @testset "eltype, keytype and valtype" begin
+        @test eltype(h) == Pair{Any,Any}
+        @test keytype(h) == Any
+        @test valtype(h) == Any
+
+        td = RobinDict{AbstractString,Float64}()
+        @test eltype(td) == Pair{AbstractString,Float64}
+        @test keytype(td) == AbstractString
+        @test valtype(td) == Float64
+        @test keytype(Dict{AbstractString,Float64}) === AbstractString
+        @test valtype(Dict{AbstractString,Float64}) === Float64
+    end
+    # test rethrow of error in ctor
+    @test_throws DomainError RobinDict((sqrt(p[1]), sqrt(p[2])) for p in zip(-1:2, -1:2))
+end
+
+@testset "RobinDict on pairs" begin
+	let x = RobinDict(3=>3, 5=>5, 8=>8, 6=>6)
+	    pop!(x, 5)
+	    for k in keys(x)
+	        RobinDict{Int,Int}(x)
+	        @test k in [3, 8, 6]
+	    end
+	end
+    
+    let y = RobinDict{Any, Int}(3=>3, 5=>5, "8"=>8, 6=>6)
+        pop!(y, "8")
+        for k in keys(y)
+            RobinDict{Int,Int}(y)
+            @test k in [3, 5, 6]
+        end
+    end
+
+    d = @inferred RobinDict(Pair(1,1), Pair(2,2), Pair(3,3))
+    @test isa(d, RobinDict)
+    @test d == RobinDict(1=>1, 2=>2, 3=>3)
+    @test eltype(d) == Pair{Int,Int}
+end
+
+@testset "KeyError" begin
+    let z = RobinDict()
+        get_KeyError = false
+        try
+            z["a"]
+        catch _e123_
+            get_KeyError = isa(_e123_,KeyError)
+        end
+        @test get_KeyError
+    end
+end
+
+@testset "Filter function" begin
+    _d = RobinDict("a"=>0)
+    @test isa([k for k in filter(x->length(x)==1, collect(keys(_d)))], Vector{String})
+    
+    h = RobinDict{Int, Int}()
+    for i in 1:100
+        h[i] = i
+    end
+    filter!(x->isodd(x.first), h)
+    for i in 1:2:100
+        @test h[i] == i
+    end
+end
+
+@testset "typeof" begin
+    d = RobinDict(((1, 2), (3, 4)))
+    @test d[1] === 2
+    @test d[3] === 4
+    d2 = RobinDict(1 => 2, 3 => 4)
+    d3 = RobinDict((1 => 2, 3 => 4))
+    @test d == d2 == d3
+    @test typeof(d) == typeof(d2) == typeof(d3) == RobinDict{Int,Int}
+
+    d = RobinDict(((1, 2), (3, "b")))
+    @test d[1] === 2
+    @test d[3] == "b"
+    d2 = RobinDict(1 => 2, 3 => "b")
+    d3 = RobinDict((1 => 2, 3 => "b"))
+    @test d == d2 == d3
+    @test typeof(d) == typeof(d2) == typeof(d3) == RobinDict{Int,Any}
+
+    d = RobinDict(((1, 2), ("a", 4)))
+    @test d[1] === 2
+    @test d["a"] === 4
+    d2 = RobinDict(1 => 2, "a" => 4)
+    d3 = RobinDict((1 => 2, "a" => 4))
+    @test d == d2 == d3
+    @test typeof(d) == typeof(d2) == typeof(d3) == RobinDict{Any,Int}
+
+    d = RobinDict(((1, 2), ("a", "b")))
+    @test d[1] === 2
+    @test d["a"] == "b"
+    d2 = RobinDict(1 => 2, "a" => "b")
+    d3 = RobinDict((1 => 2, "a" => "b"))
+    @test d == d2 == d3
+    @test typeof(d) == typeof(d2) == typeof(d3) == RobinDict{Any,Any}
+end
+
+@testset "type of RobinDict constructed from varargs of Pairs" begin
+    @test RobinDict(1=>1, 2=>2.0) isa RobinDict{Int,Real}
+    @test RobinDict(1=>1, 2.0=>2) isa RobinDict{Real,Int}
+    @test RobinDict(1=>1.0, 2.0=>2) isa RobinDict{Real,Real}
+
+    for T in (Nothing, Missing)
+        @test RobinDict(1=>1, 2=>T()) isa RobinDict{Int,Union{Int,T}}
+        @test RobinDict(1=>T(), 2=>2) isa RobinDict{Int,Union{Int,T}}
+        @test RobinDict(1=>1, T()=>2) isa RobinDict{Union{Int,T},Int}
+        @test RobinDict(T()=>1, 2=>2) isa RobinDict{Union{Int,T},Int}
+    end
+end
+
+@testset "equality" for eq in (isequal, ==)
+    @test  eq(RobinDict(), RobinDict())
+    @test  eq(RobinDict(1 => 1), RobinDict(1 => 1))
+    @test !eq(RobinDict(1 => 1), RobinDict())
+    @test !eq(RobinDict(1 => 1), RobinDict(1 => 2))
+    @test !eq(RobinDict(1 => 1), RobinDict(2 => 1))
+
+    # Generate some data to populate dicts to be compared
+    data_in = [ (rand(1:1000), randstring(2)) for _ in 1:1001 ]
+
+    # Populate the first dict
+    d1 = RobinDict{Int, AbstractString}()
+    for (k, v) in data_in
+        d1[k] = v
+    end
+    data_in = collect(d1)
+    # shuffle the data
+    for i in 1:length(data_in)
+        j = rand(1:length(data_in))
+        data_in[i], data_in[j] = data_in[j], data_in[i]
+    end
+    # Inserting data in different (shuffled) order should result in
+    # equivalent dict.
+    d2 = RobinDict{Int, AbstractString}()
+    for (k, v) in data_in
+        d2[k] = v
+    end
+
+    @test eq(d1, d2)
+    d3 = copy(d2)
+    d4 = copy(d2)
+    # Removing an item gives different dict
+    delete!(d1, data_in[rand(1:length(data_in))][1])
+    @test !eq(d1, d2)
+    # Changing a value gives different dict
+    d3[data_in[rand(1:length(data_in))][1]] = randstring(3)
+    !eq(d1, d3)
+    # Adding a pair gives different dict
+    d4[1001] = randstring(3)
+    @test !eq(d1, d4)
+
+    @test eq(RobinDict(), sizehint!(RobinDict(),96))
+
+    # Dictionaries of different types
+    @test_throws MethodError eq(RobinDict(1 => 2), RobinDict("dog" => "bone"))
+    @test eq(RobinDict{Int,Int}(), RobinDict{AbstractString,AbstractString}())
+end
+
+@testset "equality special cases" begin
+    @test RobinDict(1=>0.0) == RobinDict(1=>-0.0)
+    @test !isequal(RobinDict(1=>0.0), RobinDict(1=>-0.0))
+
+    @test RobinDict(0.0=>1) != RobinDict(-0.0=>1)
+    @test !isequal(RobinDict(0.0=>1), RobinDict(-0.0=>1))
+
+    @test RobinDict(1=>NaN) != RobinDict(1=>NaN)
+    @test isequal(RobinDict(1=>NaN), RobinDict(1=>NaN))
+
+    @test RobinDict(NaN=>1) == RobinDict(NaN=>1)
+    @test isequal(RobinDict(NaN=>1), RobinDict(NaN=>1))
+
+    @test ismissing(RobinDict(1=>missing) == RobinDict(1=>missing))
+    @test isequal(RobinDict(1=>missing), RobinDict(1=>missing))
+
+    @test RobinDict(missing=>1) == RobinDict(missing=>1)
+    @test isequal(RobinDict(missing=>1), RobinDict(missing=>1))
+end
+
+@testset "get!" begin 
+    f(x) = x^2
+    d = RobinDict(8=>19)
+    @test get!(d, 8, 5) == 19
+    @test get!(d, 19, 2) == 2
+
+    @test get!(d, 42) do  # d is updated with f(2)
+        f(2)
+    end == 4
+
+    @test get!(d, 42) do  # d is not updated
+        f(200)
+    end == 4
+
+    @test get(d, 13) do   # d is not updated
+        f(4)
+    end == 16
+
+    @test d == RobinDict(8=>19, 19=>2, 42=>4)
+end
+
+@testset "push!" begin
+    d = RobinDict()
+    @test push!(d, 'a' => 1) === d
+    @test d['a'] == 1
+    @test push!(d, 'b' => 2, 'c' => 3) === d
+    @test d['b'] == 2
+    @test d['c'] == 3
+    @test push!(d, 'd' => 4, 'e' => 5, 'f' => 6) === d
+    @test d['d'] == 4
+    @test d['e'] == 5
+    @test d['f'] == 6
+    @test length(d) == 6
+end
+
+@testset "pop!" begin
+    d = RobinDict(1=>2, 3=>4)
+    @test pop!(d, 1) == 2
+    @test_throws KeyError pop!(d, 1)
+    @test pop!(d, 1, 0) == 0
+    @test pop!(d) == (3=>4)
+    @test_throws ArgumentError pop!(d)
+end
+
+@testset "keys as a set" begin
+    d = RobinDict(1=>2, 3=>4)
+    @test keys(d) isa AbstractSet
+    @test empty(keys(d)) isa AbstractSet
+    let i = keys(d) ∩ Set([1,2])
+        @test i isa AbstractSet
+        @test i == Set([1])
+    end
+    @test Set(string(k) for k in keys(d)) == Set(["1","3"])
+end
+
+@testset "find" begin
+    @test findall(isequal(1), RobinDict(:a=>1, :b=>2)) == [:a]
+    @test sort(findall(isequal(1), RobinDict(:a=>1, :b=>1))) == [:a, :b]
+    @test isempty(findall(isequal(1), RobinDict()))
+    @test isempty(findall(isequal(1), RobinDict(:a=>2, :b=>3)))
+
+    @test findfirst(isequal(1), RobinDict(:a=>1, :b=>2)) == :a
+    @test findfirst(isequal(1), RobinDict(:a=>1, :b=>1, :c=>3)) in (:a, :b)
+    @test findfirst(isequal(1), RobinDict()) === nothing
+    @test findfirst(isequal(1), RobinDict(:a=>2, :b=>3)) === nothing
+end
+
+@testset "haskey" begin
+    h = RobinDict(1=>2, 2=>3)
+    @test haskey(h, 1) == true
+    @test haskey(h, 2) == true
+    @test haskey(h, 3) == false
+    @test_throws MethodError haskey(h, "1")
+end
+
+@testset "getkey" begin
+    h = RobinDict(1=>2, 3 => 6, 5=>10)
+    @test getkey(h, 1, 7) == 1
+    @test getkey(h, 4, 6) == 6
+    @test_throws MethodError getkey(h, "1", 8)
+end
+
+@testset "empty" begin
+    h = RobinDict()
+    for i=1:1000
+        h[i] = i+1
+    end
+    length0 = length(h.hashes)
+    empty!(h)
+    @test h.count == 0
+    @test h.idxfloor == 0
+    @test length(h.hashes) == length(h.keys) == length(h.vals) == length0
+end
+
+@testset "ArgumentError" begin
+    @test_throws ArgumentError RobinDict(0)
+    @test_throws ArgumentError RobinDict([1])
+    @test_throws ArgumentError RobinDict([(1,2),0])
+end
+
+@testset "empty tuple" begin
+    h = RobinDict(())
+    @test length(h) == 0
+end
+
+@testset "get_idxfloor" begin
+    h = RobinDict()
+    @test get_idxfloor(h) == 0
+    
+    h["a"] = 1
+    h[2] = "b"
+    @test h.idxfloor == get_idxfloor(h)
+    pop!(h)
+    @test h.idxfloor == get_idxfloor(h)
+    pop!(h)
+    @test h.idxfloor == get_idxfloor(h) == 0 
+end
+
+@testset "invariants" begin
+    h1 = RobinDict{Int, Int}()
+    for i in 1:300
+        h1[i] = i
+    end
+    
+    for i in 1:length(h1.keys)
+        if isslotfilled(h1, i)
+            @test hash_key(h1.keys[i]) == h1.hashes[i]
+        end
+    end
+
+    h2 = RobinDict{Float64, Float64}()
+    for i in 1:300
+        h2[rand()] = rand()
+    end
+    
+    for i in 1:length(h2.keys)
+        if isslotfilled(h2, i)
+            @test hash_key(h2.keys[i]) == h2.hashes[i]
+        end
+    end
+
+    h3 = RobinDict{String, Int}()
+    for i in 1:300
+        h3[randstring()] = i
+    end
+    
+    for i in 1:length(h3.keys)
+        if isslotfilled(h3, i)
+            @test hash_key(h3.keys[i]) == h3.hashes[i]
+        end
+    end
+
+    max_disp = 0
+    function check_invariants(h::RobinDict)
+        cnt = 0
+        min_idx = 0
+        sz = length(h.keys)
+        for i=1:length(h.keys)
+            isslotfilled(h, i) || continue
+            (min_idx == 0) && (min_idx = i)
+            @assert hash_key(h.keys[i]) == h.hashes[i]
+            @assert (h.hashes[i] & 0x80000000) != 0
+            cnt += 1
+            @assert typeof(h.hashes[i]) == UInt32
+            des_ind = desired_index(h.hashes[i], sz)
+            pos_diff = 0
+            if (i >= des_ind)
+                pos_diff = i - des_ind
+            else
+                pos_diff = sz - des_ind + i
+            end
+            dist = calculate_distance(h, i)
+            @assert dist == pos_diff
+            max_disp = max(max_disp, dist)
+            distlast = (i != 1) ? isslotfilled(h, i-1) ? calculate_distance(h, i-1) : 0 : isslotfilled(h, sz) ? calculate_distance(h, sz) : 0
+            @assert dist <= distlast + 1
+        end
+        @assert h.idxfloor == min_idx
+        @assert cnt == length(h)
+    end
+
+    h = RobinDict()
+    for i = 1:10000
+        h[i] = i+1
+    end
+    check_invariants(h)
+end 
\ No newline at end of file
diff --git a/test/test_sorted_containers.jl b/test/test_sorted_containers.jl
index 6981218..3db88ad 100644
--- a/test/test_sorted_containers.jl
+++ b/test/test_sorted_containers.jl
@@ -473,7 +473,6 @@ function testSortedDictMethods()
     my_assert(co == Forward)
     my_assert(haskey(m1, 71))
     my_assert(!haskey(m1, 77))
-    my_assert(get(m1, 70, nothing) == nothing)
     my_assert(get(m1, 70, -45.2) == -45.2)
     my_assert(get(m1, 83, -45.2) == convert(Float64,83)^2)
     h = get!(m1, 5, 27.0)
@@ -486,7 +485,6 @@ function testSortedDictMethods()
     my_assert(getkey(m1,7, 9) == 7)
     my_assert(getkey(m1,7.0, 9) == 7)
     my_assert(getkey(m1,12, 9) == 9)
-    my_assert(getkey(m1,12, nothing) == nothing)
     delete!(m1, 17)
     my_assert(length(m1) == length(ww) - 1)
     my_assert(deref_key((m1,advance((m1,findkey(m1,13))))) == 19)