java - 需要一个 Java TreeMap 的快速替代品，它可以在不降低速度的情况下容纳许多映射

Question

我正在编写一个使用 TreeMap 的 Java 程序，一旦有成千上万的整数、字符映射，性能就会降低到爬行速度。

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

我目前正在关注 Trove。我还查看了使用插入排序但不包括头函数和尾函数的链表的实现。不过，我认为带有插入排序的链表会比树慢，不是吗？

Answer 1

如果您正在寻找类似 TreeMap<Integer,Character> 的替代品如果您的整数键很密集，那么数组将是最有效的。但它会是一个 char[]而不是 int[]因为你想查找 char取决于 int - key 。然后我读了一些关于“基因组”的东西？!假设您想使用 char代表 Adenin、Guanin、Cytosin 和 Thymin(我不是这方面的专家)请记住 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 value 你只需要 2 位来表示四个值，即一个可以存储你的序列，每个字节有四个值，最终需要大约 6.5 MB。但是对于这样的事情你需要做一些小 Action ......