我需要一个快速的替代Java TreeMap<Integer的Character>，它可以容纳许多映射而不会变慢

Question

我正在编写一个使用TreeMap的Java程序，一旦有10个数以千计的整数和字符映射，性能就会下降到爬行。

我想知道是否有某种类型的排序集实现可以使用int和char原语，并且具有类似于"headMap“和"tailMap”函数。

我目前正在关注的是Trove。我还研究了一个链表的实现，该链表使用插入排序，但不包括head和tail函数。不过，我认为带有插入排序的链表会比树慢，不是吗？

Answer 1

如果你正在寻找像TreeMap<Integer,Character>这样的东西的替代品，如果你的整数键是密集的，那么数组将是最有效的。但它应该是char[]而不是int[]，因为您希望根据int-key查找char。然后我读到了一些关于‘基因组’的东西？！假设你想用char来表示腺苷、鸟嘌呤、细胞分裂素和胸腺嘧啶(我不是这方面的专家)，记住char会占用你16位--远远超过你对四种不同东西的需求。也许你可以使用像这样的术语

...
public static final byte UNDEF = (byte)-1;
public static final byte ADENIN = 0;
public static final byte GUANIN = 1;
public static final byte CYTOSIN = 2;
public static final byte THYMIN = 3;
...
private byte[] genome = new byte[ 26000000 ]; // or which size ever
...

如果这仍然消耗了太多的内存，这将变得棘手:假设你不需要UNDEF的值，你只需要2位来存储这四个值，也就是说，一个人可以存储你的序列，每个字节有四个值，最终需要大约6.5MB。但是对于这样的事情，你需要做一些小调整...

Answer 2

如果我理解了这个问题，您想要一个保留键顺序的数据结构，也就是说，字符在个体的引用序列中替换字符的位置。

我假设您通过增加位置顺序来处理项目。

现在，由于TreeMap实现的是Red-Black Tree，所以对于基本操作，它具有对数复杂度。

如果只需要按顺序迭代序列，那么每次插入都会对性能造成严重影响。

如果我的假设是正确的，，我会说你可以使用LinkedHashMap。

正如javadoc所解释的那样：

此实现使其客户端免受HashMap (和哈希表)提供的未指定的、通常是混乱的排序，而不会导致与TreeMap相关的成本增加。

这意味着您可以按输入元素的相同顺序迭代元素，但基本操作的复杂性与普通HashMap相同，并且由于链表处理而对性能造成了影响。

您可以将其想象为一个由双向链表遍历的HashMap，该双向链表按照键的插入顺序连接这些键。

请注意，我不是在解决你的序列是否适合内存的问题。此外，请注意，与简单的HashMap相比，LinkedHashMap将占用更多的内存。

Answer 3

如果你只是想要一个更快的地图实现，你有没有考虑过HashMap？它仍然使用对象，但如果最初创建时(请参阅前面链接中的第三种形式的构造函数)具有足够大的容量，这将允许比TreeMap更快地访问数据。

或者，如果您只对地图中类似排序集的行为感兴趣，则可以使用TreeSet获得更好的性能。

至于Trove，我不熟悉它，但我怀疑你可以从Java提供的类中获得显着的性能增强，而不是求助于第三方库，只需花一点额外的精力来检查你的数据结构中需要什么，以及他们在提供你不需要的功能时浪费了哪些额外的工作。