在字典中递归查找键

Question

我正在尝试写一个非常简单的函数，用来递归地搜索一个可能嵌套的（在最极端的情况下可以有十层深）Python字典，并返回它找到的第一个指定键的值。

我不明白为什么我的代码在处理嵌套字典时不工作。

def _finditem(obj, key):
    if key in obj: return obj[key]
    for k, v in obj.items():
        if isinstance(v,dict):
            _finditem(v, key)

print _finditem({"B":{"A":2}},"A")

它返回的是None。

不过，对于_finditem({"B":1,"A":2},"A")这个调用，它是可以正常工作的，返回2。

我相信这只是一个简单的错误，但我找不到。感觉在标准库或者collections里可能已经有类似的东西，但我也找不到。

---

_{如果你想了解这段代码有什么问题的总体解释，可以参考这个链接：为什么我的递归函数返回None？ 这里的回答主要是针对在嵌套字典中搜索的任务。}

Answer 1

这里有一种方法可以使用“栈”和“迭代器栈”模式来实现这个功能（感谢Gareth Rees的贡献）：

def search(d, key, default=None):
    """Return a value corresponding to the specified key in the (possibly
    nested) dictionary d. If there is no item with that key, return
    default.
    """
    stack = [iter(d.items())]
    while stack:
        for k, v in stack[-1]:
            if isinstance(v, dict):
                stack.append(iter(v.items()))
                break
            elif k == key:
                return v
        else:
            stack.pop()
    return default

执行print(search({"B": {"A": 2}}, "A"))时，会输出2。

Answer 2

这里有一个函数，它可以在一个字典里搜索，这个字典里面可能包含其他字典和列表。这个函数会生成一个结果值的列表。

def get_recursively(search_dict, field):
    """
    Takes a dict with nested lists and dicts,
    and searches all dicts for a key of the field
    provided.
    """
    fields_found = []

    for key, value in search_dict.items():

        if key == field:
            fields_found.append(value)

        elif isinstance(value, dict):
            results = get_recursively(value, field)
            for result in results:
                fields_found.append(result)

        elif isinstance(value, list):
            for item in value:
                if isinstance(item, dict):
                    more_results = get_recursively(item, field)
                    for another_result in more_results:
                        fields_found.append(another_result)

    return fields_found

Answer 3

当你使用递归的时候，需要把 _finditem 的结果返回。

def _finditem(obj, key):
    if key in obj: return obj[key]
    for k, v in obj.items():
        if isinstance(v,dict):
            return _finditem(v, key)  #added return statement

要修正这个算法，你需要明白如果 _finditem 没找到任何东西，它会返回 None，所以你需要明确检查这个情况，以防止过早返回：

def _finditem(obj, key):
    if key in obj: return obj[key]
    for k, v in obj.items():
        if isinstance(v,dict):
            item = _finditem(v, key)
            if item is not None:
                return item

当然，如果你的字典里有 None 值，这样做就会出错。在这种情况下，你可以为这个函数设置一个哨兵 object()，如果没找到任何东西就返回这个哨兵对象——这样你就可以通过检查这个 sentinel 来判断是否找到了东西。