表 map

1 概述

本章节涵盖 map表的概念，表的创建、增删改查，隐式行为，底层的内存拓展机制以及指向表相关操作的文档链接。

本章节内容主要面向需要学习 GS map 表的基础概念，了解 GS 表的基础操作，了解 GS 标的底层内存拓展机制 GS 编程初学者。

在阅读完本章节后应掌握表的概念、表的使用场景、表的创建、增删改查，以及表的隐式行为及内存拓展机制，提升表的性能优化理解。

2 表的概念

GS 中的 map表是通过哈希表（Hash Table）实现的，是一种使用哈希函数将键（Key，如名字、ID）快速映射到存储位置，从而实现高效数据存储和查找的数据结构。

你可以把它想象成一个有很多抽屉的柜子，每个抽屉都有编号。存放东西时，根据东西的“名字”（键）通过一个特定规则（哈希函数）算出它应该放在哪个抽屉里。找东西时，再用同样的规则直接去那个抽屉拿，非常快。

2.1 核心概念

• 键值对存储：每个元素由键（Key）和值（Value）组成，键是唯一的标识符，值是与键关联的数据。
• 哈希函数：通过哈希函数将键转换为数组索引，实现快速访问。
• 动态扩展：表的大小可以根据需要动态调整，无需预先指定容量。

2.2 典型使用场景

• 配置管理：存储程序的配置参数，如 {"host": "localhost", "port": 8080}。
• 数据缓存：缓存频繁访问的数据，提高查询效率。
• 字典映射：实现单词翻译、ID到对象的映射等功能。
• 游戏开发：存储游戏角色的属性、物品的详细信息等。

一个简单的使用场景实例如下：

// 示例：使用 map 存储游戏角色属性
map character = {
    "name": "Knight",
    "health": 100,
    "attack": 20,
    "defense": 10
};
writeln(character);

示例2-1：表的使用场景示例

3 表的基础

3.1 表的声明

表的变量声明以 map作为类型名，未初始化时默认值为 nil。示例如下:

map m_default;          // 默认值为 nil
map m_init = {};        // 初始化为空表
writeln(m_default);     // 输出: nil
writeln(m_init);        // 输出: { }

示例3-1：表的声明

输出结果如下:

nil
{ }

3.2 表的创建

  GS 支持两种常见的表创建方式：

1. 字面量初始化：使用 {}直接定义键值对。
2. 预分配空间：使用 map.allocate方法申请指定大小的表。

示例如下：

// 字面量创建表
map m_profess = {"profess": "knight", "attack": 20};
// 预分配空间的表
map m_monsters = map.allocate(256);

writeln(m_profess);        // 输出表的键值对
writeln(m_monsters);       // 输出空表
writeln(m_profess.capacity());  // 输出实际容量
writeln(m_monsters.capacity()); // 输出实际容量

示例3-2：表的创建

输出结果如下：

{ /* sizeof() == 2 */
    "profess" : "knight",
    "attack" : 20,
}
{ }
4
512

注意：map.allocate实际分配的容量可能大于请求的大小，这是为了减少哈希冲突。例如，请求 256 时，实际容量可能是 512。

3.4 表的成员新增或修改

GS 的 map表是变长数据结构，支持动态添加和修改元素：

• 赋值语句：map[key] = value新增或修改键值对。
• set 方法：map.set(key, value)功能同上。

 如以下示例所示：

map m_equip = {"sward_id": 1, "attack": 100};
m_equip["defend"] = 50;          // 新增键值对
m_equip["attack"] = 88;          // 修改已有键的值
m_equip.set("durable", 100);     // 新增键值对
m_equip.set("durable", 88);      // 修改键值对

writeln(m_equip);

示例3-3：表成员修改或新增示例

输出的结果如下:

{ /* sizeof() == 4 */
    "sward_id" : 1,
    "attack" : 88,
    "defend" : 50,
    "durable" : 88,
}

3.5 表的拼接

GS 支持通过运算符拼接多个表：

• + 运算符：创建新表，合并键值对，重复键的值由后面的表决定。
• << 运算符：原地拼接表，重复键的处理同上。

