讲个大部分数据结构和算法教科书中都不会讲的问题

919 阅读1分钟

大部分数据结构和算法书籍中,在讲某种数据结构和算法的时候,都会拿整数作为要处理的数据的类型。实际上,在真实的软件开发中,数据结构中存储的数据、算法要处理的数据,往往都不是简单的整数,而是”对象“。这里的”对象“很好理解,就是编程语言的中的”类与对象“中的对象。比如下面这几行Java代码,我们用红黑树来存储Order订单对象。

// 红黑树来存储订单,key是订单ID,value是订单对象
private TreeMap<Long, Order> id2OrderMap = new TreeMap<>(); 
 
public void add(Order order) { // 添加一个订单
 id2OrderMap.put(order.id, order);
}
 
private class Order { // 订单类
 public long id;
 public long userId;
 public long createTime;
 // ...more fields...
}

不过,你可能会有疑问,既然在真实的软件开发中,数据结构和算法要处理的都是对象,那为啥书本中都可以按照拿整数类型,而不是对象来讲解呢?

我们知道,数据结构和算法要解决的都是”更快“、”更省“的问题。更快指代码的执行速度,更省指存储空间的消耗。

”更快“这里你先简单理解为”查找更快“,当然还有增删改以及一些统计操作,不过,都差不多,你理解了”查找“,其他的操作也就都理解了。我们在一组数据中,查找一个想要的数据的时候,都是通过某个键值(key)来查找的。

这里的键值怎么理解呢?我们拿刚刚的订单的例子来说明一下。我们希望在这组订单中,按照订单ID来快速的查找订单。那我们就把订单的ID看做键值(key),并且按照key来组织成红黑树这种数据结构。红黑树中存储的是key值和订单对象的内存地址,而订单对象本身是存储在另外的内存空间中的(像Java这种语言,就是存储在堆内存中的)。

为了方便你理解,我画了一张图,你可以对比着文字描述看下。

那你可能说,那我要是再想通过订单的用户ID来查找订单呢?这个时候该怎么办呢?

你就可以再以用户ID作为键值,创建另外一个红黑树。实际上,这就是我们之前文章中提到的多重索引结构。如果翻译成Java代码的话,就是下面这一个样子。

// 两个索引
private TreeMap<Long, Order> id2OrderMap = new TreeMap<>();
private TreeMap<Long, Order> userId2OrderMap = new TreeMap<>();
 
public void add(Order order) { // order在外部创建,内存中只有一份
 id2OrderMap.put(order.id, order);
 userId2OrderMap.put(order.id, order);
}
 
private class Order {
 public long id;
 public long userId;
 public long createTime;
 // ...more fields...
}

如果画成图的话,就是下面这个样子。你会发现,订单对象是只有一份的,而索引结构有两份,一份是按照订单的ID作为键值创建的,另一份是按照订单的用户ID作为键值创建的。

你可能会说,两份索引是不是比较浪费内存空间啊?实际上,并不会。

从我前面的讲解中,你应该已经知道,索引中存储的只是就键值和对象的内存地址,如果键值是大小比较小的整数,而对象是比较大的对象(数据本身),那索引所占用内存空间比起对象所占用的内存空间来说,要小很多。

还是刚才那个订单的例子,如果一个订单对象中包含很多字段,大小是1KB,而红黑树索引中,每个节点(对应一个订单对象)的大小要远小于1KB(这个你可以自己算下)。所以,所占用内存空间会远小于订单数据本身存储所需的内存空间。

也就是说,在实际上的软件开发中,如果你要存储、要处理的是大对象,那索引所占的内存空间,是可以忽略的。当然,这个要权衡实际上情况来看,不可生搬硬套。

回到开头的问题,既然真实的软件开发中,数据结构和算法处理的数据类型都是对象,那为什么大部分数据结构和算法教科书中,都是拿整数类型来讲解呢?

因为我们在构建数据结构的时候,是按照键值构建,算法在执行的时候,也是按照键值来处理数据。键值一般都是整数(有时候是字符串,处理起来一样),我们拿整数类型来讲解,简单明了,足够了。

作者王争,前Google工程师,15万人订阅的《数据结构和算法之美》《设计模式之美》作者。微信公众号:小争哥,关注微信公众号回复PDF,获取100+页Google工程师的算法学习和面试经验分享。