JavaScript 中的有序哈希

Ordered hash in JavaScript

提问by hekevintran

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...inloop. 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?

JavaScript 对象没有为属性存储顺序（根据规范）。Firefox 在使用for...in循环时似乎保留了属性定义的顺序。我可以依赖这种行为吗？如果没有，是否有一段 JavaScript 代码实现了有序散列类型？

采纳答案by vrdhn

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:

这个问题出现在最热门的搜索结果中。在没有找到有序散列后，我只写了这个小coffescript。希望这将帮助人们登陆此页面：

## 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

回答by Ondra ?i?ka

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

2016 年的 JavaScript，特别是 EcmaScript 6，支持Map内置类.

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

Map 对象按插入顺序迭代其元素——for...of 循环为每次迭代返回一个 [key, value] 数组。

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);
}

回答by Gumbo

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.)

不，因为Object 类型被指定为一个无序的属性集合，你不能依赖它。（或者：你只能依赖一个对象是一个无序的属性集合。）

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

如果你想要一个有序的哈希集，你需要自己实现它。

回答by Florian Ledermann

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

@Vardhan 在纯 JavaScript 中的回答，使用闭包而不是经典的 OO 并添加一个 insert() 方法：

function makeOrderedHash() {
    var keys = [];
    var 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}
    };
};

var myHash = makeOrderedHash();

回答by Craig Walker

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.

我做的一个技巧是将数据存储在常规的无序散列中，然后将首选顺序存储在数组中。在 JS 中，您甚至可以将订单数组作为哈希本身的一部分。

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.

它并不完全优雅，但它完成了工作。

回答by Jared Smith

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):

意识到它晚了，但我需要这个并且在其他地方找不到它。*UPDATE 添加了必要的不可枚举的方法和属性。快速 ES 5 实现（根据需要填充）：

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...inor Object.keys()we only get the ordered values but if we check hash.propertynameit 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...inloops still work. I didn't take time to test it on non-primitives, but it works fine for strings, numbers, etc.

这里发生的事情是，通过使用Object.defineProperty()而不是赋值，我们可以使属性不可枚举，因此当我们使用哈希遍历哈希时，for...in或者Object.keys()我们只获得有序值但如果我们检查hash.propertyname它就会在那里。提供了插入、移除、同化其他对象 ( hash())、按键排序、按值排序、转换为数组或字符串、获取原始索引名称等方法。我将它们添加到原型中，但它们也是不可枚举的，for...in循环仍然有效。我没有花时间在非基元上测试它，但它适用于字符串、数字等。

回答by Simon Rigét

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]]);

回答by Ant

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

以@Craig_Walker 解决方案为例，如果您只想知道属性插入的顺序，一个简单的解决方案是：

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]
}

回答by 1mike12

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

您现在可以使用本机 Map，因为它在循环时保留插入顺序 for in