java - 存储百万长度的百万键，哪个更好红黑树或基数树？

Question

我想存储多个百万长度的键（字符串）及其关联的对象。这样我必须非常频繁地插入数据结构（rbtree 或基数树），并且与插入相比必须搜索相当少的时间。任何建议将不胜感激。谢谢你。

Answer 1

由于插入是您最关心的问题，因此您应该使用红黑树，因为它的插入时间复杂度与输入大小成对数，即O(k*log n)以log2 为底的对数，k是每个输入的大小或长度，n是输入的数量. 基数树的插入在k每个输入的大小和输入的数量n上是线性的，也就是说O(k*n)，这比红黑树差，除非许多字符串键共享足够长的前缀以便n在子-的对数表达式n。