Surprised by hashes of arrays of arrays
Shammah Chancellor
anonymous at coward.com
Thu Feb 27 14:00:04 PST 2014
On 2014-02-27 10:11:53 +0000, Jens Mueller said:
> Dear list,
>
> I stumbled over odd behavior which took quite some time of debugging.
> Sharing my results may help find a solution or just make others aware
> and reduce their debugging time.
>
> To illustrate consider the code:
>
> auto array1 = [ [1, 2], [3, 4] ];
> auto array2 = array1.dup;
> array2[0] = array2[0].dup;
>
> Does either hash(&array1) == hash(&array2) hold or hash(&array1) !=
> hash(&array2) where hash is defined as
> auto hash = &(typeid(array1).getHash);
> ?
>
> So I may be totally off here (please tell me), but it turns out that
> that both arrays have different hashes due to the way hashing is
> implemented. This, e.g., implies that equal arrays may be hashed to
> different values. Hence when you are using them as keys in an
> associative array results may be surprising.
> Note that I can make the problem more difficult to spot by using a
> struct that uses pointers or an array internally which is hidden by
> encapsulation.
>
> I find the behavior non-obvious but maybe there is reason. The current
> implementation considers only the direct contents of the struct's memory
> (the memory starting at array.ptr to array.length * size(array[0]) in
> case of dynamic arrays) and does *not* follow indirections (e.g. via
> pointers).
>
> This implies that a hash can be computed without considering all memory
> occupied by a value. In my current mental model of hashing I assumed
> that all bytes should be read by default.
>
> As you may conclude from this post I find this behavior odd. I expect a
> hash implementation to follow indirections by calling the hashing
> functions recursively. It looks to me as a case where the default is
> badly designed/implemented.
>
> Jens
You should get the same answer if in both cases they were static
arrays, but I believe array1.dup returns a slice to a heap allocated
array instead of the statically-sized array you originally had.
-S.
More information about the Digitalmars-d
mailing list