示例如下：

map m1 = {"one": 1, "two": 2};
map m2 = {"ONE": 1, "TWO": 2, "one": "test"};
writeln(m1 + m2);   // 输出合并后的新表
m1 << m2;           // 原地拼接
writeln(m1);        // 输出拼接后的结果

示例3-4： 表的拼接示例

输出结果如下：

{ /* sizeof() == 4 */
    "one" : "test",
    "two" : 2,
    "ONE" : 1,
    "TWO" : 2,
}
{ /* sizeof() == 4 */
    "one" : "test",
    "two" : 2,
    "ONE" : 1,
    "TWO" : 2,
}

3.5 表成员的移除

GS 支持多种方法移除map 表的成员键值对:

• delete(key)：移除表中以 key 为键对应的键值对成员

• delete_value(val)：移除表中以 val 为值对应的键值对成员

• clear()：清除表中所有的键值对成员

• clean_up()：清除表中所有值为 nil 的键值对成员

示例如下:

map m = {"one": 1, "two": 2, "TWO": 2, "nil": nil};
m.delete("two");            // 移除键为 "two" 的条目
m.delete_value(2);          // 移除所有值为 2 的条目
m.clean_up();               // 移除值为 nil 的条目
m.clear();                  // 清空表

示例3-5：移除表成员示例

3.6 表成员的查询

GS 支持多个表成员查询方法：

• get(key)：获取键对应的值，键不存在时返回 nil。
• contains_key(key)：检查键是否存在。
• keys() / values()：返回所有键或值的数组。

map m = {"name": "Knight", "attack": 20};
writeln(m.get("name"));           // 输出: Knight
writeln(m.contains_key("health")); // 输出: false
writeln(m.keys());                // 输出: ["name", "attack"]

示例3-6：表成员的查询

3.7 表的遍历

使用 for(key, val:map)循环遍历表的键值对：

map m = {"a": 1, "b": 2, "c": 3};
mixed key;
mixed val;
for(key, val: m) 
{
    writeln(key, ": ", val);
}

示例3-7：表的遍历示例

4 陷阱与调试

4.1 拓展消耗

当表的大小超过当前容量时，GS 会自动扩容（通常扩容为原容量的 2 倍），并重新哈希所有键值对。频繁扩容会对性能有影响，极端性能场景建议在初始化时预估大小。

// 性能对比示例
map small_map = {};                    // 初始容量较小
map preallocated_map = map.allocate(500000);  // 预分配足够容量

// 添加大量元素时，small_map 会多次扩容，性能差一些
int start_time = time.time_ms();
for(int i = 0 upto 500000)
{
    small_map[i] = i;
}
int end_time = time.time_ms();
printf("Small map extend cost time %d ms\n", end_time - start_time);

// preallocated_map 不需要扩容，性能更好
start_time = time.time_ms();
for(int i = 0 upto 500000)
{
    preallocated_map[i] = i;
}
end_time = time.time_ms();
printf("Preallocated map set cost time %d ms\n", end_time - start_time);

示例4-1：表的内存拓展示例

• 如果能预估表的最大大小，使用 map.allocate 预分配空间
• 批量操作前考虑预分配，减少扩容次数
• 监控表的 capacity() 和 sizeof() 比例，避免过度预分配

4.2 手动缩表

之前的章节我们了解到，GS 的表再容量不足够时会自动扩容，但却不会自动缩表。当表的容量远大于表中存储的键值对数量时，需要调用shrink函数手动缩表。

map.shrink(int size = -1)：函数可指定目标缩减大小，无参数则自动缩减至一个合适的大小。容量最小缩减至32。示例如下：

// 表的有序型示例
map small_map = {}; 
printlnf("Init map capacity is %d", small_map.capacity());
for(int i = 0; i < 64; i++)
{
    // 添加键值对，扩展表大小
    small_map[i] = i;
}
printlnf("After extend map capacity is %d", small_map.capacity());
for(int i = 0; i < 64; i++)
{
    // 移除所有键值对
    small_map.delete(i);
}
printlnf("After delete all key-value pair map capacity is %d", small_map.capacity());
small_map.shrink(); // 手动缩表，缩表最小将容量缩减至 32
printlnf("After shrink capacity is %d", small_map.capacity());

