Typescript, HashMap using hashcode and equal function

Question

I'm writing a typescript browser game.

I need to store an int vector3 (map position) as the map key.

Since we can't store reference type into the key of typescript Object and Map. (I mean we could for Map but cannot lookup without holding the same reference)

And there are solutions are suggested on the internet such as nested maps or stringify keys.

I want to find a more elegant solution using hashcode and equals.

Is there any suggest solution or npm library?

Why is hashcode/equals more “elegant” than stringifying keys? The former means you have to implement a multimap that stores all the keys with the same hashcode. If you can compute a unique key then you can just use a regular map. For a vector of three integers you can just do a join to get such a key. — jcalz
– jcalz, Commented Nov 20, 2021 at 14:47
I don't want to stringify since this will need to manipulate many strings in each frame. The possible way I'm looking for is to compute the hash as you said. But the thing is since int vector3 use 3 integers there are certain possibility to have collisions to hash it into 1 an integer. Except I'm going to limit the range of each int in vector3. — kitta
– kitta, Commented Nov 20, 2021 at 14:52
@jcalz BTW, Thank for the suggestion.. The compute unique hash is also in my consideration. — kitta
– kitta, Commented Nov 20, 2021 at 14:57
Do you have some evidence that concatenating numbers into a string will be slower than resolving hash collisions with a multimap? It seems like premature optimization to assume that the easy solution will have unacceptable performance. — jcalz
– jcalz, Commented Nov 20, 2021 at 15:01
I'm also interested in the question, not that much because of performance concerns, but type checkings: I feel like stringifying keys breaks the interest of using typescript. Didn't find much neither on the Internet: npm hashmap is not far from it, appart the remaining to-do: "Allow extending the hashing function in a AOP way or by passing a service" :( — aroyer
– aroyer, Commented Dec 3, 2021 at 0:49

aroyer · Accepted Answer · 2021-12-09 17:55:53Z

In as much as I could not answer the question easily for myself from what I had found on the Internet, I share a quick implementation, borrowed from Python experience (not fully tested).

The idea is to have the Hashable.hash() function return a number or a string that will let the HashableMap know when key objects are actually the same.

export interface Hashable {
    hash(): InnerHashKey;
}

export class HashableMap<K extends Hashable, V> extends Map<K, V> {
    private readonly _innerMap: InnerMap<K, V> = new InnerMap<K, V>();

    // Map<K, V> interface overload.
    public get(key: K): V | undefined {
        return this._innerMap.get(key.hash())?.value;
    }
    public has(key: K): boolean {
        return this._innerMap.has(key.hash());
    }
    public set(key: K, value: V): this {
        this._innerMap.set(key.hash(), {key: key, value: value});
        return this;
    }
    public delete(key: K): boolean {
        return this._innerMap.delete(key.hash());
    }
    public get size(): number {
        return this._innerMap.size;
    }
    public forEach(callbackfn: (value: V, key: K, map: Map<K, V>) => void, thisArg?: any): void {
        this._innerMap.forEach((value: InnerValue<K, V>): void => callbackfn(value.value, value.key, thisArg));
    }
    public entries(): IterableIterator<[K, V]> {
        return Array.from(this._innerMap.values()).map((value: InnerValue<K, V>): [K, V] => [value.key, value.value]).values();
    }
    public keys(): IterableIterator<K> {
        return Array.from(this._innerMap.values()).map((value: InnerValue<K, V>): K => value.key).values();
    }
    public values(): IterableIterator<V> {
        return Array.from(this._innerMap.values()).map((value: InnerValue<K, V>): V => value.value).values();
    }
    public clear(): void {
        this._innerMap.clear();
    }
}

type InnerHashKey = any;
type InnerValue<K, V> = {key: K, value: V};
class InnerMap<K, V> extends Map<InnerHashKey, InnerValue<K, V>> {}

Collectives™ on Stack Overflow

Typescript, HashMap using hashcode and equal function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related