Ordered hash in JavaScript

Question

JavaScript objects have no order stored for properties (according to the spec). Firefox seems to preserve the order of definition of properties when using a for...in loop. Is this behaviour something that I can rely on? If not is there a piece of JavaScript code somewhere that implements an ordered hash type?

See http://stackoverflow.com/questions/280713/elements-order-for-in-loop-in-javascript — Crescent Fresh, May 09 '10 at 19:51

score 62 · Answer 1 · edited Sep 06 '17 at 14:59

JavaScript in 2016, specifically EcmaScript 6, supports the Map built-in class.

A Map object iterates its elements in insertion order — a for...of loop returns an array of [key, value] for each iteration.

That's what you need. (I wonder why that is the first info in the description of this data structure, though.)

For example,

m = new Map()

m.set(3,'three')
m.set(1,'one')
m.set(2,'two')

m // Map { 3 => 'three', 1 => 'one', 2 => 'two' }

[...m.keys()] // [ 3, 1, 2 ]

or the example from the docs:

var myMap = new Map();
myMap.set(0, 'zero');
myMap.set(1, 'one');

myMap // Map { 0 => 'zero', 1 => 'one' }

for (var [key, value] of myMap) {
  console.log(key + " = " + value);
}

for (var key of myMap.keys()) {
  console.log(key);
}

for (var value of myMap.values()) {
  console.log(value);
}

for (var [key, value] of myMap.entries()) {
  console.log(key + " = " + value);
}

Important footnote - "Note that in the ECMAScript 2015 spec objects do preserve creation order for string and Symbol keys, so traversal of an object with only string keys would yield the keys in order of insertion" — Dev Aggarwal, Oct 29 '19 at 17:08

Florian Ledermann · Answer 2 · 2022-01-17T09:25:02.440

@Vardhan 's answer in plain JavaScript, using closure instead of classical OO and adding an insert() method:

function makeOrderedHash() {
    let keys = [];
    let vals = {};
    return {
        push: function(k,v) {
            if (!vals[k]) keys.push(k);
            vals[k] = v;
        },
        insert: function(pos,k,v) {
            if (!vals[k]) {
                keys.splice(pos,0,k);
                vals[k] = v;
            }
        },
        val: function(k) {return vals[k]},
        length: function(){return keys.length},
        keys: function(){return keys},
        values: function(){return vals}
    };
};

let myHash = makeOrderedHash();

Gumbo · Answer 3 · 2010-05-09T19:45:50.243

22

No, since the Object type is specified to be an unordered collection of properties, you can not rely on that. (Or: You can only rely on that an object is an unordered collection of properties.)

If you want to have an ordered hash set, you will need to implement it on your own.

edited May 09 '10 at 19:45

answered May 09 '10 at 19:39

Gumbo

643,351
109
780
844

8

Downvoting as this is answering only first part of question and doesn't attempt a solution – Florian Ledermann Sep 16 '14 at 15:13
4

Downvoted because it's obvious the poster knew this. Otherwise, he wouldn't have asked the question. – Robert Mah May 29 '19 at 21:01

score 9 · Accepted Answer · answered Jun 07 '13 at 09:41

9

This question come up as the top search result. After not finding a ordered hash, i just wrote this small coffescript. Hopefully this will help folks landing on this page:

## OrderedHash
# f = new OrderedHash
# f.push('a', 1)
# f.keys()
# 
class OrderedHash
 constructor: ->
   @m_keys = []
   @m_vals = {}

  push: (k,v) ->
    if not @m_vals[k]
      @m_keys.push k
    @m_vals[k] = v

  length: () -> return @m_keys.length

  keys: () -> return @m_keys

  val: (k) -> return @m_vals[k]
  vals: () -> return @m_vals

answered Jun 07 '13 at 09:41

vrdhn

4,024
3
31
39

15

