15 字典（上）：关联式数据结构的基本表示
你好，我是海纳。
前边两节课我们引入了 Python 语言中最重要的一个数据结构：列表。接下来的两节课，我们将重点介绍字典（dict）的实现，包括字典定义、创建和对元素的增、删、查、改等操作。我们先从字典的定义开始。
字典的定义
字典是一种关联数据结构，很像 C++ 里的 map 或者 Java 里的 HashMap。字典支持键（key）和对应值（value）成对插入、添加、删除等操作。
我们以一个例子来说明字典的具体用法。
上述代码定义了一个字典，这个字典包含了两组键值对。第一组，key 是整数 1，value 是字符串 "hello"。第二组，键是字符串 "world"，值是整数2。然后把字典打印出来（第 2 行），接下来是把整数 1 所对应的值 "hello" 打印出来（第 3 行），最后把字符串 "world" 所对应的值，也就是整数 2 打印出来（第 4 行）。
通过 show_file 工具，我们能观察到 Python 为了定义字典引入了新的字节码。和列表一样，我们也要实现这些专门为字典而创造的字节码。
d = {1 : "hello", "world" : 2}
1 0 LOAD_CONST 0 ('hello')
2 LOAD_CONST 1 (2)
4 LOAD_CONST 2 ((1, 'world'))
6 BUILD_CONST_KEY_MAP 2
8 STORE_NAME 0 (d)
print(d[1])
3 18 LOAD_NAME 1 (print)
20 LOAD_NAME 0 (d)
22 LOAD_CONST 3 (1)
24 BINARY_SUBSCR
26 CALL_FUNCTION 1
28 POP_TOP
这一段反编译结果中，出现了一个新的指令：BUILD_CONST_KEY_MAP，它的作用是创建一个字典。这个字典的键是一个常量列表，即 (1，"world")。其中第一个键，也就是整数 1 所对应的值，是第一个 LOAD_CONST 指令加载到栈顶上的 "hello"，第二个键字符串 "world" 所对应的值，是第二个 LOAD_CONST 指令加载到栈顶上的整数 2。
而通过键来查找字典对应的值，则是使用 BINARY_SUBSCR 指令，这条指令复用了列表的取下标指令。虽然列表的取下标和字典查找的语法很像，它们都是使用中括号来表示，并且字节码也都是 BINARY_SUBSCR，但列表和字典还是有本质的不同。列表只能使用整数作为下标，而字典则可以使用任意对象作为键，这一点请你一定注意。
接下来，我们分步骤来实现字典的创建。
第一步是在虚拟机中实现字典类。在此之前，我们实现变量表的时候，已经编写了一个维护键值对的关联式数据结构 Map ，它可以支持数据的增删查改。所以这里只需要对 Map 进行封装，把它包装成一个 HiObject 的子类就可以了。
class DictKlass : public Klass {
private:
DictKlass();
static DictKlass* instance;
public:
static DictKlass* get_instance();
void initialize();
virtual HiObject* getattr(HiObject* x, HiString* y);
virtual HiObject* subscr (HiObject* x, HiObject* y);
virtual HiObject* iter(HiObject* x);
virtual void print(HiObject* obj);
virtual void store_subscr(HiObject* x, HiObject* y, HiObject* z);
virtual size_t size();
};
class HiDict : public HiObject {
friend class DictKlass;
private:
Map<HiObject*, HiObject*>* _map;
public:
HiDict();
HiDict(Map<HiObject*, HiObject*>* map);
Map<HiObject*, HiObject*>* map() { return _map; }
void put(HiObject* k, HiObject* v) { _map->put(k, v); }
HiObject* get(HiObject* k) { return _map->get(k); }
HiObject* remove(HiObject* k) { return _map->remove(k); }
};
在代码里，我们定义了一个新的类型 HiDict，它是 HiObject 的子类。在 HiDict 中，有一个域 _map，它的类型是 Map。我们在 HiDict 中定义了各种操作，最终都转化成了对 Map 的操作。这些操作有 3 类。
- put，向字典中添加新的键值对。
- get，给定键，取出字典中相应的值。
- remove，给定键，删除相应的键值对。由于在一个字典中，所有的键都是不重复的，所以这个方法最多只能删除一个键值对。
DictKlass 的设计与 ListKlass 的设计非常像，也采用了单例模式实现。DictKlass 中还定义了 print 方法等，这些方法逻辑比较简单，这里我就不再列出它们的代码了。如果你有需要，可以在代码仓里自行查看。
有了字典的定义，BUILD_MAP 的实现就简单多了。
/**
* BUILD_MAP
*/
void Interpreter::run(CodeObject* codes) {
_frame = new FrameObject(codes);
while (_frame->has_more_codes()) {
unsigned char op_code = _frame->get_op_code();
...
FunctionObject* fo;
...
switch (op_code) {
...
case ByteCode::BUILD_CONST_KEY_MAP:
lst = (HiList*)POP();
v = new HiDict();
for (int i = 0; i < op_arg; i++) {
((HiDict*)v)->put(lst->get(op_arg - i - 1), POP());
}
PUSH(v);
break;
...
}
}
}
请注意，BUILD_CONST_KEY_MAP 本身是带有参数的，它的参数值指示了这个字典初始化时键值对的个数。执行这条字节码的时候，栈顶的第一个元素是一个列表，其中包含了字典的全部键（第 14 行）。列表所包含的元素个数和这里要创建的字典的元素个数是相同的。键所对应的值都在栈上，所以需要使用循环语句把它们一个个地取出，并与相应的键一起添加到目标字典中（第 17 至 19 行）。
可见，这里的逻辑和 BUILD_LIST 差不多。
Python 3.8 中创建字典的逻辑和Python 2.7 版本有很大的差异。Python 2.7 使用 STORE_MAP 把键值对存入字典。Python 2.7 已经逐渐退出商用场景，所以这里我们就不再展开了，如果你有兴趣可以通过查阅相关版本的代码进行验证。
当字典的键为常量时，编译器会使用 BUILD_CONST_KEY_MAP 进行优化。如果字典的键为变量时，就只能使用 BUILD_MAP 指令来创建字典了。而使用 BUILD_MAP 时，编译出的字节码就会更多一些。你可以看一下示例。
我们通过 show_file 工具查看它所对应的字节码。
6 42 LOAD_CONST 3 (1)
44 STORE_NAME 2 (a)
7 46 LOAD_CONST 1 (2)
48 STORE_NAME 3 (b)
8 50 LOAD_NAME 2 (a)
52 LOAD_CONST 0 ('hello')
54 LOAD_NAME 3 (b)
56 LOAD_CONST 4 ('world')
58 BUILD_MAP 2
60 STORE_NAME 0 (d)
可见，BUILD_MAP 所使用的键和值都被展开加载到操作数栈上。基于以上分析，BUILD_MAP 的实现如下所示：
case ByteCode::BUILD_MAP:
v = new HiDict();
for (int i = 0; i < op_arg; i++) {
((HiDict*)v)->put(POP(), POP());
}
PUSH(v);
break;
在实现了这两个字节码以后，我们就可以运行这部分开始时的那个测试用例了。
在没有定义 HiDict 之前，我们在 FrameObject 和 FunctionObject 中使用了大量的 Map 来作为键值对的容器。有了 HiDict 以后，就不用再使用 Map 了，我们把所有的 Map 全部替换为 HiDict。这些代码散落在各个文件中，而且代码总量不大，所以这里我就不再列出了。
字典作为豪装版 Map，可以在 Python 测试代码里打印出它的内容，这是一个非常有用的功能。另外，将来在实现自动内存管理的时候，HiDict 也比 Map 更加容易操作。
接下来，我们来实现字典元素的增删查改的功能。
字典的查询和插入
刚刚的例子已经说明了，字典的查询是通过 BINARY_SUBSCR 字节码实现的，插入则依赖 STORE_SUBSCR 这个字节码。这两个字节码，在支持列表操作的时候，就已经实现过了。对于字典，我们只要在 DictKlass 中实现 subscr 和 store_subscr 方法就可以了。
刚刚我们在实现字典的基本功能时，就已经把这两个方法实现了。除此之外，字典还定义了 get 方法、has_key 方法，用来查询数据。逻辑都比较简单，这里也不再列出了。
字典中有一个特别的方法，名为 setdefault，它的作用是为指定的键设置默认值。比如 setdefault(key, value) 的作用是先查看字典中是否有 key，如果有，就什么也不做，如果没有，就把 (key, value) 插入字典。下面我给出这个方法的实现，你可以参考。
/**
* dict.setdefault
*/
void DictKlass::initialize() {
HiDict* klass_dict = new HiDict();
klass_dict->put(new HiString("setdefault"),
new FunctionObject(dict_set_default));
set_klass_dict(klass_dict);
}
HiObject* dict_set_default(ObjList args) {
HiDict* dict = (HiDict*)(args->get(0));
HiObject* key = args->get(1);
HiObject* value = args->get(2);
if (!dict->has_key(key))
dict->put(key, value);
return Universe::HiNone;
}
然后我们可以通过以下的测试用例进行测试。
# test set.default
d = {1 : "hello"}
d.setdefault(1, 2)
d.setdefault(2, 3)
print(d[1]) # "hello"
print(d[2]) # 3
从字典中删除元素
字典的删除操作有两种办法，一种是使用 pop 方法，对应 Python 2.7 中的 remove方法，另一种是使用 del 关键字。
使用 pop 方法，需要在 Klass 中添加新的方法。pop 方法接受一个参数，代表要删除的键。还可以再接受一个额外的默认参数。如果被删除的键存在，就删除字典里对应的元素，并返回对应的值。如果键不存在，返回指定的默认值。如果键不存在且默认值没有指定，就触发 KeyError 异常。下面这个例子说明了 pop 方法的具体行为，你可以看一下。
经过以上分析，我们就可以编写出对应的虚拟机代码了。
/**
* dict.pop
*/
void DictKlass::initialize() {
HiDict* klass_dict = new HiDict();
klass_dict->put(new HiString("setdefault"),
new FunctionObject(dict_set_default));
klass_dict->put(new HiString("pop"),
new FunctionObject(dict_pop));
set_klass_dict(klass_dict);
}
HiObject* dict_pop(ObjList args) {
HiDict* x = (HiDict*)args->get(0);
HiObject* y = args->get(1);
HiObject* z = Universe::HiNone;
if (x->has_key(y)) {
z = x->get(y);
x->remove(y);
}
else {
if (args->length() == 3) {
z = args->get(2);
}
}
return z;
}
del 关键字的实现，需要依赖 DELETE_SUBSCR 字节码。这个字节码在删除列表元素的时候我们也已经使用过了。这里我再展示一下删除字典数据的具体做法。
void DictKlass::del_subscr(HiObject* x, HiObject* y) {
assert(x && x->klass() == (Klass*) this);
((HiDict*)x)->remove(y);
}
不管是 pop 方法，还是 del 关键字，都会调用到 HiDict 的 remove 方法，最终会调用 Map 的 remove 方法删除元素。
到这里，字典元素的增删查改功能，就已经全部实现了。由于字典的操作复用了很多列表的字节码，以及 HiObject 中的入口函数，所以实现字典的增删查改功能就比列表容易了很多。
接下来，我们遍历字典。
遍历字典
Python 2.7 中有7 种常用的字典遍历方法，Python 3.8 只保留了其中一种。例如以下代码展示了 2.7 版本中的遍历方式：
# test_dict_iter.py
d = {1 : "a", 2 : "b"}
print d.keys() # [1, 2]
for k in d.keys():
print k, d[k]
for v in d.values():
print v
print d.items() # [(1, 'a'), (2, 'b')]
for k, v in d.items():
print k, v
for k in d.iterkeys():
print k, d[k]
for v in d.itervalues():
print v
for k, v in d.iteritems():
print k, v
for k in d:
print k, d[k]
在 3.8 版本中，只有最后一种使用字典迭代器的方式还被保留。iterkeys、itervalues 和 iteritems 三个接口被删除，而 keys、values 和 items 则发生了重大变化。我们先来讲解普通迭代器的实现，然后再详细考察 keys、values 和 items三个接口的变化。
字典迭代器
和列表的迭代器一样，字典也有迭代器，当我们使用 for 语句（GET_ITER 字节码）或者使用 iter 函数来创建一个遍历字典的迭代器的时候，就会得到一个具体迭代器对象。我们先来编码实现它。
class DictIterator : public HiObject {
private:
HiDict* _owner;
int _iter_cnt;
public:
DictIterator(HiDict* owner);
HiDict* owner() { return _owner; }
int iter_cnt() { return _iter_cnt; }
void inc_cnt() { _iter_cnt++; }
};
和列表迭代器一样，我们也使用了一个计数器 _iter_cnt 来记录当前迭代器所进行到的位置。owner 记录了迭代器要访问的字典。
虚拟机在执行 GET_ITER 这条指令的时候，会通过调用字典对象的 iter 方法来获得一个新的迭代器。
接下来，虚拟机就会循环执行 FOR_ITER 指令来获取元素，而这条指令是通过调用迭代器的__next__ 方法来实现的。所以在 DictIteratorKlass 的初始化阶段，就会把 next 这个函数名与具体的执行函数绑定起来。你可以看一下对应的代码。
// 字典迭代器的初始化
DictIteratorKlass::DictIteratorKlass() {
HiDict* klass_dict = new HiDict();
klass_dict->put(StringTable::get_instance()->next_str,
new FunctionObject(dictiterator_next));
set_klass_dict(klass_dict);
}
// __next__ 方法的对应实现
HiObject* dictiterator_next(ObjList args) {
DictIterator* iter = (DictIterator*)(args->get(0));
HiDict* adict = iter->owner();
int iter_cnt = iter->iter_cnt();
if (iter_cnt < adict->map()->size()) {
HiObject* obj = adict->map()->get_key(iter_cnt);
iter->inc_cnt();
return obj;
}
else // TODO : we need Traceback here to mark iteration end
return nullptr;
}
到这里，字典的迭代器就实现完了。接下来，我们就重点研究 keys、values 和 items 三个方法的实现。
通过视图访问字典
Python 2.7 中的 keys 方法会生成一个列表，其中包含了字典里所有的键。当字典非常大的时候，keys 的结果就会是一个非常大的列表，这会带来比较大的性能开销。
而 iterkeys 这个方法可以避免创建中间列表，因为它返回的是一个迭代器。但是我们有时又想使用 "in" 操作符来判断某个对象是否在字典中，iterkeys 则无法支持这个操作。
Python 3.8 中，重新实现了 keys 方法，把两者结合起来，这样一来既可以支持高效地遍历，也可以支持 "in" 操作符，以及交、并、差等操作。也就是说，keys 方法的返回值，既可以像迭代器，又可以像列表或者集合。
具备这个能力的神奇机制就是字典视图。字典里存储了真正的数据，而视图是一个代理工具，让使用者以不同的方式来访问这些数据。数据是不变的，但是视图却可以根据使用者的场景，在迭代器和集合、列表之间切换。
在开始之前，我们先来看一个具体的例子。
a = {1 : 100, 2 : 200, 4 : 400}
b = {3 : 100, 4 : 400}
for k in a:
print(k)
for k in a.keys():
print(k)
print(a[k])
print(3 in b.keys())
通过这个例子，我们可以看到 keys 方法既有迭代器的能力（第 7 行），也同时具备普通对象的能力（第 11 行）。要实现这一点，我们不妨定义一个 DictView 类，继承自 HiObject 类，同时还有迭代器的功能。
class DictView : public HiObject {
private:
HiDict* _owner;
int _iter_cnt;
public:
DictView(HiDict* owner);
HiDict* owner() { return _owner; }
int iter_cnt() { return _iter_cnt; }
void inc_cnt() { _iter_cnt++; }
};
template<ITER_TYPE iter_type>
HiObject* dict_view_next(ObjList args);
和上节课中的列表迭代器相同，我们也使用了一个计数器来记录当前迭代器所进行到的位置。字典提供了三种类型的迭代器，分别是 keys、values 和 items。三种不同的迭代器，它们的逻辑几乎是全部相同的，为了避免重复编码，我们使用模板来实现这三种不同的迭代器的 Klass。
// Dict views
enum ITER_TYPE {
ITER_KEY = 0,
ITER_VALUE,
ITER_ITEM
};
template<ITER_TYPE n>
class DictViewKlass : public Klass {
private:
static DictViewKlass* instance;
DictViewKlass();
public:
static DictViewKlass* get_instance();
virtual HiObject* iter(HiObject* x) { return x; }
virtual HiObject* contains(HiObject* x, HiObject* y);
};
// hiDict.cpp
HiObject* dict_keys(ObjList args) {
HiDict* x = (HiDict*)(args->get(0));
HiObject* it = new DictView(x);
it->set_klass(DictViewKlass<ITER_KEY>::get_instance());
return it;
}
HiObject* dict_values(ObjList args) {
HiDict* x = (HiDict*)(args->get(0));
HiObject* it = new DictView(x);
it->set_klass(DictViewKlass<ITER_VALUE>::get_instance());
return it;
}
HiObject* dict_items(ObjList args) {
HiDict* x = (HiDict*)(args->get(0));
HiObject* it = new DictView(x);
it->set_klass(DictViewKlass<ITER_ITEM>::get_instance());
return it;
}
dict_keys 方法的返回值是一个 DictView 对象（第 25 行）。
iter 方法中，直接将入参返回。入参实际上是一个迭代器对象，这是为了实现 GET_ITER 字节码，这种方式与 ListIterator 是完全一样的。对于 for i in d.keys() 这种写法，就会用到 iter 方法，如果你还不理解这里的实现，可以自己编写例子，查看字节码，加深理解。
我们使用枚举常量来代表不同类型的迭代器，其中 ITER_KEY 代表了遍历字典键的迭代器，而ITER_VALUE则代表了遍历字典值的迭代器。例如 dict_keys 方法中，就是把一个迭代器与键迭代器的 Klass 相关联（第 24 行）。
接下来，我们要在 DictViewKlass 中实现 next 方法。
template<ITER_TYPE iter_type>
DictViewKlass<iter_type>::DictViewKlass() {
const char* klass_names[] = {
"dict_keys",
"dict_values",
"dict_items",
};
HiDict* klass_dict = new HiDict();
klass_dict->put(StringTable::get_instance()->next_str,
new FunctionObject(dict_view_next<iter_type>));
set_klass_dict(klass_dict);
set_name(new HiString(klass_names[iter_type]));
}
DictView::DictView(HiDict* dict) {
_owner = dict;
_iter_cnt = 0;
}
template<ITER_TYPE iter_type>
HiObject* dict_view_next(ObjList args) {
DictIterator* iter = (DictIterator*)(args->get(0));
HiDict* adict = iter->owner();
int iter_cnt = iter->iter_cnt();
if (iter_cnt < adict->map()->size()) {
HiObject* obj;
if (iter_type == ITER_KEY)
obj = adict->map()->get_key(iter_cnt);
else if (iter_type == ITER_VALUE) {
obj = adict->map()->get_value(iter_cnt);
}
else if (iter_type == ITER_ITEM) {
HiList* lobj = new HiList();
lobj->append(adict->map()->get_key(iter_cnt));
lobj->append(adict->map()->get_value(iter_cnt));
obj = lobj;
}
iter->inc_cnt();
return obj;
}
else // TODO : we need Traceback here to mark iteration end
return NULL;
}
我们在这段代码里实现了模板类的 next 方法。
不同的迭代器类型，它的返回值各不相同，键迭代器每一次迭代都会取得字典中的一个键（第 29 行），值迭代器通过 get_value 获取值（第 31 行），item迭代器则通过列表来创建一个键值对作为返回值（第 34 至 37 行）。
到这里，keys 方法作为迭代器的功能就全部完成了。接着，我们来实现 in 操作判断。
在列表中，in 操作符是通过 contains 方法来实现，由于 DictView 是继承自 HiObject 的，所以天然就具备了 contains 方法，而且这个方法会转向调用自己所对应的 Klass 的 contains 方法，在这里就是 DictViewKlass 中的方法。
你要注意的是，DictViewKlass 是一个泛型类，所以在使用它的时候，要注意区分泛型参数类型。下面是 contains 方法的具体实现，你可以看一下。
template<ITER_TYPE iter_type>
HiObject* DictViewKlass<iter_type>::contains(HiObject* x, HiObject* y) {
assert(x->klass() == DictViewKlass<iter_type>::get_instance());
HiDict* adict = ((DictView*)x)->owner();
assert(adict->klass() == DictKlass::get_instance());
bool flag = false;
if (iter_type == ITER_KEY) {
flag = adict->map()->has_key(y);
}
else if (iter_type == ITER_VALUE) {
}
else if (iter_type == ITER_ITEM) {
}
if (flag) {
return Universe::HiTrue;
}
else {
return Universe::HiFalse;
}
}
参数 x 是一个视图对象，它本身不存储任何数据。对 x 的访问，最终都会转移到它所对应的字典数据里（第 3 至 5 行）。
实现完 contains 方法以后，这部分所有的测试用例就可以全部运行成功了。这也意味着，字典视图的基本结构我们已经搭建完成了。视图不仅具备了迭代器的功能，也同时具备了集合和列表的功能。
这里我只实现了 keys 的判断，values 和 items 的实现就留给你来完成。
总结
这节课我们实现了字典这种关联式数据结构。列表和字典是 Python 语言中最重要的两个数据结构，对它们进行增删查改也是最基本的操作。
在列表的基础上，实现字典是比较容易的，这节课我们只用了很少的篇幅就讲解了如何实现字典的增删查改操作。
字典功能变化最大的是遍历。Python 3.8 引入了视图的概念来实现字典的遍历。视图是非常重要的一个概念，它的主要作用是在数据不变的情况下，为数据操作提供了一种代理，而代理可以灵活地根据使用者场景在迭代器和集合、列表之间切换。
思考题
这节课我们讲的 dict view 的概念是软件领域非常常用的一种优化手段，除此之外你还知道哪些 view？欢迎你把你了解的view分享到评论区，我们一起讨论，如果你觉得这节课的内容对你有帮助的话，也欢迎你分享给其他朋友，我们下节课再见！
- 有风 👍（0） 💬（0）
老师，这里的实现字典，打印出来都是反着的？在构建dict的时候把数据存反了。
2025-01-06 - ifelse 👍（0） 💬（0）
关系数据库里的表和视图的关系
2024-10-30