JavaScript HashMap with fast key/values iteration

[Ezelia]

Hello,

 

I'm sharing with you a code I made to handle big lists of objects that need fast iteration.

 

it's a TypeScript code, the compiled version is also provided : https://gist.github.com/alaa-eddine/6317515
 

what this code do ?

 

in JavaScript when you want to manipulate lists of objects, you have the choice between Arrays [] and Objects {}.

 

Objects are sort of hashtables with key => value representation, so access to values is fast knowing the key.

 

Arrays don't provide key => value facility but are mutch faster than object when you have to iterate throught all items.

 

 

sometimes you need both features : direct access AND fast iteration, this is the reason why I wrote this code.

it provide direct access to an array of keys, and array of values and also direct access to elements throught their keys.

I don't know if such implementation allready exists (didn't find any) ...

TODO :
 * add sort method
 * clean keys/values array when the number of undefined elements becomes big (due to removed items).


feedbacks are welcome

[xerver]

Looks cool Ezelia, do you have a jsperf comparing your implementation to a for-in loop? Any metrics on memory usage increases?

 

I would also like to see setup/destroy time comparisons (how performance is the `add`/`remove` for large sets)?

[Ezelia]

here is the jsperf with 10000 items

http://jsperf.com/custom-hashmap-implementation-vs-for-in-vs-for-loop

in case of direct access to HashMap values it's almost as fast as array.

(seems jsperf.com is having some issues, it's not recording my results and not showing charts :/ )

[Chris]

I just added three other iteration methods to the test case, as well as fixing a bug in your test (you were re-defining the "o" variable with each loop).

 

Nothing came close to your "disguised array" method used in your Custom HashMap class

Nicely done! Altough I don't get why you would want to iterate over an objects properties in the first place...

 

Also, It would be nice if you could just say:

var speedyHash = new HashMap(normalObj);

To take a normal object and turn it into a speedy HashMap. Calling add() for each property is very tiresome.

I would fork and implement it by myself, but: you sadly made it in TypeScript

[Ezelia]

@Chris, the compiled JS version is available in the same gist.
as I said this is an experimental class ...

and the reason why I created such a class is that I started implementing an Entity System for a game engine... and for my implementation I need fast way to iterate all my entities (every single thing in the game is an entity so they can be thousands) .
but I also need to get quick access to entity properties. 

this is why I need both object and array features

[Edit] : I'll add the possibility to construct the HashMap from an initial object

[Chris]

I know that there is also a compiled version - but if I add code to the compiled version, it will be overwritten, the next time you compile your typescript source

 

Yeah, I've read about your entity system approach. Need to make a comment about it, there

[xerver]

Nice! Being able to use a native for loop to iterate the values, but still have direct access via named keys is pretty sweet! Definately a memory for speed trade off here, but very cool stuff Ezelia keep it up.