JavaScript中的不可变哈希表和数组实现？

Question

有没有简单的不可变哈希表和数组实现在JavaScript中？我不需要最快的速度，比克隆更好的合理速度就可以了。如果有简单的Java或其他语言的实现，可以轻松地理解并移植到JavaScript，那也很好。

更新：目标不仅仅是冻结哈希表（或数组），而是要实现一个高效的更新操作——更新不可变哈希表应该返回一个新的不可变哈希表。它应该比“克隆原始数据并更新”更有效率。

本机JS类型的更新复杂度大约为O(1)，通过克隆的复杂度将为O(n)，使用特殊的不可变数据结构（我所要求的）将为0(log(n))。

更新2：JavaScript已经有Array / Hash：

是的，但它们是可变的，我需要类似但不可变的东西，基本上可以通过克隆hash2 = hash1.clone(); hash2[key] = value来完成，但这样做非常低效，有算法可以使其非常高效，而不使用clone。

hash1 = {}
hash2 = hash1.set('key', 'value2')
hash3 = hash1.set('key', 'value3)

console.log(hash1) // => {}
console.log(hash2) // => {key: 'value2'}
console.log(hash3) // => {key: 'value3'}

解决方案：

这不是一个不可变哈希的实现，而更像是我当前问题的一种hack方法，也许它也能帮助其他人。

再说一些为什么我需要不可变数据结构的原因 - 我使用Node.js和类似于内存数据库的东西。一个请求可以读取数据库，另一个请求可以更新它 - 更新可能需要很长时间（调用远程服务） - 所以我不能阻塞所有读进程并等待更新完成，而且更新可能会失败，数据库应该回滚。所以我需要以某种方式隔离（ACID）内存数据库的读写操作。

这就是为什么我需要不可变数组和哈希表 - 以实现类似MVCC的东西。但似乎有一种更简单的方法来做到这一点。更新操作不是直接更新数据库 - 而是将更改记录到数据库中（但不直接执行），例如“将42添加到数组db.someArray中”的形式。

最终 - 更新操作的产物将是一系列这样的更改命令的数组，因为它可以很快地应用 - 我们可以阻止数据库应用它。

但是，如果在JavaScript中有不可变数据结构的实现，那还是很有趣的，所以我会让这个问题保持开放状态。

- Alex Craft

---

什么是“哈希和数组”？JavaScript有数组；你是否在考虑像java.util.Vector这样的索引集合？ - eh9

没有这样的东西在JS中，也没有直接的实现方式，据我所知...你可以做的所有实现都会比标准本地可变对象慢。 - redShadow

“高效实现”但是“速度不是最快的？”是的，它应该比本地可变类型慢两到五倍，但不像使用“克隆”操作那样低效。 - Alex Craft

@AlexeyPetrushin 你知道 Object.preventExtensions()、Object.seal() 和 Object.freeze() 吗？ - Šime Vidas

@ŠimeVidas 很有趣，但与许多当前到稍旧的浏览器不兼容.. 例如ie* - Sajjan Sarkar

Answer 1

我知道这个问题已经很老了，但是我认为像我一样在搜索的人应该被指向Facebook的Immutable.js，它以非常高效的方式提供了许多不同类型的不可变数据结构。

- JustGage

Answer 2

我有同样的要求，需要JS的持久化数据结构，所以我一段时间前制作了一个持久化映射的实现。

https://github.com/josef-jelinek/cofy/blob/master/lang/feat.js

它包含了基于平衡树（排序）的映射实现，以及一个简单的写时复制映射实现（还有未完成的持久化向量/数组）。

var map = FEAT.map();
var map1 = map.assoc('key', 'value');
var value = map1.get('key');
var map2 = map1.dissoc('key');
...

它支持其他方法，如count()、contains(key)、keys(into = [])、values(into = [])、toObject(into = {})、toString()

实现并不太复杂，且为公共领域。我也接受建议和贡献者:).

更新: 您可以在https://github.com/josef-jelinek/cofy/blob/master/tests/test-feat.html找到单元测试(用例示例)。

更新2: 持久向量实现也已经存在，其操作包括：count()、get(i)、set(i, value)、push(value)、pop()、toArray(into = [])、toString()

- jJ'

Answer 3

唯一使一个对象不可变的方法是将其隐藏在一个函数内部。然后，您可以使用该函数返回默认哈希值或更新版本，但您实际上不能在全局范围内存储不可变哈希值。

function my_hash(delta) {
    var default = {mykey: myvalue};
    if (delta) {
        for (var key, value in delta) {
            if (default.hasOwnProperty(key)) default[key] = value;
        }
    }
    return default;
}

虽然我不认为这是一个好主意。

- Evan Davis

---

让我向您介绍 Object.freeze():P - Šime Vidas

@ŠimeVidas 哇，棒极了！我不知道那个。 - Evan Davis

谢谢，但目标不是冻结一个对象，而是以高效的方式进行略微修改的副本。 - Alex Craft

让我向你介绍一下Object.freeze()的性能表现http://jsperf.com/object-freeze-performance。起初我简直不敢相信。 - jJ'

Answer 4

我所知道的在Javascript中克隆一个对象的最佳方法，是包含在underscore.js中的方法。

简而言之：

_.clone = function(obj) {
  if (!_.isObject(obj)) return obj;
  return _.isArray(obj) ? obj.slice() : _.extend({}, obj);
};

_.extend = function(obj) {
  each(slice.call(arguments, 1), function(source) {
    for (var prop in source) {
      obj[prop] = source[prop];
    }
  });
  return obj;
};

- redShadow