我有一个很大的元素列表（数千万） . 我试图计算这些元素的几个子集的出现次数 . 事件分布是长尾的 .
数据结构目前看起来像这样（在OCaml-ish风格）：
type element_key
type element_aggr_key
type raw_data = element_key list
type element_stat =
{
occurrence : (element_key, int) Hashtbl.t;
}
type stat =
{
element_stat_hashtable : (element_aggr_key, element_stat) Hashtbl.t;
}
Element_stat当前使用哈希表，其中键是每个元素，值是整数 . 但是，这是低效的，因为当许多元素只出现一次时，出现的哈希表会多次调整大小 . 我无法避免通过设置较大的初始大小来调整发生哈希表的大小，因为实际上有很多element_stat实例（stat中的哈希表的大小很大） .
我想知道这个用例是否有更高效（内存方式和/或插入方式）的数据结构 . 我发现了很多现有的数据结构，比如trie，radix tree，Judy array . 但我很难理解他们的差异以及他们是否适合我的问题 .
1 回答
你在这里有一个表
element_aggr_key映射到表，然后将element_key映射到int. 出于所有实际目的，这相当于将element_aggr_key * element_key映射到int的单个表，因此您可以这样做：然后你有一个哈希表，你可以给它一个巨大的初始大小 .