finding all keys that map to a value in javascript. And efficient alternatives

Question

I'm working on an application in javascript where each user is in a room. No two users share the same name and no two rooms share the same name. Currently I have it set up like this:

var userroommap = {
  username: "room",
  username2: "room",
  username3: "room2"
}

getting the room a user is in is as simple as

userroommap["user"]

but in order to get all users which are present in a room I would have to iterate over the entire userroommap like so:

for (var x in userroommap) {
  if (userroommap[x] == "room")
    //user x is present in room 
  }
}

In my application I must know which users are in which rooms very often so I am considering using another object to hold all users in a room, something like:

var roomusermap = {
  room:["username", "username2"],
  room2:["username3"]
}

Adding users to the room is trivial because all you have to do is append to an array, however removing a username from a room requires iterating over the array and becomes a decent operation. This already is a decent solution to my problem, but I became curious if there was a better solution. So: is there a better way to (i) store the roomusermap, perhaps without arrays? or, alternatively (ii) find all users in a room?

What's the problem with using the object? Are you seeing real performance issues? — T.J. Crowder
– T.J. Crowder, Commented Oct 22, 2015 at 4:54
i guess I am just curious if there is some way to do value: key that I didn't list. However your comment made me realize it is kind of a useless question :/ — Elliot E
– Elliot E, Commented Oct 22, 2015 at 5:09

Peter Dixon-Moses · Accepted Answer · 2015-10-23 14:08:11Z

1

The data-structure described in the previous answer is called a BiMap.

A BiMap ideally provides equivalent performance for value: keys lookup operations as for key: values lookups. It is typically implemented by internally managing two separate maps (one with a forward-mapping {key:values} and one with a reverse-mapping {value:keys}).

Here's an existing implementation to use if you're not rolling your own. https://www.npmjs.com/package/bimap

edited Oct 23, 2015 at 14:08

answered Oct 23, 2015 at 14:00

Peter Dixon-Moses

3,22916 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

T.J. Crowder · Accepted Answer · 2015-10-22 05:12:44Z

Unless you've identified a genuine, real-world performance problem, I'd stick with the simple solution.

That said, a few thoughts for you:

All modern JavaScript engines give you the Object.keys function, which returns an array of an object's own enumerable properties. This may be more efficient than your for-in loop for two reasons:
1. It's happening within the engine's code, which lets the engine optimize
2. for-in looks for enumerable properties in prototype objects, whereas Object.keys knows it's only supposed to look in that specific object

Your roomusermap can contain maps per room, it doesn't need to use arrays.

var roomusermap = {
    room: {
        username: user,
        username2: user2
    },
    room2: {
        username3: user3
    }
};

Adding a user to a room becomes:

userroommap[username] = roomname;
roomusermap[roomname][username] = user;

Removing a user is:

delete userroommap[username];
delete roomusermap[roomname][username];

If you're seeing performance problems with those map objects, something to keep in mind is that removing a property from an object (delete) puts the object into "dictionary mode" on several JavaScript engines (having previously been in a more optimized state), significantly impacting the time required to look up properties on that object.

So in the very hypothetical case where the property lookup performance starts to be an issue, you could consider storing undefined rather than deleting the property. E.g., instead of:
```
delete userroommap[username];
delete roomusermap[roomname][username];
```
you'd do
```
userroommap[username] = undefined;
roomusermap[roomname][username] = undefined;
```
However, you'd have to adjust your checks for whether a user is in a room, and you couldn't use Object.keys (on its own) to get the list anymore since you have to weed out the properties with the value undefined. You could use Object.keys with filter:
```
var map = roomusermap[roomname];
var users = Object.keys(map).filter(function(username) {
    return map[username] !== undefined;
});
```
So you'd really want to do that only if you've identifed a genuine problem caused by objects going into dictionary mode.

Maybe not such a useless question, this is helpful, thank you.

Collectives™ on Stack Overflow

finding all keys that map to a value in javascript. And efficient alternatives

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related