这其实就是时间、空间复杂度互换的设计思想
邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是使用起来就比较耗时间。
就像图中的例子，如果要确定，是否存在一条从顶点 2 到顶点 4 的边，那就要遍历顶点 2 对应的那条链表，看链表中是否存在顶点 4。
而且，链表的存储方式对缓存不友好。
所以，比起邻接矩阵的存储方式，在邻接表中查询两个顶点之间的关系就没那么高效了。
在基于链表法解决冲突的散列表中，如果链过长，为了提高查找效率，可以将链表换成其他更加高效的数据结构，比如平衡二叉查找树等。
邻接表长得很像散列表。所以，也可以将邻接表同散列表一样进行“改进升级”。
可以将邻接表中的链表改成平衡二叉查找树，来提高查询效率。
实际开发中，可以选择用红黑树。这样，就可以更加快速地查找两个顶点之间是否存在边了。
这里的二叉查找树可以换成其他动态数据结构，比如跳表、散列表等。
除此之外，还可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。
四、如何存储微博社交网络中的好友关系
数据结构是为算法服务的，所以具体选择哪种存储方法，与期望支持的操作有关系。针对微博用户关系，假设需要支持下面这样几个操作：
判断用户 A 是否关注了用户 B；
判断用户 A 是否是用户 B 的粉丝；
用户 A 关注用户 B；
用户 A 取消关注用户 B；
根据用户名称的首字母排序，分页获取用户的粉丝列表；
根据用户名称的首字母排序，分页获取用户的关注列表。
关于如何存储一个图，主要的存储方法有：邻接矩阵和邻接表。
因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间。所以，这里采用邻接表来存储。
不过，用一个邻接表来存储这种有向图是不够的。
比如去查找某个用户关注了哪些用户非常容易，但是如果要想知道某个用户都被哪些用户关注了，也就是用户的粉丝列表，是非常困难的。
基于此，需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。
对应到图上，邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。
如果要查找某个用户关注了哪些用户，可以在邻接表中查找；如果要查找某个用户被哪些用户关注了，从逆邻接表中查找。
基础的邻接表不适合快速判断两个用户之间是否是关注与被关注的关系，所以选择改进版本，将邻接表中的链表改为支持快速查找的动态数据结构。
比如：红黑树、跳表、有序动态数组、散列表等。
因为需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，这里选择跳表。
因为，跳表插入、删除、查找都非常高效，时间复杂度是 O(logn)，空间复杂度上稍高，是 O(n)。
最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效。
如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。
但是如果像微博那样有上亿的用户，数据规模太大，就无法全部存储在内存中了。
可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。
如下图所示：机器1上存储顶点1， 2， 3的邻接表，在机器2上，存储顶点4， 5的邻接表。逆邻接表的处理方式也一样。
当要查询顶点与顶点关系的时候，就利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上查找。