高效实现技能表处理：从数据结构到并发优化

4次阅读

没有评论

共计 1670 个字符，预计需要花费 5 分钟才能阅读完成。

在游戏开发中，技能系统往往是核心模块之一。随着游戏规模的扩大，技能表可能包含成千上万个条目，每个条目又包含复杂的属性和效果描述。这种大规模数据处理常常面临以下挑战：

内存占用高：传统的数组或列表存储方式会导致内存浪费，尤其是在技能表中存在大量相似或重复数据时
查询效率低：线性查找或简单哈希实现难以应对高频的技能触发场景
并发竞争：多线程环境下，技能表的读取和更新操作可能引发竞态条件

在处理技能表时，数据结构的选择至关重要。以下是几种常见方案的对比：

数组 / 列表：
优点：实现简单，内存连续，遍历速度快
缺点：插入删除效率低(O(n))，查找需要线性时间
哈希表：
优点：O(1)时间复杂度的查找和插入
缺点：内存开销大，哈希冲突可能影响性能
跳表：
优点：有序结构，查找效率接近 O(log n)
缺点：实现复杂，内存占用较高
混合结构：
结合哈希表的快速查找和数组的内存效率
适合大多数游戏技能系统的需求

我们采用分层的混合数据结构：

主索引层：使用开放寻址法的哈希表存储技能 ID 到数据位置的映射
数据存储层：连续内存区块存储实际技能数据，减少内存碎片
版本控制层：为每个技能条目添加版本号，支持乐观并发控制

// 技能条目结构
struct SkillEntry {
    uint32_t id;
    uint16_t version;
    // 其他技能属性...
};

// 技能表主类
class SkillTable {
private:
    std::vector<SkillEntry> m_data;      // 连续存储
    std::vector<uint32_t> m_index;       // 哈希索引
    std::mutex m_updateMutex;            // 更新锁

public:
    // 获取技能（线程安全）const SkillEntry* GetSkill(uint32_t id) {uint32_t pos = Hash(id) % m_index.size();
        while (m_index[pos] != 0) {if (m_data[m_index[pos]-1].id == id) {return &m_data[m_index[pos]-1];
            }
            pos = (pos + 1) % m_index.size();}
        return nullptr;
    }

    // 更新技能（带版本控制）bool UpdateSkill(const SkillEntry& entry) {std::lock_guard<std::mutex> lock(m_updateMutex);

        auto* existing = GetSkill(entry.id);
        if (!existing || existing->version != entry.version) {return false; // 版本冲突}

        // 执行更新...
        return true;
    }
};