java - 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)] 时间运行的？如果没有，正确答案是什么？

Answer 1

当您从字符串(或 JSONTokener)实例化 JSONObject 时，

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