5 进阶内容

5.1 拓展机制

当表中的键值对数量超过容量的3/4时，为了避免哈希冲突对表的性能影响，GS 表会自动将容量扩展为原本容量的两倍，并重哈希所有键值对。

示例如下：

// 内存拓展机制示例
map small_map = map.allocate(12); // 创建一个初始容量为16的map表，能够容纳(12 * 4 / 3)空间的2的次方数 -> 16
writeln("Init map capacity is:", small_map.capacity());
// 16 * 3 / 4 = 12
for(int i = 0; i < 12; i++)
{
    small_map[i] = i;
}

// 键值对数量小于等于 12, map 不会扩展
writeln("After set 12 key-value pair, map capacity is: ", small_map.capacity());

// 添加第13个键值对
small_map[13] = 13;

// 键值对数量大于 12, map 扩展
writeln("After set 13's key-value pair, map capacity is: ", small_map.capacity());

示例5-1：内存拓展机制示例

5.2 类型问题

GS 在操作表时会自动进行类型检查工作

• 表中取出内容时与接收类型不匹配时会报错。
• 表中存储的数据的子类型不同时，会以先入表的数据的子类型为准：

示例如下：

enum NUM
{
    ONE= 1,
};
map m = {1:1, 2:2};
map m1 = {NUM.ONE:1};
try
{
    // 尝试使用错误的类型接收表的取出数据
    string str = m[1];
    writeln("We got error type val: ", str);
}
catch
{
    printlnf(HIR"Got type check failed"NOR);
}
// 尽管存储的为枚举，整型做key也可正常存取对应val
writeln(HIG, "Get value by int key result: ", m1[1], NOR);
// 输出m1表的第一个键
writeln("m1 key one is %O", m1.keys()[0]);

示例5-2：部分表类型检查

运行实例可以看到表的类型检查报错。以及表中存储为枚举的值1时，使用整型1也可以正确的存取数据，此时键的数据类型由先进入表的数据类型决定。

5.3 表的有序性及破坏

当前的map表不保证键值对的顺序。尽管在不调用map的删除操作的情况下map表的键值对顺序始终是不变的，但整体上不建议利用表的有序性特定。

// 表的有序型示例
map small_map = {}; 
for(int i = 0; i < 4; i++)
{
    small_map[i] = i;
}
// 遍历表，发现键值对保留的插入的顺序
for(int key, int val: small_map)
{
    printlnf("key %O val %O", key, val);
}

printf("----Afet key '1' is deleted------\n");
small_map.delete(1);
// 遍历表，发现表的有序性被破坏
for(int key, int val: small_map)
{
    printlnf("key %O val %O", key, val);
}

示例5-3：表的有序性及破坏示例

实际在底层实现中，在删除一个键值对时，最后一个键值对被直接转移到被删除的键值对上并修改对应hash。这样避免了额外的拷贝操作(性能好)但代价时破坏了表的有序性。

6 扩展阅读

更多表相关的内容请参阅如下文档：

• 表的手册
• 表的外部函数

7 总结

本章系统介绍了 GS 中 map表的核心概念和完整使用方法。通过理论学习与丰富的代码示例，读者可以掌握表的创建、增删改查、遍历等基础操作，并深入理解其底层哈希表实现机制。关键要点包括：表的动态扩容特性（当容量使用率达75%时自动翻倍扩容）、性能优化技巧（使用 map.allocate预分配空间避免频繁扩容）、以及实际应用中的注意事项（如类型安全、有序性不保证等）。

map作为 GS 中重要的键值对数据结构，在配置管理、数据缓存、游戏开发等场景中具有广泛应用价值。建议开发者在实际使用中结合业务需求合理预分配空间，对不确定的键查询使用安全的 get方法，并在适当时候使用 shrink进行内存回收。掌握这些知识将显著提升代码的效率和健壮性，为后续复杂应用开发奠定坚实基础。