javascript - Deep Search JSON-Object - Stack Overflow

admin管理员组

文章数量:1316842

I'm currently having a problem with a deep search in a json object and even though i thought this issue must have been covered alot, I wasn't able to find anything that was really helpful so far (and I actually found alot, also this thread. Maybe I've been looking at code for too long today but it didn't really help me)

Basically what i want is pretty simple. I have a JSON-Object thats pretty deep filled with objects. All i want is a function that returns an array with all objects that contain a given Key-Value-Pair. I made this function to return the first found object which works just fine

 deepSearch: function(Obj, Key, Value){
                    var returned = [];
                    var result = false;
                    var searchObj = function(_Obj, _Key, _Value){
                        if(_Obj[_Key]===_Value){
                            return _Obj;    
                        } else {
                            return false;
                        }
                    }
                    result = searchObj(Obj, Key, Value);

                    $.each(Obj, function(key, value){
                        if(typeof(Obj[key]) === 'object' && Obj[key]!== null && !result)
                            result = customGeneralFunctions.objects.deepSearch(Obj[key], Key, Value);
                            if(result) return result;
                    });
                    return result;
                }

Now I want to change it to return an array contianing all Objects with that pair. I've been trying for a while now and I think it wouldnt be a change too hard but I just can't wrap my head around it. Maybesomeone has an idea that helps me. Thanks in advance and

Greetings Chris

I'm currently having a problem with a deep search in a json object and even though i thought this issue must have been covered alot, I wasn't able to find anything that was really helpful so far (and I actually found alot, also this thread. Maybe I've been looking at code for too long today but it didn't really help me)

Basically what i want is pretty simple. I have a JSON-Object thats pretty deep filled with objects. All i want is a function that returns an array with all objects that contain a given Key-Value-Pair. I made this function to return the first found object which works just fine

 deepSearch: function(Obj, Key, Value){
                    var returned = [];
                    var result = false;
                    var searchObj = function(_Obj, _Key, _Value){
                        if(_Obj[_Key]===_Value){
                            return _Obj;    
                        } else {
                            return false;
                        }
                    }
                    result = searchObj(Obj, Key, Value);

                    $.each(Obj, function(key, value){
                        if(typeof(Obj[key]) === 'object' && Obj[key]!== null && !result)
                            result = customGeneralFunctions.objects.deepSearch(Obj[key], Key, Value);
                            if(result) return result;
                    });
                    return result;
                }

Now I want to change it to return an array contianing all Objects with that pair. I've been trying for a while now and I think it wouldnt be a change too hard but I just can't wrap my head around it. Maybesomeone has an idea that helps me. Thanks in advance and

Greetings Chris

• javascript
• object
• search
• recursion

Share Improve this question Follow edited May 23, 2017 at 12:09 CommunityBot 111 silver badge asked Feb 15, 2017 at 14:45 relief.melonerelief.melone 3,32233 gold badges3636 silver badges6363 bronze badges 4

• please add the object and the wanted result from a call of the function. – Nina Scholz Commented Feb 15, 2017 at 14:48
• Can you share the sample json file as well? – Tariq B. Commented Feb 15, 2017 at 14:49
• Can you please put a sample input and a desired sample output? – Guillermo Moratorio Commented Feb 15, 2017 at 14:50
• Your code seems to run fine. jsfiddle/kaminasw/fnzs7th1 – Tariq B. Commented Feb 15, 2017 at 14:54

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 5

A safe deep object search?

Can't let this pass 3 answers with examples, all flawed. And all illustrate some classic Javascript coding got-ya's

null is an Object

_{UPDATE an answer has been changed.}

As the code is no longer visible I will just leave the warning when iterating an object's properties and you use typeof to check if you have an object be careful to check for null as it is also of type "object"

getObject returns to early and fails to find additional objects nested inside objects that meet the condition. Though easily fixed by removing the return it will still throw a TypeError: Cannot read property 'find' of null if the object being searched contains an array with null in it.

for in the indiscriminate iterator

_{UPDATE an answer has been removed.}

