javascript - 检查重复的 Javascript 对象

Question

TL;DR 版本:我想避免将重复的 Javascript 对象添加到类似对象的数组中，其中一些对象可能非常大。什么是最好的方法？

我有一个应用程序，我在其中将大量 JSON 数据加载到 Javascript 数据结构中。虽然它比这复杂一点，但假设我通过一系列 AJAX 请求从服务器将 JSON 加载到 Javascript 对象数组中，例如:

var myObjects = [];

function processObject(o) {
    myObjects.push(o);
}

for (var x=0; x<1000; x++) {
    $.getJSON('/new_object.json', processObject);
}

使事情复杂化的是 JSON:

• 处于未知模式中
• 任意长度(可能不是很大，但可能在 100-200 kb 范围内)
• 可能包含跨不同请求的重复项

我最初的想法是有一个额外的对象来存储每个对象的哈希值(通过 JSON.stringify？)并在每次加载时检查它，如下所示:

var myHashMap = {};

function processObject(o) {
    var hash = JSON.stringify(o);
    // is it in the hashmap?
    if (!(myHashMap[hash])) {
        myObjects.push(o);
        // set the hashmap key for future checks
        myHashMap[hash] = true;
    }
    // else ignore this object
}

但我担心 myHashMap 中的属性名称可能有 200 kb 的长度。所以我的问题是:

• 有没有比 hashmap 想法更好的方法来解决这个问题？
• 如果不是，是否有比 JSON.stringify 更好的方法来为任意长度和模式的 JSON 对象创建哈希函数？
• 对象中的超长属性名称可能会出现哪些问题？

Answer 1

我建议您创建 JSON.stringify(o) 的 MD5 散列并将其存储在您的散列图中，并引用您存储的对象作为散列数据。并确保 JSON.stringify() 中没有对象键顺序差异，您必须创建对键进行排序的对象的副本。

然后，当每个新对象进来时，您根据 HashMap 检查它。如果您在散列映射中找到匹配项，则将传入对象与您存储的实际对象进行比较，以查看它们是否真正重复(因为可能存在 MD5 散列冲突)。这样，您就有了一个易于管理的哈希表(其中只有 MD5 哈希)。

下面的代码用于创建对象(包括嵌套对象或数组中的对象)的规范字符串表示，如果您只是调用 JSON.stringify()，它会处理可能具有不同顺序的对象键。

// Code to do a canonical JSON.stringify() that puts object properties 
// in a consistent order
// Does not allow circular references (child containing reference to parent)
JSON.stringifyCanonical = function(obj) {
    // compatible with either browser or node.js
    var Set = typeof window === "object" ? window.Set : global.Set;

    // poor man's Set polyfill
    if (typeof Set !== "function") {
        Set = function(s) {
            if (s) {
                this.data = s.data.slice();
            } else {
                this.data = [];
            }
        };
        Set.prototype = {
            add: function(item) {
                this.data.push(item);
            },
            has: function(item) {
                return this.data.indexOf(item) !== -1;
            }
        };
    }

    function orderKeys(obj, parents) {
        if (typeof obj !== "object") {
            throw new Error("orderKeys() expects object type");
        }
        var set = new Set(parents);
        if (set.has(obj)) {
            throw new Error("circular object in stringifyCanonical()");
        }
        set.add(obj);
        var tempObj, item, i;
        if (Array.isArray(obj)) {
            // no need to re-order an array
            // but need to check it for embedded objects that need to be ordered
            tempObj = [];
            for (i = 0; i < obj.length; i++) {
                item = obj[i];
                if (typeof item === "object") {
                    tempObj[i] = orderKeys(item, set);
                } else {
                    tempObj[i] = item;
                }
            }
        } else {
            tempObj = {};
            // get keys, sort them and build new object
            Object.keys(obj).sort().forEach(function(item) {
                if (typeof obj[item] === "object") {
                    tempObj[item] = orderKeys(obj[item], set);
                } else {
                    tempObj[item] = obj[item];
                }
            });
        }
        return tempObj;
    }

    return JSON.stringify(orderKeys(obj));
}

算法

var myHashMap = {};

function processObject(o) {
    var stringifiedCandidate = JSON.stringifyCanonical(o);
    var hash = CreateMD5(stringifiedCandidate);
    var list = [], found = false;
    // is it in the hashmap?
    if (!myHashMap[hash] {
        // not in the hash table, so it's a unique object
        myObjects.push(o);
        list.push(myObjects.length - 1);    // put a reference to the object with this hash value in the list
        myHashMap[hash] = list;             // store the list in the hash table for future comparisons
    } else {
        // the hash does exist in the hash table, check for an exact object match to see if it's really a duplicate
        list = myHashMap[hash];             // get the list of other object indexes with this hash value
        // loop through the list
        for (var i = 0; i < list.length; i++) {
            if (stringifiedCandidate === JSON.stringifyCanonical(myObjects[list[i]])) {
                found = true;       // found an exact object match
                break;
            }
        }
        // if not found, it's not an exact duplicate, even though there was a hash match
        if (!found) {
            myObjects.push(o);
            myHashMap[hash].push(myObjects.length - 1);
        }
    }
}

jsonStringifyCanonical() 的测试用例在这里:https://jsfiddle.net/jfriend00/zfrtpqcL/