前缀树（Trie）为何采用数组而非unordered_map？后者存在哪些劣势？

首先给出常见的前缀树数组实现结构体：

struct trie{
    int count;
    trie* next[26];
};

虽然用unordered_map<char, trie*>作为next字段能按需分配空间且实现可行，但主流方案仍选择数组，核心原因在于unordered_map存在以下明显劣势：

• 访问性能差距大：数组通过字符索引（如c - 'a'）直接定位子节点，是O(1)的常数时间访问，且数组内存连续，缓存命中率高。而unordered_map基于哈希表实现，需要先计算字符的哈希值，还要处理哈希冲突（比如链地址法下遍历链表），实际访问开销远高于数组，在高频操作的场景下，性能差距会被显著放大。

• 实际内存开销未必更小：看似unordered_map是按需分配，但哈希表本身有额外结构开销——每个键值对要存储字符、指针，还有哈希表的桶结构、链表节点的额外指针。以64位系统为例，数组的26个指针仅占208字节，对于多数场景，这个固定开销比哈希表的零散开销更划算；如果前缀树节点的平均分支数接近26，unordered_map的内存浪费反而更严重。

• 实现与维护更复杂：数组实现的逻辑极简，初始化、插入、查询都直接通过索引操作，无需处理哈希函数、冲突解决等细节，代码简洁易读，不容易出错。而unordered_map需要处理字符到键的映射，还要考虑哈希函数的适配（虽然默认char哈希没问题，但扩展字符集时需调整），代码相对繁琐，维护成本更高。

• 性能稳定性差：数组实现针对固定小字符集（如小写英文字母）的行为完全确定，不存在性能波动。而unordered_map的性能依赖于哈希分布，极端情况下（比如恶意构造的哈希冲突），访问时间会退化到O(n)，无法保证稳定的性能表现。

内容的提问来源于stack exchange，提问作者유정현