I have added the removed code as an example in the snippet below function deepSearch is fatally flawed and will more likely throw a RangeError: Maximum call stack size exceeded error then find the object you are looking for. eg deepSearch({ a:"a"},"id",3);. When using for in you should type check as it will iterate a string as well as an object's properties.

function deepSearch(object, key, value) {
  var filtered = [];
  for (var p in object)
    if (p === key && object[p] === value) filtered.push(object);
    else if (object[p]) filtered = filtered.concat(deepSearch(object[p], key, value));      
  return filtered;
}

Dont trust the callback.

Alex K search passed most tests (within reasonable scope of the question) but only if the code in the form of the ment // tip: here is a good idea to check for hasOwnProperty would have been included.

But that said the function has a flaw (and inefficiency) as it will call predicate on all properties of an object, and I can think of plenty of scenarios in which the function can return many references to the same object eg the reciprocal search for objects with property key NOT with value predicate = (key,val)=>{return key === "id" && val !== 3}.

The search should only add one entry per object thus we should test the object not the properties. We can never trust the callback to do what we expect.

And as it is the accepted answer I should point out that Array.concat should really not be used as it is in this situation. Using closure is much more efficient and allows you to not have to pass the current state to each recursion.

---

Circular reference.

The flaw to floor them all.

I am not to sure if it is relevant as the question does state that the data is from the form JSON and hence would be free of any circular reference (JSON can not reference).

But I will address the problem and several solutions.

A circular reference is simply an object referencing itself. For example.

var me = {};
me.me = me;

That will crash all the other answers if passed as an argument. Circular references are very mon.

Some solutions.

• First solution is to only accept data in the form of a JSON string and equally return the data as a JSON string (so balance is maintained and the universe does not explode). Thus eliminating any chance of a circular reference.

• Track recursion depth and set a limit. Though this will stop a callstack overflow it will not prevent the result being flawed as a shallow circular reference can create duplicate object references.

• The quick down and dirty solution is a simple try catch around a JSON.stringify and throw TypeError("Object can not be searched"); for those on that side of the data bus..

• The best solution is to decycle the object. Which in this case is very amenable to the actual algorithm we are using. For each unique object that is encountered we place it in an array. If we encounter an object that is in that array we ignore it and move on.

---

A possible solution.

Thus the general purpose solution, that is safe (I hope) and flexible. Though it is written for ES6 so legacy support will have to be provided in the form of babel or the like. Though it does e with a BUT!

// Log function 
function log(data){console.log(data)}

// The test data
var a = {
    a : "a",
    one : {
        two : {
            find : "me",
            data : "and my data in one.two"
        },
        twoA : {
            four : 4,
            find : "me",
            data : "and my data in one.twoA"
        }
    },
    two : {
        one : {
            one : 1,
            find : "not me",
        },
        two : {
            one : 1,
            two : 1,
            find : "me",
            data : "and my data in two.two"
        },
    },
    anArray : [
        null,0,undefined,/./,new Date(),function(){return hi},
        {
            item : "one",
            find : "Not me",
        },{
            item : "two",
            find : "Not me",
            extra : {
                find : "me",
                data : "I am a property of anArray item 1",
                more : {
                    find : "me",
                    data : "hiding inside me"
                },
            }
        },{
            item : "three",
            find : "me",
            data : "and I am in an array"
        },{
            item : "four",
            find : "me",
            data : "and I am in an array"
        },
    ],
    three : { 
        one : {
            one : 1,
        },
        two : {
            one : 1,
            two : 1,
        },
        three : {
            one : 1,
            two : {
                one : {
                    find : "me",
                    data : "and my data in three.three.two.one"
                }
            }
        }
    },
}

// Add cyclic referance
a.extra = {
    find : "me",
    data : "I am cyclic in nature.",
}
a.extra.cycle = a.extra;
a.extraOne = {
    test : [a],
    self : a,
    findme : a.extra,
};




