Clojure

PersistentHashMap uses a hashing function that is incongruent with the equality function it uses

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: Release 1.3
  • Fix Version/s: Release 1.4
  • Component/s: None
  • Labels:
    None
  • Approval:
    Ok

Description

PersistentHashMap hashes its keys with Util.hash which simply calls Object.hashCode, but it compares its keys for equality using Util.equiv. This means:

user=> (clojure.lang.Util/equiv (Integer. -1) (Long. -1))
true
user=> (= (clojure.lang.Util/hash (Integer. -1)) (clojure.lang.Util/hash (Long. -1)))
false

which breaks the contract of a hash table (keys that are equal should hash to values that are equal).

The following bad behavior results:

user=> (def bad-map (clojure.lang.PersistentHashMap/create {(Long. -1) :here}))
#'user/bad-map
user=> (contains? bad-map (Integer. -1))
false
user=> (get bad-map (Integer. -1))
nil
user=> (= bad-map (clojure.lang.PersistentHashMap/create {(Integer. -1) :here}))
false

Compared to:

user=> (def bad-map (clojure.lang.PersistentHashMap/create {(Long. 0) :here}))
#'user/bad-map
user=> (contains? bad-map (Integer. 0))
true
user=> (get bad-map (Integer. 0))
:here
user=> (= bad-map (clojure.lang.PersistentHashMap/create {(Long. 0) :here}))
true

This bug also infects PersistentHashSet:

user=> #{(Long. 0) (Integer. 0)}
IllegalArgumentException Duplicate key: 0  clojure.lang.PersistentHashSet.createWithCheck (PersistentHashSet.java:56)
user=> #{(Long. -1) (Integer. -1)}
#{-1 -1}
user=> (contains? #{(Long. 0)} (Integer. 0))
true
user=> (contains? #{(Long. -1)} (Integer. -1))
false

Activity

Hide
Paul Stadig added a comment -

There may be a couple different ways to fix this. I think what would work is adding a Util.hashEquiv method that has the same equality semantics as Util.equiv and using that to hash keys instead.

I'd be glad to create a patch for that.

Show
Paul Stadig added a comment - There may be a couple different ways to fix this. I think what would work is adding a Util.hashEquiv method that has the same equality semantics as Util.equiv and using that to hash keys instead. I'd be glad to create a patch for that.
Hide
Paul Stadig added a comment -
Show
Paul Stadig added a comment - This ticket can be closed now. It is fixed by https://github.com/clojure/clojure/commit/b5f5ba2e15dc2f20e14e05141f7de7c6a3d91179

People

Vote (0)
Watch (2)

Dates

  • Created:
    Updated:
    Resolved: