getJSONObject 和 getJSONArray 方法的复杂性是什么？

Question

我正在使用 org.json 库作为我的 Java 应用程序的 JSON-客户端，我想知道这个库中某些方法的复杂性。

我正在通过 HTTP API 从数据库中检索另一个 JSON 对象（等等）中的 JSON 数组中的数千个 JSON 对象。作为示例（仅作为示例，我的情况要复杂得多），假设我正在做类似的事情：

// Ignoring attributes types
import org.json.*;

public static void main(String[] args) {
    response = MyHTTPClient.post(url, query).asJSON();
    response = JSON.parse(response);
    data = response.getJSONObject(1).getJSONArray("results").getJSONObject(0);
}

org.json 库中的 getJSONObject(int) 和 getJSONArray(String) 方法的复杂性如何？它是运行在常数 [O(1)] 或线性 [O(n)] 时间内？如果none，正确答案是什么？

Answer 1

当您从字符串（或 JSONTokener）实例化 JSONObject 时，

org.json 将解析整个 JSON 文档。 getJSONObject() 和 getJSONArray() 方法只是无类型 get() 方法的类型版本（return Object 实例）。如果您查看源代码，您会发现 JSONObject 使用 HashMap 而 JSONArray 使用 ArrayList 进行内部表示，因此执行时间接近恒定（ O(1))

Answer 2

getJSONArray 和 getJSONObject 以及方法最终都会调用 opt(String paramString) 方法，该方法从 HashMap 获取值。所以他们应该在接近恒定的时间内工作，即理想情况下为 O(1)。这是一个代码片段：

public Object opt(String paramString)
{
  return paramString == null ? null : map.get(paramString);
}

大家可以自己看源码，深入挖掘。

getJSONObject 和 getJSONArray 方法的复杂性是什么？

What's the complexity of getJSONObject and getJSONArray methods?

java

json

time-complexity

asymptotic-complexity

org.json