OP asked for a solution in JavaScript -> see below for my port – Florian Ledermann Sep 16 '14 at 12:29
@FloLedermann Thanks, also, http://js2.coffee/ can help in these situations generally. – crizCraig Feb 02 '15 at 17:48
`if not @m_vals[k]` seems like it would push the key to the m_keys array again if the value is anything falsy. Should probably do a `if (!(k in this.m_vals))` (writing it that way because I don't know CoffeeScript). – M Miller Aug 20 '15 at 02:13

score 5 · Answer 5 · answered May 02 '13 at 23:25

One trick I do is to store the data in a regular unordered hash, and then store the preferred order in an array. In JS, you can even make the order array part of the hash itself.

var myHash = {
  a: "2",
  b: "3",
  c: "1"
};

myHash.order = [ myHash.c, myHash.a, myHash.b ];

alert("I can access values by key. Here's B: " + myHash.b);
var message =  "I can access also loop over the values in order: ";

for (var i=0;i<myHash.order.length;i++)
{ 
  message = message + myHash.order[i] + ", ";
}

alert(message)

It's not exactly elegant, but it gets the job done.

This solution looks quite fragile to me, as the mechanism used for ordering is not encapsulated and the client code has to know about the internals to make it work... may be OK for throwaway projects, but certainly not production ready IMO. — Florian Ledermann, Oct 02 '14 at 09:20

Jared Smith · Answer 6 · 2014-07-03T18:23:41.390

Realize its late but I needed this and couldn't find it elsewhere. *UPDATE Added necessary non-enumerable methods and properties. Quick ES 5 implementation (polyfill as needed):

function orderedHash(object) {
    'use strict'
    var obj = object || {}
    Object.defineProperties(this, {
        'length': {
            value: 0,
            writable: true
        },
        'keys' : {
            value: [],
            writable: true
        },
        'sortedBy': {
            value: '',
            writable: true
        }
    })
    this.hash(obj)
    obj = null
}
Object.defineProperties(orderedHash.prototype, {
    'sortByKeys': {
        value: function sortByKeys() {
            var i, len, name
            this.keys.sort(function(a, b) {   
                return a >= b ? 1 : -1
            })
            for (i=0, len = this.keys.length; i < len; ++i) {
                name = this.keys[i]
                this[i] = this[name]
            }
            this.sortedBy = 'keys'
            return null
        }   
    },
    'sortByValues': {
        value: function sortByValues() {
            var i, len, newIndex, name, ordered = [], names = this.keys.splice(0)
            this.keys = []
            for (i=0, len = this.length; i < len; ++i) {
                ordered.push(this[i])
                ordered.sort(function(a, b) {   
                    return a >= b ? 1 : -1
                })
                newIndex = ordered.lastIndexOf(this[i])
                name = names[i]
                this.keys.splice(newIndex, 0 , name)
            }
            for (i=0, len = ordered.length; i < len; ++i) {
                this[i] = ordered[i]
            }
            this.sortedBy = 'values'
            return null
        }
    },
    'insert': {
        value: function insert(name, val) {
            this[this.length] = val
            this.length += 1
            this.keys.push(name)
            Object.defineProperty(this, name, {
                value: val,
                writable: true,
                configurable: true
            })
            if (this.sortedBy == 'keys') {
                this.sortByKeys()
            } else {
                this.sortByValues()
            }
            return null
        }
    },
    'remove': {
        value: function remove(name) {
            var keys, index, i, len
            delete this[name]
            index = this.keys[name]
            this.keys.splice(index, 1)
            keys = Object.keys(this)
            keys.sort(function(a, b) {   
                return a >= b ? 1 : -1
            })
            for (i=0, len = this.length; i < len; ++i) {
                if (i >= index) {
                    this[i] = this[i + 1]
                }
            }
            delete this[this.length - 1]
            this.length -= 1
            return null
        }
    },
    'toString': {
        value: function toString() {
            var i, len, string = ""
            for (i=0, len = this.length; i < len; ++i) {
                string += this.keys[i]
                string += ':'
                string += this[i].toString()
                if (!(i == len - 1)) {
                    string += ', '
                }
            }
            return string
        }
    },
    'toArray': {
        value: function toArray() {
            var i, len, arr = []
            for (i=0, len = this.length; i < len; ++i) {
                arr.push(this[i])
            }
            return arr
        }
    },
    'getKeys': {
        value: function getKeys() {
            return this.keys.splice(0)
        }
    },
    'hash': {
        value: function hash(obj) {
            var i, len, keys, name, val
            keys = Object.keys(obj)
            for (i=0, len = keys.length; i < len; ++i) {
                name = keys[i]
                val = obj[name]
                this[this.length] = val
                this.length += 1
                this.keys.push(name)
                Object.defineProperty(this, name, {
                    value: val,
                    writable: true,
                    configurable: true
                })
            }
             if (this.sortedBy == 'keys') {
                this.sortByKeys()
            } else {
                this.sortByValues()
            }
            return null
        }
    }
})

What happens here is that by using Object.defineProperty() instead of assignment can we make the properties non-enumerable, so when we iterate over the hash using for...in or Object.keys() we only get the ordered values but if we check hash.propertyname it will be there. There are methods provided for insertion, removal, assimilating other objects (hash()), sorting by key, sorting by value, converting to array or string, getting the original index names, etc. I added them to the prototype but they are also non-enumerable, for...in loops still work. I didn't take time to test it on non-primitives, but it works fine for strings, numbers, etc.

Simon Rigét · Answer 7 · 2019-09-26T22:22:33.097

A fairly simple way is to use an array to store the order. You need to write a custom compare function to establish the order you require. The down side is that you have to sort the array and keep track of relations, each time you change the hash table.

var order=[];
var hash={"h1":4,"h2":2,"h3":3,"h4":1};

function cmp(a,b) {
  if (hash[a] < hash[b]) return -1;
  if (hash[a] > hash[b]) return 1;
  return 0;
}

// Add initial hash object to order array
for(i in hash) order.push(i);
order.sort(cmp);
// h4:1 h2:2 h3:3 h1:4

// Add entry
hash['h5']=2.5;
order.push('h5');
order.sort(cmp);
// h4:1 h2:2 h5:2.5 h3:3 h1:4

// Delete entry
order.splice(order.indexOf('h5'), 1);
delete hash['h5'];
// h4:1 h2:2 h3:3 h1:4

// Display ordered hash array (with keys)
for(i in order) console.log(order[i],hash[order[i]]);

score 1 · Answer 8 · answered Oct 11 '16 at 08:51

Taking @Craig_Walker solution, if you are only interested to know in which order the properties have been inserted, an easy solution would be :

var obj ={ }
var order = [];

function add(key, value) {
    obj[key] = value;
    order.push(key);
}

function getOldestKey() {
    var key = order.shift();
    return obj[key]
}

function getNewsetKey() {
    var key = order.pop();
    return obj[key]
}

score 1 · Answer 9 · answered May 24 '19 at 15:48

1

You can now use a native Map since it preserves the insertion order when looped over with for in

answered May 24 '19 at 15:48

1mike12

2,946
3
27
36

score 0 · Answer 10 · answered May 06 '21 at 09:37

class @OrderedHash

  constructor: (h_as_array=[])->
    @keys = []
    @vals = {}
    if h_as_array.length > 0
      i = 0
      while i < h_as_array.length
        @push(h_as_array[i], h_as_array[i+1])
        i += 2
    @

  push: (k,v)->
    @keys.push k if not @vals[k]
    @vals[k] = v

  length: ()-> return @keys.length
  keys:   ()-> return @keys
  val:   (k)-> return @vals[k]
  vals:   ()-> return @vals
  each: (callback)->
    return unless callback
    for k in @keys
      callback(@vals[k])

Ordered hash in JavaScript

10 Answers10

Linked