# Custom hash and equal functions for Map and Set collections

**URL:** <https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673>\
**Category:** 💡 Ideas\
**Tags:** proposal\
**Created:** [February 28, 2021, 9:24pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673 "2021-02-28T21:24:16Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [February 28, 2021, 9:24pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/1 "2021-02-28T21:24:16Z")

</div>

Sometimes object keys need a specific hash functions to speed up the search for especially large objects or they have circular dependencies. Sometimes it's not necessary to stringify the whole object. In other situations you need to keep original key's object (not string or some unique id). Therefore, almost all languages ​​which expose collections in their standard libraries have the ability to override the default hash and equal functions.

Similar to [collection-normalization proposal](https://github.com/tc39/proposal-collection-normalization) I propose add `hash` and `equals` methods during construction:

```javascript
const set = new Set(undefined, {
  hash(key) {
     return murmur3(key.name) ^ key.type
  },

  equals(lhs, rhs) {
    return (
      lhs.name == rhs.name && 
      lhs.type == rhs.type
    )
  }
})

set.add({ name: 'a', type: 0 })
set.add({ name: 'b', type: 1 })

```

Similar to `Map` and probably for equivalent weak collections.

Also this approach allow us reuse usually existing methods in the following way:

```javascript
class Vec2 {
  constructor(x, y) { this.x = x; this.y = y }

  static equals(a, b) { return a.x == b.x && a.y == b.y }
  static hash(v) { return fnv1a(v.x, fnv1a(v.y)) }
}

const pos2cell = new Map(undefined, Vec2)

```

It's pretty common request:

1. [data structures - JavaScript hashmap equivalent - Stack Overflow](https://stackoverflow.com/questions/368280/javascript-hashmap-equivalent/383540#383540)

2. [javascript - How to use ES6 Hash Map on any object without maintaing a reference (I.e. Java hashcode) - Stack Overflow](https://stackoverflow.com/questions/28357647/how-to-use-es6-hash-map-on-any-object-without-maintaing-a-reference-i-e-java-h)

3. [javascript - Define a custom hash() method for use with ES6 maps - Stack Overflow](https://stackoverflow.com/questions/31582852/define-a-custom-hash-method-for-use-with-es6-maps)

4. [javascript - Associative array without toString, etc - Stack Overflow](https://stackoverflow.com/questions/367440/associative-array-without-tostring-etc#367454)

---

<div class="post-metadata">

**Author:** ![aclaymore](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/aclaymore/32/501_2.png) [@aclaymore](https://es.discourse.group/u/aclaymore)\
**Post date:** [February 28, 2021, 10:15pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/2 "2021-02-28T22:15:02Z")

</div>

What would be considered a valid return type for the hash function? Only 32 bit integers?

Does appear that under-the-hood at least v8 uses 32bit int hash structures for Map and Set. Not sure about other JS engines [v8/ordered-hash-table.cc at dc712da548c7fb433caed56af9a021d964952728 · v8/v8 · GitHub](https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021d964952728/src/objects/ordered-hash-table.cc#L140-L152)

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [February 28, 2021, 10:59pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/3 "2021-02-28T22:59:05Z")

</div>

> [@aclaymore](#):
>
> What would be considered a valid return type for the hash function? Only 32 bit integers?

Yes, indeed. All hash table's implementations which I know use 32 or 64-bit unsigned integers for the result of the hash function.

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 1, 2021, 2:04pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/4 "2021-03-01T14:04:10Z")

</div>

another discussion:  
[https://esdiscuss.org/topic/maps-with-object-keys](https://esdiscuss.org/topic/maps-with-object-keys)

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [March 2, 2021, 12:48pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/5 "2021-03-02T12:48:25Z")

</div>

What's the value of this that the collection normalization proposal doesn't provide?

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 2, 2021, 1:43pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/6 "2021-03-02T13:43:23Z")

</div>

normalization proposal provide `coerceKey` and `coerceValue`. `coerceKey` has similar goal with `hash`, but returns string as a result. This proposal targets more low-level stuff and suggests returning a customized raw hash number for `hash` method. Also provide `equal` method which important for actual key comparison.

Hash lookup consists of two stages. It takes object key, calculate hash (currently it stringify object first) value and if this value exists in map the next step is compare stringified keys. This proposal suggesting provide ability to customize this stages by providing `hash` and `equals` in user space.

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 2, 2021, 1:56pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/7 "2021-03-02T13:56:39Z")

</div>

Examples in other languages.  
C++:

```javascript
using h = std::hash<int>;
auto hash = [](const Vec2& n) { return ((17 * 31 + h()(n.x)) * 31 + h()(n.y)) * 31; };
auto equal = [](const Vec2& l, const Vec2& r) { return l.x == r.x && l.y == r.y; };

std::unordered_map<Vec2, int, decltype(hash), decltype(equal)> map(32, hash, equal);

```

Rust:

```javascript
extern crate fnv;

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use fnv::FnvHasher;

#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
pub Vec2 {
  ...
}

let mut map = HashMap<Vec2, String, BuildHasherDefault<FnvHasher>>::default();

```

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [March 2, 2021, 2:39pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/8 "2021-03-02T14:39:00Z")

</div>

I get how it's different, but what is the _value added_?

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 2, 2021, 2:51pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/9 "2021-03-02T14:51:10Z")

</div>

I thought I covered the main reasons in enough detail in the original post. Provide lower-level control for the user over how objects are turned into a hash, by the way, sometimes hashing can be completely avoided. `coerceKey` does not provide this option. So hash function overloading and `coerceKey` are orthogonal things

---

<div class="post-metadata">

**Author:** ![mfulton26](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/mfulton26/32/578_2.png) [@mfulton26](https://es.discourse.group/u/mfulton26)\
**Post date:** [March 2, 2021, 2:54pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/10 "2021-03-02T14:54:09Z")

</div>

I for one am looking forward to [GitHub - tc39/proposal-record-tuple: ECMAScript proposal for the Record and Tuple value types. | Stage 2: it will change!](https://github.com/tc39/proposal-record-tuple) being implemented and I think it makes this no longer needed. Typically mutable objects shouldn't be used in a hash set or as a key in a hash map so this seems more ideal to me.

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [March 2, 2021, 11:45pm UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/11 "2021-03-02T23:45:16Z")

</div>

Hashing is generally necessary even for integers to get proper hash table performance because you need inputs to be sufficiently evenly distributed across the table to minimize the worst-case linear factor (which is effectively zero with the best hash functions). And it's worth noting that [most people don't even know how to set a table's load factor correctly](https://youtu.be/ncHmEUmJZf4?t=3065), [much less write a good hash function for hash tables unassisted](https://www.intigua.com/blog/good-and-bad-equals-and-hashcode).

I'm more in favor of using the proposed tuples and records for composite map keys than adding a dedicated hash function - it solves the same issue even better without subjecting the developer to stuff that generally should be implementation details.

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 3, 2021, 12:03am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/12 "2021-03-03T00:03:30Z")

</div>

> [@claudiameadows](#):
>
> Hashing is generally necessary even for integers to get proper hash table performance because you need inputs to be sufficiently evenly distributed across the table to minimize the worst-case linear factor

I meant case when object already have some linearly grow unique id or id generated by PRNG with linear distribution

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 3, 2021, 12:17am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/13 "2021-03-03T00:17:41Z")

</div>

Regarding use tuples / records instead objects for keys. Well this have some limitations. Like what if you already receive objects which need to use as keys? What if this objects required prototypes, what if this objects required circular references? All this not possible with key records.

Look at Python which also have tuples. Python still allow you override hash and equal for dicts: [Glossary — Python 2.7.18 documentation](https://docs.python.org/2/glossary.html#term-hashable) via overriding ` __hash__ ()` and ` __eq__ ()`/` __cmp__ ()` for specific object.

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [March 10, 2021, 7:08am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/14 "2021-03-10T07:08:24Z")

</div>

If you're that concerned about performance, you'd be better off writing your own hash table implementation.

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 10, 2021, 8:11am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/15 "2021-03-10T08:11:42Z")

</div>

> If you're that concerned about performance, you'd be better off writing your own hash table implementation.  
> Currently it's only one way. But it's not optimal. Because built-in Map/Set written on native C++ so you never outperform this. But that implementations already have and use `hash` and `equal` methods that we could overload / customize in user space. So why not do it?

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [March 12, 2021, 7:47am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/16 "2021-03-12T07:47:15Z")

</div>

I don't see implementations doing anything different than what Abseil does with _their_ hash tables - rehashing the hash result. And as for equality, I expect that tuples will bring only negligible overhead compared to raw results.

Personally, I would recommend waiting until V8 implements the record/tuple proposal, then [adding support for your proposal](https://github.com/v8/v8/blob/d9d13b381492a379c46e77a6ed424cfb5e7573dd/src/builtins/builtins-collections-gen.cc) and benchmarking it.

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 12, 2021, 11:26am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/17 "2021-03-12T11:26:07Z")

</div>

This proposal not only about performance =) Please see starter message. I list there quite a few things that tuples / records cannot solve by their nature

---

<div class="post-metadata">

**Author:** ![MaxGraey](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/maxgraey/32/651_2.png) [@MaxGraey](https://es.discourse.group/u/MaxGraey)\
**Post date:** [March 12, 2021, 11:44am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/18 "2021-03-12T11:44:27Z")

</div>

And we don't wait tuples to solve part of this problem due to tuple:

```javascript
class PointListNode extends Point { 
  constructor(x=0, y=0) {
    super(x, y);
    this.next = null;
    this.prev = null;
  }
  ...
  // add
  // remove
}

let map = new Map
let root = new PointListNode
map.set(#[root.x, root.y], someValue)

```

could be resolved via:

```javascript
map.set(`${root.x}${root.y}`, someValue)

```

But this not solve problem when you need have key as Object (not tuple or string) to iterate key-value later and have full access to this keyed object

---

<div class="post-metadata">

**Author:** ![claudiameadows](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/claudiameadows/32/126_2.png) [@claudiameadows](https://es.discourse.group/u/claudiameadows)\
**Post date:** [March 14, 2021, 12:32am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/19 "2021-03-14T00:32:58Z")

</div>

> [@MaxGraey](#):
>
> I list there quite a few things that tuples / records cannot solve by their nature

In theory, you can use references as perfect hashes if you assign a unique value to each reference, each string, each number, etc., given arbitrarily large memory available. Your proposal is about performance and computational complexity (which is literally the theoretical study of algorithm performance), not pure algorithmic theory.

---

<div class="post-metadata">

**Author:** ![yjhmelody](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/yjhmelody/32/797_2.png) [@yjhmelody](https://es.discourse.group/u/yjhmelody)\
**Post date:** [April 30, 2021, 9:49am UTC](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673/20 "2021-04-30T09:49:30Z")

</div>

Many times we need to hash based on the key if the key is a complex object. If we don't have a reference to the key in the map, we will never be able to access it unless we traverse it.

Such as when I use web worker to post a map data. The worker thread have not any reference of the keys.

[Next page](https://es.discourse.group/t/custom-hash-and-equal-functions-for-map-and-set-collections/673.md?page=2)