Order in keys and values for identical hash tables

[mahrud]

Shouldn't the order of keys and values of a hash table depend only on the hash? Why can I get two identical hash tables with different keys and values?

i1 : partition(even, {1,2,3,4,5}, {true, false})

o1 = HashTable{false => {1, 3, 5}}
               true => {2, 4}

o1 : HashTable

i2 : (keys oo, values oo)

o2 = ({true, false}, {{2, 4}, {1, 3, 5}})

o2 : Sequence

i3 : partition(even, {1,2,3,4,5}, {false, true})

o3 = HashTable{false => {1, 3, 5}}
               true => {2, 4}

o3 : HashTable

i4 : (keys oo, values oo)

o4 = ({false, true}, {{1, 3, 5}, {2, 4}})

o4 : Sequence

i5 : o1 === o3

o5 = true

i6 : keys o1 === keys o3

o6 = false

i7 : values o1 === values o3

o7 = false

Of course, I see that the buckets are different:

i13 : buckets o1

o13 = {{}, {(true, {2, 4}), (false, {1, 3, 5})}, {}, {}}

o13 : List

i14 : buckets o3

o14 = {{}, {(false, {1, 3, 5}), (true, {2, 4})}, {}, {}}

o14 : List

So is this just because the first element, 1, in the call to partition was odd? I don't think the output hash table itself should be affected by this.

[mahrud]

By the way, there's some code depending on this behavior, so we should be careful about changing it:

M2/M2/Macaulay2/m2/document.m2

Line 521 in 1fd2382

(ino, inp) := toSequence values partition(isOption, arg, {true, false});

[pzinn]

simpler example:

i1 : h1=hashTable{false=>1,true=>2}

o1 = HashTable{false => 1}
               true => 2

o1 : HashTable

i2 : h2=hashTable reverse{false=>1,true=>2}

o2 = HashTable{false => 1}
               true => 2

o2 : HashTable

i3 : keys h1

o3 = {true, false}

o3 : List

i4 : keys h2

o4 = {false, true}

o4 : List

i6 : h1===h2

o6 = true

[d-torrance]

For this particular case, it's because the hash table is small (the minimum size of 4 buckets), and so true and false get stuffed into the same bucket:

i1 : hash true % 4

o1 = 1

i2 : hash false % 4

o2 = 1

So the order in which they get stuffed affect where in the linked list they appear.

[mahrud]

That makes sense. Is this a feature or a misfeature in this case? Maybe we can make sure true and false don't have the same remainder mod 4?

[d-torrance]

Yeah, I think so -- see #3471.