#1485 js: Map doesn't handle equal hash codes

dsav Fri 8 Apr 2011

Please, consider the following code:

@Js
internal const class MyKey {
  override Int hash() { 42 }
  
  override Bool equals(Obj? t) {
    echo("equals called")
    return t === this    
  }
}

// somewhere in the code:
MyKey:Str map := [:]
key0 := MyKey()
key1 := MyKey()
map[key0] = "key0"
map[key1] = "key1"
echo(map[key0])
echo(map[key1])

This will print key1 twice, MyKey.equals never called. So, Map in JavaScript doesn't correctly handle objects with equal hash codes.

Upd: We investigated that Map uses toStr instead of hash method in JavaScript. So, if different objects return the same toStr value, they are considered the same object. So, actually it's two bugs:

  1. toStr is used to get hash code, which violates the method's contract
  2. equals is never called if "hash codes" are equal

andy Fri 8 Apr 2011

Promoted to ticket #1485 and assigned to andy

JavaScript does not contain native support for hash tables - so we use an Object and properties to simulate. So from an implementation perspective the keys will be strings. The issue is that JavaScript also does not have native support for something like Obj.hash (see ticket #1464) - which we need to fix hashKey properly to generate a unique string key. So these two go hand-in-hand. But lets promote to a ticket to track.

Yuri Strot Fri 8 Apr 2011

This issue looks quite serious while we can't rely on the same behaviour of Map in Java and JS.

I think the simplest way to implement Obj.hash is to provide some number generator (like global counter or local time) on hash request to associate fantom object with unique number. Number generator can be improved in the future to provide good numbers for hash codes.

To get the same Map's contract for JavaScript we can use Java's HashMap approach: use key hashes as keys in JS map and list of objects with the same hash codes as values. In case of several keys with the same hash code we need to compare these keys using Obj.equals method. Such approach already implemented in the JS hashtable: http://www.timdown.co.uk/jshashtable/

If you agree on that but currently haven't enough time to implement it, I think our team can work on this. Does it make sense?

andy Fri 8 Apr 2011

This is not on my immediate radar - so you are welcome to take a stab at it.

Thats about right - we'll need a decent Obj.hash implementation - I think you'll have to use a global reference counter - or random number generator - since we only have ms precision with time. Probably should be lazily set on first call to hash if not overridden. Then fix up Map.js to handle key collisions.

andy Wed 9 Nov 2011

Ticket resolved in 1.0.61

Rewrote Map with a more proper implementation: changeset

This (and recent fixes) address several issues: #1464, #1680, #1682

Also fixed support for caseInsensitive maps - which were not working correctly before. Still does not support ordered maps - but I added a println if you set that field, just to remind anyone who forgets or is not aware.

andy Fri 11 Nov 2011

Still does not support ordered maps

Fixed - Map.ordered now properly supported

Login or Signup to reply.