檢查重複的Javascript對象

Question

TL; DR版本：我想避免將重複的Javascript對象添加到類似對象的數組中，其中一些對象可能非常大。什麼是最好的方法？

我有一個應用程序，我將大量的JSON數據加載到Javascript數據結構中。雖然這是比這更復雜一點，假設我加載JSON成JavaScript對象從服務器陣列通過一系列的AJAX請求，類似的：

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對象創建散列函數的功能比JSON.stringify？
• 對象中超長屬性名稱可能存在的問題是什麼？

Answer 1

我建議你創建一個JSON.stringify（o）的MD5哈希值，並將它存儲在你的哈希映射中，並將存儲對象引用爲哈希數據。爲確保JSON.stringify()中沒有對象鍵順序差異，您必須創建訂購鍵的對象的副本。

然後，當每個新的對象進來時，你檢查哈希映射。如果在哈希映射中找到匹配項，則將傳入對象與您存儲的實際對象進行比較，以確定它們是否真正重複（因爲可能存在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/

Answer 2

1. 可能。例如，如果您知道什麼樣的對象通過，您可以編寫比JS對象的鍵更好的索引和搜索系統。但是你只能用JavaScript和對象密鑰用C編寫...
2. 必須你的哈希是無損的嗎？如果可以嘗試失去壓縮（MD5）。我猜你會失去一些速度並獲得一些記憶。順便說一句，做JSON.stringify(o)保證相同的鍵排序。因爲{foo: 1, bar: 2}和{bar: 2, foo: 1}等於對象，但不是字符串。
3. 成本內存

一個可能的優化：

而不是使用getJSON使用$.get並通過"text"爲dataType PARAM的。比你可以使用結果作爲你的哈希值，然後轉換爲對象。

其實寫最後一句我雖然對另一種解決方案：

• 收集與$.get所有結果到數組
• 用的buildin（C速度）排序它Array.sort
• 現在你可以很容易地發現和刪除重複一個for

再次不同的JSON字符串可以使相同的JavaScript對象。