适合URI存储的比普通Set更优的空间高效可序列化查找数据结构咨询

针对你存储大量带公共片段URI的场景，以下几种数据结构完全满足你提出的5项特性，表现远优于普通HashSet：

• 压缩前缀树（Radix Tree / 基数树）
  针对有大量公共前缀的字符串场景优化，会自动合并重复的公共前缀片段，你的场景下内存占用仅为普通HashSet的1/5到1/10。contains查询和add操作的时间复杂度均为O(k)，k为URI的长度，实际使用时和普通HashSet的O(1)性能差异极小。序列化时仅需存储树结构，无需重复保存公共前缀，序列化/反序列化效率极高，成员判定100%精确。
  主流语言均有成熟生产级实现，比如Java的org.apache.commons.collections4.trie.PatriciaTrie、Go的github.com/armon/go-radix、Python的radix三方库。
• 有限状态转换器（FST，Finite State Transducer）
  适合集合写入后极少更新的静态场景，内存压缩率比Radix Tree更高，相同数据量下内存占用仅为Radix Tree的1/2到2/3。查询速度接近普通HashSet，本身的存储结构天生支持高效序列化/反序列化，无需额外转换即可直接持久化，成员判定完全精确。
  最知名的实现是Lucene核心包内置的FST组件，其他语言均有成熟的移植版本。
• 字符串字典映射 + Roaring Bitmap 组合方案
  先将所有URI的公共前缀抽入统一字典，将不同的URI后缀映射为连续的唯一整数ID，用Roaring Bitmap存储这些ID。contains查询和add操作均为O(1)，性能和普通HashSet完全持平，Roaring Bitmap本身的内存效率极高，100万条数据的内存占用仅为几MB，序列化后体积也极小，成员判定100%精确。
  适合可以接受提前做URI到整数ID映射的场景，几乎所有主流语言都有Roaring Bitmap的成熟实现。

• 如果你需要频繁向集合中新增元素，优先选择压缩前缀树（Radix Tree），适配性最高
• 如果你的集合是批量写入后基本不会修改的静态数据，优先选择FST，内存效率和查询性能都是最优的
• 如果你可以提前完成URI到整数ID的映射，优先选择字符串字典映射 + Roaring Bitmap 方案，性能和内存表现都可以做到最优

内容的提问来源于stack exchange，提问作者Kasper Zutterman