HashMap equality calculated incorrectly

[fmw]

The following hashCodes should not be equal, but they are:

expect(HashMap.of(["a", 1], ["b", 0]).hashCode()).not.toBe(HashMap.of(["a", 0], ["b", 1]).hashCode());

The reason for this is that the HashMap hash code is calculated for the pairs in isolation, combining the hash codes of the kv-pairs and summing them up.

Calculating the pairs in isolation is correct because I think the order is not guaranteed in a HashMap (otherwise you could just send the whole list entries to fieldsToHashCode instead).

Adding up the hash code of the key and the value is not, however, because that produces the false match as demonstrated above, as adding doesn't guarantee the uniqueness of the pairs of keys and values.

Something like this should fix it in the HashMap implementation:

HashMap.prototype.hashCode = function () {
  return this.hamt.fold(function (acc, value, key) {
    return acc + 37 * (Comparison_1.getHashCode(key) * Comparison_1.getHashCode(value));
  }, 0);
};

(Thank you for creating prelude-ts, by the way, our team has gotten a lot of value out of this library and I absolutely love it).

[emmanueltouzery]

Hi, first off thank you for the kind words! Much appreciated.

Generally speaking it's not a correctness issue if there are hashcode collisions.

For instance: https://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#hashCode()

It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

As they write though, avoiding collisions should be good for performance. I would most likely merge a PR that would change this behavior (assuming it doesn't slow down computation time for the hashcode and it's still correct), if it's only a potential performance issue however I'm unlikely to modify it myself at this point.

[fmw]

Thanks for the reply. I didn't check if the equals result was correct for this input.

Our React state architecture needs hashCodes to be unique to detect changes in our store, because we use prelude-ts to enable us to do very efficient comparisons of the state in the store using the hash codes.

React is constantly asking "did the store change?" and the store is a big, complex tree structure. As we are using immutable values the hashCodes are idempotent, so we cache them inside of our objects. This makes this repeated question from React a simple integer comparison, rather than having to recalculate equality for the whole tree structure every time.

I'd be happy to make a PR, but I can't get prelude-ts to compile locally.

When I run npm i I get:

1025         : K extends `${number}`
                         ~~~

node_modules/@types/lodash/common/object.d.ts:1026:19 - error TS1005: ':' expected.

1026             ? '0' extends keyof T
                       ~~~~~~~

node_modules/@types/lodash/common/object.d.ts:1026:33 - error TS1005: ';' expected.

1026             ? '0' extends keyof T

(and so forth, just included a small part of the output).

Is there a specific version of node.js I should use? I tried with Node.js v16.14.0 and v18.12.0. Also, maybe a dependency has changed between your local version and what is in NPM? This could be fixed by adding or sharing a package-lock.json.

[emmanueltouzery]

it's got to be about your typescript version. i'd expect the tsc specified in prelude's package.json to work. npm test doesn't work for you either? Maybe you could try to bring prelude's typescript version in your PATH.. In prelude's folder:

export PATH=node_modules/typescript/bin:$PATH
npm test

[Annoiiyed]

Hi again! I contributed a while ago but have a new github account, so if you see a ghost commit somewhere, that's me

I wanted to see if I could get the tests to run with the given instructions, but with a fresh install of nodejs Gallium, simply running npm i fails for me as well :) could you maybe provide your lockfile, just to make sure its not an upstream package issue?

[emmanueltouzery]

hmm indeed maybe not putting the package.lock in the repo was simply stupid :( try this: https://www.dropbox.com/s/pyudv9asqp711rp/package-lock.json?dl=0

but i kinda doubt that's the problem. might be wrong though.

[fmw]

Yes, that fixes it, thanks for sharing. I will look into making a merge request and will get back to you.

[emmanueltouzery]

hmm. damn. i'll get that package lock in the repo presumably tonight then. my bad :grimacing:

[fmw]

I've created a PR: https://github.com/emmanueltouzery/prelude-ts/pull/67

The build is failing, but if you add the package-lock.json that will fix itself, I think.

I also saw some npm audit issues while running npm install. It would be great to fix those as well if you are are adding the package-lock.json anyway, but if you don't have the time I'll make a PR for that too.

[emmanueltouzery]

the npm audit issues are i think for test dependencies, which are just for benchmarks comparing to alternatives. the library itself only has two dependencies, list and hamt_plus. But if you can, i'd merge a PR!

it seems even after adding the package lock tests are still failing on CI, i'm not quite sure why.

[Annoiiyed]

After some testing I think its because the pipelines use Yarn (and thus don't read NPM's package lock)

[emmanueltouzery]

Ah yes, it's configured through .circleci/config.yml

Should be straightforward to fix. Well spotted!!

[Annoiiyed]

Yep, though I also spotted another minute thing in the pipeline, so I created https://github.com/emmanueltouzery/prelude-ts/pull/72 :)

[fmw]

@emmanueltouzery the pipeline is now green https://github.com/emmanueltouzery/prelude-ts/pull/67

[emmanueltouzery]

published 1.0.5 on npm with the changes, that should be it! thank you again!