I have a custom object Value which I want to use as a key to a Table.
So let's say we have something like:
var index = initOrderedTable[Value,Value]()
In this table, I want to be able to add and retrieve value-key pairs, like:
proc getIndex*(k: Value): Value =
if index.hasKey(k):
return index[k]
else:
return NoValue
proc setIndex*(k: Value, v: Value) =
index[k] = v
So far so good.
Since the keys of our table are custom objects, I also have the appropriate hash function (in the same file as getIndex and setIndex, like that:
proc hash*(v: Value): Hash {.inline.}=
# calculate the hash for the given value
Now, the way things are (as described), and although my hash function works fine, when testing the existing of an existing key in the table, it cannot be found. So, I thought it's not calculating the hash the way I told it to, but in a different way. (And I have verified this).
So... I decided to convert the table to an OrderedTable[Hash,Value], rename my hash function to something else like calculateHash and for every setIndex and getIndex, call calculateHash on the given key value, and use this - explicitly - as a key.
And it works beautifully and exactly as expected.
So, the question is rather simple:
How do I tell the Nim compiler to use my existing hash function for Value objects, e.g. in the case of Table search?
Did you put the hash after or before the procedures that indexed the table? The following code works as intended but as soon as you move the value below the set and get it fails of course.
import std/[tables, hashes]
proc hash(a: int): Hash =
result = hashes.hash(a)
echo "Used our hash"
var a: Table[int, int]
proc getIndex*(k: int): int =
if a.hasKey(k):
return a[k]
else:
return -1
proc setIndex*(k: int, v: int) =
a[k] = v
a[100] = 300
assert getIndex(300) == -1
assert getIndex(100) == 300
setIndex(3, 400)
assert getIndex(3) == 400
The Table is declared at the top of the file.
Then the getIndex and setIndex functions.
And I have played with placing the hash function both after getIndex and setIndex (with a forward declaration) and before.
The sole difference I can see in your example is me exporting the hash function (hash*) and declaring it {.inline.}. Perhaps that's the reason?
Let me experiment...
Another, slightly unrelated, question on the above:
I've compiled your example code. How many times do you see "Used our hash" being printed? Is that normal?
A tiny-bit more elaborate example (based on your example).
import std/[tables, hashes]
type
Value = ref object
i: int
var a: Table[Value, Value]
proc hash(a: Value): Hash
proc getIndex*(k: Value): int =
if a.hasKey(k):
return a[k].i
else:
return -1
proc setIndex*(k: Value, v: int) =
a[k] = Value(i: v)
proc hash(a: Value): Hash =
result = hashes.hash(a.i)
echo "Used our hash"
a[Value(i:100)] = Value(i:300)
assert getIndex(Value(i:300)) == -1
assert getIndex(Value(i:100)) == 300
setIndex(Value(i:3), 400)
assert getIndex(Value(i:3)) == 400
I see "Used our hash" twice. And it seems to me rather weird. Doesn't hasKey (in getIndex) hash the value first before looking it up? Or... doesn't setIndex hash the value before setting it?
So, I would expect at least 3 calls to the hash function (or perhaps 5, considering the 2 set-indexes)
I now read your edit. And yes, what you mention makes perfect sense. But it's not what I see...
Btw, the exact same thing happens when I move the hash to the end, or to the top...
Update example code (saved as hashy.nim):
import std/[tables, hashes]
type
Value = ref object
i: int
proc `==`*(a: Value, b: Value): bool =
result = a.i == b.i
echo "Used our =="
proc hash*(a: Value): Hash =
result = hashes.hash(a.i)
echo "Used our hash for " & $(a.i)
var a: Table[Value, Value]
proc getIndex*(k: Value): int =
if a.hasKey(k):
return a[k].i
else:
return -1
proc setIndex*(k: Value, v: int) =
a[k] = Value(i: v)
a[Value(i:100)] = Value(i:300)
assert getIndex(Value(i:300)) == -1
assert getIndex(Value(i:100)) == 300
setIndex(Value(i:3), 400)
assert getIndex(Value(i:3)) == 400
Compiled with nim c hashy.nim.
Running it gives me:
Used our hash for 100
Used our hash for 3
So, my conclusion is that our custom hash function is only getting called for direct index-assignments, e.g. a[k] = X
As the following works I can only say for some reason there is some odd reference indirection causing this issue.
import std/[tables, hashes]
type
Value = ref object
i: int
var a: Table[Value, Value]
proc hash(a: Value): Hash
proc `$`(a: Value): string = $(a[])
proc getIndex*(k: Value): int =
if a.hasKey(k):
return a[k].i
else:
return -1
proc setIndex*(k: Value, v: int) =
a[k] = Value(i: v)
proc hash(a: Value): Hash =
result = hashes.hash(a.i)
echo "Called this hash"
let
val100 = Value(i: 100)
val300 = Value(i: 300)
val3 = Value(i: 3)
a[val100] = Value(i: 300)
assert getIndex(val300) == -1
assert getIndex(val100) == 300
setIndex(val3, 400)
assert getIndex(val3) == 400