if(! Object.allWith){
    /*  Non writeable enumerable configurable property of Object.prototype 
        as a function in the form
        Object.allWith(predicate)
        Arguments
            predicate Function used to test the child property takes the argument
               obj the current object to test
            and will return true if the condition is meet 
        Return
            An array of all objects that satisfy the predicate
            
        Example
        
        var test = {a : { key : 10, data: 100}, b : { key : 11, data: 100} };
        var res = test.allWith((obj)=>obj.key === 10);
        // res contains test.a
    */
    Object.defineProperty(Object.prototype, 'allWith', {
        writable : false,
        enumerable : false,
        configurable : false,
        value : function (predicate) {
            var uObjects = [];
            var objects = [];
            if (typeof predicate !== "function") {throw new TypeError("predicate is not a function")}
            (function find (obj) {
                var key;
                if (predicate(obj) === true) {objects.push(obj)}
                for (key of Object.keys(obj)) {
                    let o = obj[key];
                    if (o && typeof o === "object") {
                        if (! uObjects.find(obj => obj === o)) {
                            uObjects.push(o);
                            find(o);
                        }
                    }
                }
            } (this));
            return objects;
        }
    });
}else{
    console.warn("Warn!! Object.allWith already defined.");
}

var res = a.allWith(obj => obj.find === "me");
res.forEach((a,i)=>(log("Item : " + i + " ------------"),log(a)))

Why are you searching through unknown data structures?

It works for all the test cases I could e up with, but that is not at all the definitive test. I added it to the Object.prototype because you should not do that!!! nor use such a function or derivative thereof.

This is the first time I have written such a function, and the reason is that I have never had to write something like that before, I know what the data looks like and I dont have to create dangerous recursive iterators to find what is needed.. If you are writing code and you are not sure of the data you are using there is something wrong in the design of the whole project.

Hopefully this will help you to solve your task. Lets use recursion to search deep into object. Also lets make it more generic.

// search function takes object as a first param and
// a predicate Function as second predicate(key, value) => boolean
function search(obj, predicate) {
    let result = []; 
    for(let p in obj) { // iterate on every property
        // tip: here is a good idea to check for hasOwnProperty
        if (typeof(obj[p]) == 'object') { // if its object - lets search inside it
            result = result.concat(search(obj[p], predicate));
        } else if (predicate(p, obj[p])) 
            result.push(
               obj
            ); // check condition
    }
    return result;
}

Lets test it!

var obj = {
    id: 1,
    title: 'hello world',
    child: {
        id: 2,
        title: 'foobar',
        child: {
            id: 3,
            title: 'i should be in results array '
        }
    },
    anotherInnerObj: {
        id: 3,
        title: 'i should be in results array too!'
    }
};

var result = search(obj, function(key, value) { // im looking for this key value pair
    return key === 'id' && value === 3;
});

Output:

result.forEach(r => console.log(r))
// Object {id: 3, title: "i should be in results array "}
// Object {id: 3, title: "i should be in results array too!"}

You've created a returned array. First, push the result of searchObj() into it. Then in your loop, if you get a result, concat() it to returned. Finally, return returned at the end of the function. That should do it...

You could use a simplified version and

• check if object not truthy or object is not an object, then return
• check if given key and value match, then add the actual object to the result set,
• get the keys and iterate over the properties and call the function again.

At last, the array with the collected objects is returned.

function getObjects(object, key, value) {
    function iter(o) {
        if (!o || typeof o !== 'object') {
            return;
        }
        if (o[key] === value){
            result.push(o);
        }
        Object.keys(o).forEach(function (k) {
            iter(o[k]);
        });
    }

    var result = [];
    iter(object);
    return result;
}

var object = { id: 1, title: 'hello world', child: { id: null, title: 'foobar', child: { id: null, title: 'i should be in results array ' } }, foo: { id: null, title: 'i should be in results array too!' }, deep: [{ id: null, value: 'yo' }, { id: null, value: 'yo2' }] };

console.log(getObjects(object, 'id', null));

.as-console-wrapper { max-height: 100% !important; top: 0; }

本文标签： javascriptDeep Search JSONObjectStack Overflow