Table has inconsistent hash

[rotu]

The hash of a Table depends on how that Table was derived.

This violates the prime rule of hashes (If two values compare equal, their hashes must also be equal) and results in corrupt data structures when Table is used as a key in a hashed container.

Example

import std/tables
import std/hashes

let t = ()
var a = toTable({t:t})
del(a,t)
let b = default(typeof(a))

assert a==b , "tables are equal"
# this following assertion fails!
assert hash(a) == hash(b), "table hashes are equal"

Current Output

Error: unhandled exception: /Users/dan/Documents/fates/nim/fates/issue.nim(11, 8) `hash(a) == hash(b)` table hashes are equal [AssertionDefect]

Expected Output

no error

Possible Solution

• I believe the issue is that the hash depends on the allocated table size, since this also fails:

var a=initTable[int,int](initialSize=10)
var b=initTable[int,int](initialSize=100)
assert a==b , "tables are equal"
# this following assertion fails!
assert hash(a) == hash(b), "table hashes are equal"

Additional Information

$ nim -v
Nim Compiler Version 1.6.6 [MacOSX: arm64]
Compiled at 2022-05-05
Copyright (c) 2006-2021 by Andreas Rumpf

active boot switches: -d:release -d:nimUseLinenoise

[rotu]

Workaround below. I'm not sure that this is a good idea (e.g. multiple parts of code may have conflicting hashes for the same object). I think this needs to be part of std/tables.

import std/[tables, hashes]

proc hash*[K,V](s: Table[K,V]): Hash =
  for p in pairs(s):
    result = result xor hash(p)
  result = !$result

[planetis-m]

Is there even a hash for Table? https://nim-lang.github.io/Nim/theindex.html#hash I think it picks the generic hash for objects.

[rotu]

@planetis-m Yes, that does seem to be the case, which bit me quite badly.

It would be nice if defining a new equality operator somehow undefined the hash function, so this would be caught at compile time.

Oddly enough, there’s an order-invariant hash for ordered tables of JSON nodes (rather than correctly defining the hash on the JsonNodeObj class)

Nim/lib/pure/json.nim

Line 499 in 800cb00

proc hash*(n: OrderedTable[string, JsonNode]): Hash =