javascript中的有序散列

这个问题是最重要的搜索结果。在找不到有序散列之后,我就编写了这个小的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

不,因为 Object type is specified to be an unordered collection of properties 你不能相信。(或者:只能依赖对象是无序的属性集合。)

如果你想要一个有序的散列集,你需要自己实现它。

2016年的javascript,特别是ecmascript 6,支持 Map built-in class .

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

这就是你需要的。(我想知道为什么这是描述这个数据结构的第一个信息。)

例如,

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 ]

或来自 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);
}

@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();

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

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)

它不太优雅,但能完成任务。

意识到很晚了,但我需要这个,在别处找不到。 *更新 添加了必需的不可枚举方法和属性。 快速实施ES 5(根据需要使用Polyfill):

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

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

一个相当简单的方法是使用数组来存储订单。 您需要编写一个自定义比较函数来建立所需的顺序。 其缺点是每次更改哈希表时,都必须对数组进行排序并跟踪关系。 如果你必须维护一个不断变化的散列表,那就不是很整洁了。

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

使用@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]
}