我正在编写一个使用TreeMap的Java程序，一旦有成千上万个整数字符映射，性能就会减慢到爬行。
我想知道是否有某种类型的排序集实现，可以使用int和char原语，并具有类似"headMap"one_answers"tailMap"的功能。
我正在看Trove目前。我还研究了一个链表的实现，它使用插入排序，但不包括头和尾函数。我觉得用插入排序的链表会比树排序慢，不是吗?
如果你正在寻找TreeMap<Integer,Character>的替代品，如果你的整数键是密集的，那么数组将是最有效的。但是它应该是char[]而不是int[]因为你想根据int键来查找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.5 MB。但是对于这样的事情，你需要做一些位摆弄……
如果我理解了这个问题，您需要一个保留键的顺序的数据结构，即替换单个字符在引用序列中的位置的字符。
我假设您是按位置递增顺序处理项目的。
现在，由于TreeMap正在实现红黑树，它的基本操作具有对数复杂度。
如果您只需要按顺序迭代序列，那么每次插入都会对性能造成严重影响。
如果我的假设是正确的，我想说你可以使用LinkedHashMap。
javadoc解释:
该实现通常使其客户端免于未指定的操作由HashMap(和Hashtable)提供的混乱排序，没有导致与TreeMap相关的成本增加。
意味着可以按照输入元素的顺序迭代元素，但基本操作与普通HashMap具有相同的复杂性，并且由于链表处理而影响性能。
你可以把它想象成一个由双链表遍历的HashMap，按键的插入顺序连接键。
请注意，我没有解决你的序列是否适合内存的事实。另外，要注意LinkedHashMap将比简单的HashMap占用更多内存。
如果您只是想要一个更快的Map实现，您考虑过HashMap吗?这仍然使用对象，但如果最初创建了足够大的容量(参见前面链接中构造函数的第三种形式)，这将允许比TreeMap更快地访问数据。
或者，如果您只对映射中的sortedset类行为感兴趣，那么使用TreeSet可能会获得更好的性能。
至于Trove，我不熟悉它，但我怀疑你可以从Java提供的类中获得显著的性能增强，而不是求助于第三方库，只需要花费一点额外的精力来检查你需要从数据结构中得到什么，以及他们提供了你不需要的功能，浪费了哪些额外的工作。
正如Steve所写的，使用分析器检查TreeMap是否是罪魁祸首可能是值得的。
其他选项包括:
-
使用
HashMap和大initialCapacity -
如果你的键集是密集的，那么你可以使用
int[]。那将是最快的。
您看过PriorityQueue了吗?
要保存大量的元素，你最好使用B-Tree。这种结构在数据库中广泛用于保存索引。例如Oracle和MySQL，如果我没弄错的话。看看JDBM3。还应该存在其他实现
如果您知道这是您的性能瓶颈和/或内存问题-那么我会考虑使用trove TIntCharHashMap。在过去，我已经成功地使用了宝库映射来提高性能并减少内存消耗。
请注意，键不会被排序，但您可以非常便宜地获得键的int[]，然后可以对其进行排序。因此，如果您只是偶尔需要排序遍历，则可以根据需要对它们进行排序。
如果你发现这很难看(或妨碍性能)，你可以将TIntCharHashMap和排序的int[]包装到你自己的排序映射中——你只需要自己维护不变量。
我发现trove没有直接基于树的顺序维护map/set类有点不幸，但我很感谢它提供的工具。
处理非常大的排序映射的一种技术是使用SortedSet组合来按排序顺序管理键，使用Map组合来管理实际的键到值映射。通过这种方式，您可以使用headSet()和tailSet()对键进行快速迭代，然后使用从集合返回的键来查找实际的映射。
我没有证据证明为什么这个工作，但根据我的经验，它是非常大的排序地图快10倍。
值得尝试Max Bolingbroke的B-Tree式解决方案