我今天写了一本关于大学中与Java中数据结构的实现有关的类(class)的试卷。最后一个问题是按照以下思路:
解释为什么使用TreeMap 来存储具有整数系数的多项式是很方便的，尤其是当多项式应该以标准形式打印为String时尤其如此。
我意识到这是一个错误，因此继续解释为什么我认为这不是一个好主意。相反，我主张使用简单的int []数组，因为数组具有O(1)随机访问，双向O(n)迭代且指针(引用)没有额外的内存占用。
假设我错了，使用(分类的)TreeMap有一些好处，有人可以向我解释这些好处吗？我之所以这样说是因为Matlab，Octave，Maple和其他经过良好测试的数值程序都使用数组来存储多项式，所以这不可能全都是错的。
最佳答案
我认为最引人注目的示例是x^10000 + 3x^2 + 2之类的东西。您要制作一个new int[10000]而不是TreeMap中的3个节点？ :-)
当然，可以对它进行排序，以便更轻松地构造和操纵多项式。
而且您确定数值程序会为此使用数组吗？如果您认为情况如此，那么我希望看到对其内部实现的引用。
至于内存占用问题，java.util.TreeMap的标准实现将产生7个额外的引用和原语，其中一个内部有一个引用，另一个内部有7个引用。因此，您正在为此寻找15个其他引用。每个条目将具有5个引用和一个原语，因此，数组的大小为15 + 6 * n，而不是2 + 1 * n。 因此，只要您有(14 + 5 * n)个空多项式，使用TreeMap就会比使用数组少占用内存。
最小的示例是x^20，它将具有21个数组元素和1个数组引用，总共22个单词，而TreeMap只有21个单词。
可以想象，我在实现中缺少引用，但是我对它进行了很好的介绍。
关于java - 在TreeMaps中存储多项式-为什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8508521/