K/V 与 Array
接触 JSON 的人都知道，JSON 可通过 K/V（Key/Value） 结构很直观地表现一棵树，因为 V 可以“包含”另外一个 K/V 从而不断嵌套下去形成“树状”的结构。但 V 不一定必须为另外一个 K/V，而是可以为 Array 数组。数组中由可以“包含”更多的 K/V 或者又是数组类型——也是可以的。如此反复下去，可以形成层数很深的一棵树。例如
{
aa : {
cc ：[
“dd”,
{
ee: true, ff: “hihi”
}
]
},
bb: [ ]
}
这里说的树是指无序树，甚至根节点也没有，不过没关系，在最外一层加上便是。
比较微妙的是 JSON 允许了数组和 K/V 相互嵌套。下级子节点应该用 K/V 来装，还是用 Array 来装呢？又怎么理解数组和 K/V 的关系呢？个人理解，数组本质上也可以归纳其为 K/V。我们一般讨论数组时候还会接触到数组的索引，例如 arr[0] = a, arr[1] = b，索引便是 key 的一种，只不过我们通常 JSON 里面的 key 为字符串，实际上为 int 类型也是允许的。相较而言，数组结构比 K/V 的简单，是 K/V 的一种简化。当然我这种只是“大而化之”的理解，——实际上它们差别很多，好比它们的数据结就显著不同：数组仅仅是一个线性表；K/V 会复杂的多，一般要经过多步 hash 的运算。
再看看上面的 JSON 例子，看起来这个 JSON 想要表达很多东西，最外层是个 K/V，里面的 aa 是下一层的 K/V，但 bb 却是数组，——似乎结构有点混乱。如果用来表现一个树，显然也是一颗“混乱的树”。如果实际开发遇到这样结构的设计，那肯定有问题的，需要好好简化的。不过，无论怎么简化，一旦引入树的概念后，好像还是会有矛盾的地方，例如 K/V 和 Array 两者都可以延伸一下级节点，它们之间有什么不同呢？什么时候该用 K/V 呢？什么时候又该使用 Array 呢？这并无标准答案，JSON 自身并不会说明清楚或者强制要求。再例如 cc 这个数组，第一个元素是字符串，第二个元素是 K/V。因为我们知道，JSON 包含的元素可允许是不同类型的，即混合多种类型的值为一个数组——那样本身是没问题的。但结合树的概念的话问题就来了，是否 K/V 就必须是引出下级树节点吗？——我大可以理解为 JSON 的一个值，她是 K/V 类型，那也是合法的啊，同理数组也不一定引出下级的节点，当前只是表现同类对象的集合，——那也是完全合法的。所以怎么定义这是个树节点，还是说一个 JSON 值？二义性的问题由此产生了。
为解决这个二义性的问题，我们可以对 JSON 作适当的约定，以便更清晰地和准确地反映一棵树。首先节点用 K/V 表示；Children 是下级节点的数组，是容器。它不能是其他的类型如 map 的类型，只能是 Array。只有 最外一层 和 父容器名为 children 的数组，里面的 K/V 才是树节点。一个节点可以有零个或一个 children 的 K/V，且 V 必然是数组。
如下便是一个我们约束定义的树：
[ {
'name' : "关于我们",
'id' : 'about',
'children' : [
{
name : "公司历程",
id : 'history'
},
{
name : "企业文化",
id : 'cluture'
}
]
}, {
'name' : "美食天地",
'id' : 'product',
'children' : [
{
name : "最新美食",
id : 'new',
'children' : [
{
'id' : 'yuecai',
'name' : '粤菜'
},
{
'id' : 'yuecai',
'name' : '湘菜'
}
]
},
{
name : "热门菜谱",
id : 'hot'
}
]
},
{
'name' : "最新资讯",
'id' : 'news'
},
{
'name' : "招聘信息",
'id' : 'hr'
}, {
'name' : "联系我们",
'id' : 'contact'
}]
值得注意的是该结构最外一层为 Array 而不是 K/V。
遍历 JSON
JSON 本身乃 JavaScript 的产物，虽然也有序列化和反序列化的过程，但使用起来还是比较自然、“原生原味”的。
这里重点说说 Java 世界处理 JSON 的话题。当 JSON 字符串经过解析器反序列化之后，可得到 Java 识别的类型。如果引入三方包，就有其自定义的类型（如 JSONArray、JSONObject）。但是我们这里不使用三方包的类型来说明问题（虽然可能都是“同理”得出一致的结论），——因为那又牵涉到该使用哪个三方包的问题（选择困难症患者-_-）。
于 Java 而言与 JSON 对应的结构一般自然的选择是 Map/List 组合——本文就拿 Map/List 就好了。这里用泛型可以加强说明所包含元素的类型是什么，使之更加直观和清晰，即 Map，其中，String 是 key 的类型，我们知道 JSON 的key 类型就是字符串类型；Object 便是 Value 的类型，可以是合法的 JSON 值（字符串、数字、null），或者是另外一个 Map 或 List。至于 List 的泛型便是嵌套的 List<Map>。于是，我们可以写一个方法（或者第三方包），JSON 字符串被解析之后，得到 Map/List 结构的 Java 类型，变成 Java 可以理解的“树”。应该怎么遍历的这棵树呢？最简单的方法，莫过于递归这个 Map/List。
好比现在输入这段 JSON，这是网站的配置文件：
{
"site" : {
"titlePrefix" : "大华•川式料理",
"keywords" : "大华•川式料理",
"description" : "大华•川式料理饮食有限公司于2015年成立，本公司目标致力打造中国新派川菜系列。炜爵爷川菜料理系列的精髓在于清、鲜、醇、浓、香、烫、酥、嫩，擅用麻辣。在服务出品环节上，团队以ISO9000为蓝本建立标准化餐饮体系，务求以崭新的姿态面向社会各界人仕，提供更优质的服务以及出品。炜爵爷宗旨：麻辣鲜香椒，美味有诀窍，靓油用一次，精品煮御赐。 ",
"footCopyright":"dsds"
},
"dfd":{
"dfd":'fdsf',
"id": 888,
"dfdff":{
"dd":'fd'
}
},
"clientFullName":"大华•川式料理",
"clientShortName":"大华",
"isDebug": true,
"data" : {
"newsCatalog_Id" : 6,
"jobCatalog_Id" :7
}
}
送入 JSON 解析器得到 Map：
这里暂忽略 JSON 解析器的原理。先接着看看遍历 JSON 的过程。假设我们要把所有 key 列出来
@SuppressWarnings("unchecked")
public void travel(Map<String, Object> map) {
for (String key : map.keySet()) {
Object obj = map.get(key);
System.out.println("The key is:" + key);
if (obj != null && obj instanceof Map) {
Map<String, Object> _map = (Map<String, Object>) obj;
travel(_map);
}
}
}
打印结果如下
前面说到，我们讨论的是树结构，已经有这样的约定：如果遇到 Key 为 children 且 value 为数组元素的话，那就下级节点，数组里的都是子节点 K/V。否则就是普通的一个 JSON 数组。
@SuppressWarnings("unchecked")
public void travel(Map<String, Object> map) {
for (String key : map.keySet()) {
Object obj = map.get(key);
System.out.println("The key is:" + key);
if (obj != null && obj instanceof Map) {
Map<String, Object> _map = (Map<String, Object>) obj;
if (_map.get(children) != null && _map.get(children) instanceof List) {
List<Map<String, Object>> list = (List<Map<String, Object>>) _map.get(children);
for (Map<String, Object> __map : list)
travel(__map);
}
}
}
}
与前面的函数相比只是增加了 children 的判断，然后遍历 children 里面各项的 map。——一切都非常简单是吧？可以说毫无惊艳之处。不过读者可试着改造一下，把当前支持 Map<String, Object> map 类型的参数改为List<Map<String, Object>> list 的，看看遍历过程有什么不同。
分析树
现在不妨把需求的难度提高那么一丢丢：希望可以完整记下节点的完整的“路径”和层级。文章到这里写得太长太冗长了，笔者还是赶紧给出代码，赶紧收尾。
输入 JSON 数组：
[ {
'name' : "关于我们",
'id' : 'about',
'children' : [
{
name : "公司历程",
id : 'history'
},
{
name : "企业文化",
id : 'cluture'
}
]
}, {
'name' : "美食天地",
'id' : 'product',
'children' : [
{
name : "最新美食",
id : 'new',
'children' : [
{
'id' : 'yuecai',
'name' : '粤菜'
},
{
'id' : 'yuecai',
'name' : '湘菜'
}
]
},
{
name : "热门菜谱",
id : 'hot'
}
]
},
{
'name' : "最新资讯",
'id' : 'news'
},
{
'name' : "招聘信息",
'id' : 'hr'
}, {
'name' : "联系我们",
'id' : 'contact'
}]
这里给出前一小节的答案，就是遍历 List 的，并增加了功能。
/**
* 分析这棵树，为每个节点增加 fullPath 和 level 属性，分别表示完整的路径和层数
*
* @param list
* 输入的树，必须为 List
* @param superNode
* 父级节点
* @param level
* 层数
*/
@SuppressWarnings("unchecked")
public void travelList(List<Map<String, Object>> list, Map<String, Object> superNode, int level) {
for (Map<String, Object> map : list) {
if (map != null) {
String currerntPath = (superNode != null ? superNode.get("fullPath").toString() : "") + "/" + map.get(id).toString();
map.put("fullPath", currerntPath);
map.put("level", level);
// 记录父级信息
List<String> supers = new ArrayList<>();
map.put("supers", supers);
if (superNode != null) {
supers.addAll((List<String>) superNode.get("supers"));
supers.add(superNode.get("fullPath") + ":" + superNode.get("name")); // 仅记录 id 和 name
}
if (map.get(children) != null && map.get(children) instanceof List)
travelList((List<Map<String, Object>>) map.get(children), map, level + 1);
}
}
}
结果是
好吧，我承认，这也不是太难的例子，仍然不外乎 for 循环+ 递归。下一篇要写 Stack 的内容了。