CODEWITHSUNDEEP
javascriptdata-structures
nickf
nickf

Reputation: 546085

Objects vs arrays in Javascript for key/value pairs

Say you have a very simple data structure:

(personId, name)

...and you want to store a number of these in a javascript variable. As I see it you have three options:

// a single object
var people = {
    1 : 'Joe',
    3 : 'Sam',
    8 : 'Eve'
};

// or, an array of objects
var people = [
    { id: 1, name: 'Joe'},
    { id: 3, name: 'Sam'},
    { id: 8, name: 'Eve'}
];

// or, a combination of the two
var people = {
    1 : { id: 1, name: 'Joe'},
    3 : { id: 3, name: 'Sam'},
    8 : { id: 8, name: 'Eve'}
};

The second or third option is obviously the way to go if you have (or expect that you might have) more than one "value" part to store (eg, adding in their age or something), so, for the sake of argument, let's assume that there's never ever going to be any more data values needed in this structure. Which one do you choose and why?

Edit: The example now shows the most common situation: non-sequential ids.

Upvotes: 84

Views: 73281

Answers (6)

scaraveos
scaraveos

Reputation: 1006

I created a little library to manage key value pairs.

https://github.com/scaraveos/keyval.js#readme

It uses

  • an object to store the keys, which allows for fast delete and value retrieval operations and
  • a linked list to allow for really fast value iteration

Hope it helps :)

Upvotes: 2

derobert
derobert

Reputation: 51157

Actually, there is a fourth option:

var people = ['Joe', 'Sam', 'Eve'];

since your values happen to be consecutive. (Of course, you'll have to add/subtract one --- or just put undefined as the first element).

Personally, I'd go with your (1) or (3), because those will be the quickest to look up someone by ID (O logn at worst). If you have to find id 3 in (2), you either can look it up by index (in which case my (4) is ok) or you have to search — O(n).

Clarification: I say O(logn) is the worst it could be because, AFAIK, and implementation could decide to use a balanced tree instead of a hash table. A hash table would be O(1), assuming minimal collisions.

Edit from nickf: I've since changed the example in the OP, so this answer may not make as much sense any more. Apologies.

Post-edit

Ok, post-edit, I'd pick option (3). It is extensible (easy to add new attributes), features fast lookups, and can be iterated as well. It also allows you to go from entry back to ID, should you need to.

Option (1) would be useful if (a) you need to save memory; (b) you never need to go from object back to id; (c) you will never extend the data stored (e.g., you can't add the person's last name)

Option (2) is good if you (a) need to preserve ordering; (b) need to iterate all elements; (c) do not need to look up elements by id, unless it is sorted by id (you can do a binary search in O(logn). Note, of course, if you need to keep it sorted then you'll pay a cost on insert.

Upvotes: 7

levik
levik

Reputation: 117529

The third option is the best for any forward-looking application. You will probably wish to add more fields to your person record, so the first option is unsuitable. Also, it is very likely that you will have a large number of persons to store, and will want to look up records quickly - thus dumping them into a simple array (as is done in option #2) is not a good idea either.

The third pattern gives you the option to use any string as an ID, have complex Person structures and get and set person records in a constant time. It's definitely the way to go.

One thing that option #3 lacks is a stable deterministic ordering (which is the upside of option #2). If you need this, I would recommend keeping an ordered array of person IDs as a separate structure for when you need to list persons in order. The advantage would be that you can keep multiple such arrays, for different orderings of the same data set.

Upvotes: 1

Nathaniel Reinhart
Nathaniel Reinhart

Reputation: 1183

Given your constraint that you will only ever have name as the value, I would pick the first option. It's the cleanest, has the least overhead and the fastest look up.

Upvotes: 0

karim79
karim79

Reputation: 342645

Assuming the data will never change, the first (single object) option is the best.

The simplicity of the structure means it's the quickest to parse, and in the case of small, seldom (or never) changing data sets such as this one, I can only imagine that it will be frequently executed - in which case minimal overhead is the way to go.

Upvotes: 3

Dan Lew
Dan Lew

Reputation: 87430

Each solution has its use cases.

I think the first solution is good if you're trying to define a one-to-one relationship (such as a simple mapping), especially if you need to use the key as a lookup key.

The second solution feels the most robust to me in general, and I'd probably use it if I didn't need a fast lookup key:

  • It's self-describing, so you don't have to depend on anyone using people to know that the key is the id of the user.
  • Each object comes self-contained, which is better for passing the data elsewhere - instead of two parameters (id and name) you just pass around people.
  • This is a rare problem, but sometimes the key values may not be valid to use as keys. For example, I once wanted to map string conversions (e.g., ":" to ">"), but since ":" isn't a valid variable name I had to use the second method.
  • It's easily extensible, in case somewhere along the line you need to add more data to some (or all) users. (Sorry, I know about your "for argument's sake" but this is an important aspect.)

The third would be good if you need fast lookup time + some of the advantages listed above (passing the data around, self-describing). However, if you don't need the fast lookup time, it's a lot more cumbersome. Also, either way, you run the risk of error if the id in the object somehow varies from the id in people.

Upvotes: 58

Related Questions