检测 JSON 数组中没有重复项的最快正确方法是什么？

Question

我需要检查 serde_json::Value 数组中的所有项目是否都是唯一的。由于这种类型没有实现 Hash 我想出了以下解决方案：

use serde_json::{json, Value};
use std::collections::HashSet;

fn is_unique(items: &[Value]) -> bool {
    let mut seen = HashSet::with_capacity(items.len());
    for item in items.iter() {
        if !seen.insert(item.to_string()) {
            return false;
        }
    }
    true
}

fn main() {
    let value1 = json!([1, 2]);
    assert!(is_unique(&value1.as_array().unwrap()));
    let value2 = json!([1, 1]);
    assert!(!is_unique(&value2.as_array().unwrap()));
}

我认为它应该只有在 serde_json 是用 preserve_order 特性构建的（每次都以相同的顺序序列化对象）时才应该有效，但我不是 100% 确定。

主要使用上下文:

JSON 架构验证。 “uniqueItems”关键字实现。

相关使用案例

JSON 数组的重复数据删除以优化对它们的 JSON 模式推断。

例如输入数据为[1, 2, {"foo": "bar"}]。一个简单的推论可能输出如下：

{
    "type": "array", 
    "items": {
        "anyOf": [
            {"type": "integer"}, 
            {"type": "integer"},
            {"type": "object", "required": ["foo"]}
        ]
    }
}

items/anyOf 中的值可以减少到只有两个值。

问题：检查任意 JSON 数组中没有重复项的最省时且最正确的方法是什么？

我用了serde_json = "1.0.48"

生锈：1.42.0

Playground

Answer 1

取决于 JSON 数组是否已排序。如果已排序，您可以使用二进制搜索来检查该值是否与其他值匹配。要排序，您可以使用归并排序。总复杂度为 O(nlogn + logn)。或者您可以按顺序迭代并检查重复行 O(n^2)。

Answer 2

将每个数组项转换为字符串的成本相当高——它至少需要为每个项分配一个字符串，而且很可能不止于此。确保映射（或 JSON 语言中的 "objects"）以规范形式表示也很困难。

一个更快、更强大的替代方法是自己为 Value 实施 Hash。您需要定义一个新类型包装器，因为您不能在外部类型上实现外部特征。这是一个简单的示例实现：

use serde_json::Value;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;

#[derive(PartialEq)]
struct HashValue<'a>(pub &'a Value);

impl Eq for HashValue<'_> {}

impl Hash for HashValue<'_> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        use Value::*;
        match self.0 {
            Null => state.write_u32(3_221_225_473), // chosen randomly
            Bool(ref b) => b.hash(state),
            Number(ref n) => {
                if let Some(x) = n.as_u64() {
                    x.hash(state);
                } else if let Some(x) = n.as_i64() {
                    x.hash(state);
                } else if let Some(x) = n.as_f64() {
                    // `f64` does not implement `Hash`. However, floats in JSON are guaranteed to be
                    // finite, so we can use the `Hash` implementation in the `ordered-float` crate.
                    ordered_float::NotNan::new(x).unwrap().hash(state);
                }
            }
            String(ref s) => s.hash(state),
            Array(ref v) => {
                for x in v {
                    HashValue(x).hash(state);
                }
            }
            Object(ref map) => {
                let mut hash = 0;
                for (k, v) in map {
                    // We have no way of building a new hasher of type `H`, so we
                    // hardcode using the default hasher of a hash map.
                    let mut item_hasher = DefaultHasher::new();
                    k.hash(&mut item_hasher);
                    HashValue(v).hash(&mut item_hasher);
                    hash ^= item_hasher.finish();
                }
                state.write_u64(hash);
            }
        }
    }
}

None 的值是随机选择的，以使其不太可能与其他条目冲突。为了计算浮点数的哈希值，我使用了 ordered-float crate。对于映射，代码为每个 key/value 对计算一个散列，然后简单地将这些散列异或在一起，这是与顺序无关的。有点不幸的是，我们需要对用于散列映射条目的散列器进行硬编码。我们可以通过定义我们自己的 Hash 特征版本来抽象它，然后从我们自定义的 Hash 特征中派生出 std::hash::Hash 的具体实现，但这会使代码复杂化很多，所以除非你需要，否则我不会那样做。

我们无法导出 Eq，因为 Value 没有实现 Eq。但是，我认为这只是一个疏忽，所以我 filed an issue to add an Eq implementation（PR 已被接受，因此它将在未来的某个版本中发布）。

检测 JSON 数组中没有重复项的最快正确方法是什么？

What is the fastest correct way to detect that there are no duplicates in a JSON array?

algorithm

json

rust

serde