对key-value“键值对”的理解，以及现实世界中的key-value

为什么有这样的疑问？

看《Algorithms 4th》的 Priority Queue 一节，书里频繁提到将key排序的情况，但之前的排序没提过key-value这种结构。

public class MaxPQ<Key extends Comparable<Key>>

这个PQ结构里，支持把无限数目的key陆续放到队列里，这个队列的大小是人为固定的，PQ主要依靠insert和delMax(delMin)操作，后者返回最大或最小值。

为什么是key，而不是直接将value排序？
其实我对key-value这种键值对根本不理解。

实体与指标(属性)

实际key-value有很多应用，我觉得最容易让我理解的是计算机里的进程概念，计算机下一次执行哪个程序，是靠一个动态的列表决定的，这个列表应该是进程优先级的排序，每次取进程优先级最高的那个进程。但进程本身是无法排序的，所以需要把key放到队列里排序，再通过key找到进程。

所以可以清晰一些概念了，待排序的本应该是一系列支持comparable的实体集合，比如整数、字符串等，但是这些都算是虚拟的实体，现实世界的实体本身仅仅是一个实体，想描述这个实体需要利用一些指标，比如重量、大小、颜色等固有属性，名称是人赋予的，位置则是不稳定的。

比如我们想给一群人排序，排法是多种多样的，可以根据身高、体重、年龄、人的姓氏拼音、家庭住址的远近排……所以说实体本身不能排序，能排的是实体的一些指标或属性。仅仅是一个身高的序列一般是没什么意义的，这个身高只有跟具体的人绑定起来才有意义(当然也不是一定没意义，比如我就想知道这个学校里身高的分布)。跟实体绑定的过程就是key-value这种键值组合的过程，key是身高，value是实体，但实体本身是现实世界中的，我们需要给它赋予一个符号排代表它，所以value就是人的名字(或学号)。

进程不是现实世界中的实体，但是进程本身仅仅是进程，不可比较大小，这一点与现实中的实体是类似的，我们往往给进程一个名称、进程号等等，这是为了标识某个特定进程，在某个进程的生命周期中往往是不变的(如果能变化就不能唯一标识某个进程了)。进程的优先级，这个值是需要计算出来的，不同时刻不同进程的优先级值都是变化的。我们的目的是将进程优先级排出序来，但进程优先级值的分布我们一般是不关心的，所以key是优先级值，排好后通过key将value取出来，即得到真正的进程名，然后操作系统再通过进程名来做调度。

“比较大小”到底是什么意思

我这里先随便说一下，具体可能要读测度论。

比较大小是数学中的概念，能比较大小的事物，本质上都会把事物映射到一个实数数轴上，再通过加减(或左右位置)来决定大小。程序语言里我们能自己定义不同事物的比较方法，实现comparable接口，本质上还是建立事物到实数数轴的映射，而且映射函数中一定会用到事物的指标(属性)。这样就能直接利用普通的方法对事物排序了，因为排好序后我们自然就得到了有序的事物，每个事物都是一个复合的数据结构。

所以MaxPQ<Key extends Comparable<Key>>里的key也可以是实现了comparable的实体类，这样就不用再通过key去取值了。

所以总结一下，在学merge sort等排序方法时，一般我都是直接对整数排序，整数天然就是可排序的数学抽象实体；对普通的实体排序，则需要实体实现comparable方法。在Priority Queue里，往往直接对key进行排序，再通过key去取实际的实体，其实这也是个measure映射过程，把实体映射为key值，本质上跟实现comparable方法再去排序是一样的。

更广义的key-value

脱离开排序的领域谈谈key-value

在真实世界里，实体本身仅仅是实体，想标识它，可以给它名字，但是仅仅有名字是不够的，需要建立映射关系才行，这样才能通过名字取出实体。
可实际上，实体本身跟名字没办法建立一一映射，需要利用实体的属性。比如我们认一个人，肯定是先确定ta的样貌(有时相貌还不够，还需要对话等过程)，然后再认定ta是某某人。这里有个假设，就是实体由其属性来唯一确定，属性是多维的。属性值集合->名称，这才是最终的映射，其实实体是不能直接认识的，我们只是通过一系列属性值来判断某个实体存在的。

key-value对是普遍存在的，这里key是名字，value是属性值集合，value将不同事物区分开来，然后我们再用key对这个事物标识。

key-value pair in searching

在搜索技术里key-value pair扮演什么角色呢？

好的例子：一本书最后的索引，key是关键字，value页码

查找的过程就是信息匹配的过程，就是看有没有与你手上信息相匹配的条目，找到的话，就拿出对应的value，value是我们真正关心的，而且是难以记忆的，可能很长(比如一个网页地址)，key是容易记忆的短的东西，比如一个实体的名字。

所以key是符号，value是实体，或者说实际数据体。