# Trouble defining hash/isequal for an interval type

**URL:** <https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629>\
**Category:** General Usage\
**Tags:** question, dictionary, hash\
**Created:** [November 23, 2023, 9:01am UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629 "2023-11-23T09:01:31Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [November 23, 2023, 9:01am UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629/1 "2023-11-23T09:01:31Z")

</div>

I tried to practice on this topic, but evidently I still lack a lot of knowledge to be profitable.  
I would like to be able to merge the two dictionaries so that, for example, merge(da,db) ==db  
That is, having da and db keys equivalent, the second overwrites the first.  
Where am I wrong and/or what is missing?

```julia
julia> h=hash(13)
0xa9497f3bd292fe31

julia> Base.hash(a::Interval, h::UInt) = xor(Int(a.lo*10+a.hi), h)

julia> import Base.==

julia> ==(a::Interval, b::Interval) = a.lo <= b.lo <=a.hi || b.lo <= a.lo <=b.hi
== (generic function with 187 methods)

julia> Base.isequal(a::Interval, b::Interval) = a.lo <= b.lo <=a.hi || b.lo <= a.lo <=b.hi

julia> a=Interval(0,2)
[0, 2]

julia> b=Interval(2,4)
[2, 4]

julia> b==a
true

julia> a==b
true

julia> isequal(a,b)
true

julia> isequal(b,a)
true

julia> da=Dict(a=>'a')
Dict{Interval{Float64}, Char} with 1 entry:
  [0, 2] => 'a'

julia> db=Dict(b=>'b')
Dict{Interval{Float64}, Char} with 1 entry:
  [2, 4] => 'b'

julia> da[a]
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)

julia> da[b]
ERROR: KeyError: key [2, 4] not found
Stacktrace:
 [1] getindex(h::Dict{Interval{Float64}, Char}, key::Interval{Float64})
   @ Base .\dict.jl:484
 [2] top-level scope
   @ c:\Users\sprmn\.julia\environments\v1.9.0\IntervalArit1.jl:62

```

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [November 23, 2023, 12:04pm UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629/2 "2023-11-23T12:04:53Z")

</div>

It is a bit unclear to me what your goal is exactly. `a` and `b` are obviously different intervals, they just happen to have identical length. You (re)define `hash`, `==` and `isequal` for this type but you violate the constraint that `hash(a) == hash(b)` gives the same result as `isequal(a, b)`. See the docstring of `hash`:

```julia
Compute an integer hash code such that `isequal(x,y)` implies `hash(x)==hash(y)`. The
optional second argument `h` is another hash code to be mixed with the result.

```

This also explains why your Dict `da` does find not a compatible entry with `da[b]`.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [November 23, 2023, 1:35pm UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629/3 "2023-11-23T13:35:37Z")

</div>

> [@rocco\_sprmnt21](#):
>
> `==(a::Interval, b::Interval) = a.lo <= b.lo <=a.hi || b.lo <= a.lo <=b.hi`

In addition to the problem identified by @abraemer above (your `isequal` and `hash` functions are inconsistent), this is not a valid definition for `==` because it is not transitive.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 23, 2023, 2:54pm UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629/4 "2023-11-23T14:54:45Z")

</div>

This. The first thing you need to do is figure out what your equivalence classes are. Then implement checking if two intervals are in the same equivalence class for isequal. Finally implement hash that gives the same value for any two instances in the same equivalence class.

For intervals I presume you’d want to check that the endpoints of the interval are isequal. You could do other things though, like check that the first endpoint is equal or that the midpoint is equal. Those are kind of odd choices but they are valid equivalence classes.

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [November 24, 2023, 8:09am UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629/5 "2023-11-24T08:09:44Z")

</div>

> [@abraemer](#):
>
> It is a bit unclear to me what your goal is exactly

What I was trying to do was to use (clumsily, I understand from your, @stevengj and @StefanKarpinski’s answers) an idea seen in an ‘other post’ of which I don’t remember the link in which the hash() and ==() functions were redefined for a new User Type.  
The aim was to use a “special dictionary” to solve [this](https://discourse.julialang.org/t/how-to-separate-joint-and-disjoint-intervals-from-an-interval-vector/106515) problem.  
The idea was to emulate the groupby function (to create equivalence classes and put them together as requested by the OP (at least as I understood it), via the mergewith!(combine, d1,d2, … .)).

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 25, 2023, 11:20pm UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629/6 "2023-11-25T23:20:58Z")

</div>

I don’t get what the equivalence classes of intervals are supposed to be. Can you explain that?

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [November 26, 2023, 8:45am UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629/7 "2023-11-26T08:45:23Z")

</div>

No, of course. In the way I had defined the relation is not of equivalence as it has no transitive property (as pointed out by @stevengj).  
I just tried to explain (I use Google Translate to write in English :)) what I had improperly tried to do.  
I finally realized that I couldn’t do [what I wanted](https://discourse.julialang.org/t/how-to-separate-joint-and-disjoint-intervals-from-an-interval-vector/106515) using the Dict structure.

Below is an example, following your instructions

```julia
julia> using IntervalArithmetic

julia> import Base: hash,==, isequal

julia> hash(a::Interval) = hash(a.lo-a.hi)
hash (generic function with 102 methods)

julia> ==(a::Interval, b::Interval) = a.lo-a.hi == b.lo - b.hi
== (generic function with 188 methods)

julia> isequal(a::Interval, b::Interval) = isequal(a.lo-a.hi, b.lo - b.hi)
isequal (generic function with 29 methods)

julia> a=Interval(0,2)
[0, 2]

julia> b=Interval(2,4)
[2, 4]

julia> c=Interval(-3,-1)
[-3, -1]

julia> da=Dict(a=>"a")
Dict{Interval{Float64}, String} with 1 entry:
  [0, 2] => "a"

julia> dc=Dict(c=>'c')
Dict{Interval{Float64}, Char} with 1 entry:
  [-3, -1] => 'c'

julia> db=Dict(b=>'b')
Dict{Interval{Float64}, Char} with 1 entry:
  [2, 4] => 'b'
julia> mergewith((x...)->join(x,'-'), da,db,dc)        
Dict{Interval{Float64}, Any} with 1 entry:
  [0, 2] => "a-b-c"

```

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 26, 2023, 2:58pm UTC](https://discourse.julialang.org/t/trouble-defining-hash-isequal-for-an-interval-type/106629/8 "2023-11-26T14:58:46Z")

</div>

Yes, that looks correct—it considers all intervals with the same length to be equal.