使用映射 (mapping)					1992 September 28

MudOS 映射资料型态文件 -  撰稿: Truilkan@TMI

MudOS 0.9 提供了名为「映射」的资料型态. 映射与其他语言中的联结阵列
(associative arrays)  一样 (例如 Perl). 一个联结阵列与普通的阵列类似, 但
是联结阵列可以使用任何资料型态 (字串、物件、整数、阵列等等) 作为索引
(index) , 而阵列只能使用整数. 另外, 联结阵列是疏松的阵列 (sparse arrays)
, 也就是说, 您可以只指定第 1,000,000  项元素的内容, 而不必指定其他元素.
映射有两个实际的用途:
1)  资料库
2)  代替 C  的集合资料型态 struct. 只需要把映射中的关键字 (key) 当作
struct  的栏位 (field)  即可.

这样宣告一个映射:

mapping x;

一个映射可以用两种方法初始化 (initialize):

   x = ([关键字一 : 内容值一, 关键字二 : 内容值二, ...]);

   (注意: x = ([]); 可以造出一个空的映射)

请注意一个映射必须先初始化, 才能指定其中的任何元素. 有此限制是因为游戏驱
动程式将所有的变数初始化为 0 (不管变数是什麽型态).  如果您没有初始化一个
映射, 您为此阵列指定元素时, 就会看到 Indexing on illegal type  (索引指向
的资料型态违法) 的错误.

新的 (关键字, 内容值) 可以用以下的方法加进一个映射:

x[key] = value;

上面的叙述使驱动程式寻找在映射 x  中的特定关键字 (key). 如果映射 x  有此
关键字, 则映射中联结的内容值 (value)  就换成等号右边指定的值. 如果映射并
没有包括这个关键字, 则会自动动态 (dynamically) 配置 (allocate)  另外的空
间, 并将新的 (关键字, 内容值) 插入映射中.

映射中的一个元素可以下行的方式读取:

   write(x[key] + "\n");

一个阵列的元素可以下行的方式删除:

   map_delete(x, key);

删除之後, 会让下面的运算式为真 (1):

   undefinedp(x[key])

所以您可以撰写像以下的程式码:

if (undefinedp(value = x["MudOS"])) {
    write("「MudOS」为映射 x 的一个元素。\n");
} else {
    write("关键值「MudOS」的值是：" + value + "。\n");
}

关键字 (索引) 的列表可以用 keys() 超越函式列出, 举例如下:

   mixed *idx;
   map x;

   x = ([ "x" : 3, "y" : 4]);
   idx = keys(x);  /* idx == ({"x", "y"}) 或 ({"y", "x"}) */

请注意, 看来很明显的, keys()  会以一个随机的顺序 (random) 传回索引的列表
 (这种随机的顺序, 是映射储存资料的方式的副作用 ---- 在此, 是因为可扩充式
资料搜寻表 (extensible hash table)  顺序的关系)

一个映射的内容值 (values) 列表, 可以 values() 超越函式列出:

   idx = values(x);

使 idx 等於 ({3, 4}) 或 ({4, 3}). 注意, values() 传回的内容值顺序则跟
keys() 传回的顺序相同.

 (关键字, 内容值) 在一个映射中, 可以利用 each()  超越函式反覆搜寻.
each()  在找到映射的尾端时, 就传回一个空向量 (null vector).  each() 传回
 (关键字, 内容值) 的顺序, 与 keys() 和 values()  传回的顺序相同. 举例:

   mixed *pair;

   while ((pair = each(x)) != ({})) {
      write("key   = " + pair[0] + "\n");
      write("value = " + pair[1] + "\n");
   }

映射可以为二元 (two-dimensional) (或是更高次元的映射),  道理与 LPC  阵列
相同:

   mapping x, y;

   x = ([]);
   y = ([]);

   y["a"] = "c";
   x["b"] = y;

   则 x["b"]["a"]  == "c"

   映射也可以由 *  (乘法) 运算子组合得到 (数学上的组合).

   mapping r1, r2, a;

   r1 = ([]);
   r2 = ([]);

   r1["driver"] = "mudlib";
   r2["mudlib"] = "castle";

所以:

   a = r1 * r2 

定义出 a["driver"] == "castle";

您也可以将两个映射相加. 两个映射的总和定义为两个映射的联集 (union).

   a = r1 + r2

定义出 a["driver"] == "mudlib" 和 a["mudlib"] == "castle"

「+=」也可使用. 所以您可以用:

   a += ([key : value]);

可以代替:

   a[key] = value;

不过, 後面这种 a[key] = value 的形式要比前面的 a += ([key : value]) 的方
法要来得有效率. 因为前面的方法还要创造一个新的映射［译按: 指 
([key : value]) 这个映射］, 而後者不用.

映射不能使用 - (减号) 运算子［要使用 map_delete() ］.

sizeof() 超越函式可以判断一个映射中有多少对 (关键字, 内容值)  的资料.

   write("映射 x 内含 " + sizeof(x) + " 个元素。\n");

内部的做法 (implementation):

MudOS 的映射使用可扩充式的资料搜寻表 (extensible hash table). 资料搜寻表
的大小一定是 2  的乘幂 (power of 2).  当资料搜寻表的内容装满一定的程度时
, 资料搜寻表的就增为两倍以维持资料搜寻的效率.

作者:

MudOS 的映射原本由 Whiplash@TMI 所写. 其中的一部份後来由 Truilkan@TMI 重
写［使用可扩充式的资料搜寻表以替换原来的二元树 (binary tree)］.

映射资料结构的一部份是基於 Larry Wall 写的 Perl 程式语言的 hash.c 模组.
Perl  的整套程式适用於 GNU Copyleft general public license.

翻译:	Spock @ FF	97.Aug.11.
