如何使用LinkedHashMap获取子图？
目前，我正在使用TreeMap来存储一些x和y坐标，但与ArrayList或HashMap相比，迭代速度非常慢。 我正在使用它，因为我需要subMap()方法，因此即使精确的X值（键）不存在，我也可以在确定的范围内获得X值。
LinkedHashMap与HashMap速度几乎相同，我可以按照插入顺序迭代键（我需要插入顺序或比较顺序，因为它在TreeMap中完成）但我没有submap()方法。 在TreeMap中，我可以非常快速地生成子图。
是否存在任何数据结构或某种方式来存储有序值（通过插入顺序或比较器）比TreeMap更快，即使精确值不在地图中，也允许获取范围内的子图？ 我的意思是，也许我想要2到25之间的值，但2不存在，最近的是3，所以它将从3到25返回一个子图。或者某种方式将此function添加到LinkedHashMap ？
听起来你需要一个TreeMap，它的迭代速度并不比LinkedHashMap慢得多，并且可以满足您的需求。 由于HashMap是无序的，因此subMap没有意义。
今天我终于得到了我的问题的答案。 经过一些测试HashMap ， LinkedHashMap和TreeMap比ArrayList慢，我想只使用它们来创建subMaps() 。 所以我创建了一个扩展ArrayList的新类，它给了我一个非常好的性能，在这个答案的帮助下，我创建了快速获取子列表而不是索引的方法。 这是完整的课程：
/** * The purpose of this class is to be a faster replacement to a {@link java.util.TreeMap} with * the ability to get sublist containing a range of x values. ArrayList access time is O(1) while * {@link java.util.TreeMap} is O(log(n)). When large data is handled the impact on performance is * noticeable. */ public class XYDataset extends ArrayList { private final float COMPARISON_THRESHOLD = 0.01f; final Comparator comparator = new Comparator () { @Override public int compare(PointValue lhs, PointValue rhs) { if (Math.abs(lhs.getX() - rhs.getX()) < COMPARISON_THRESHOLD) return 0; return lhs.getX() < rhs.getX() ? -1 : 1; } }; public XYDataset(int capacity) { super(capacity); } public XYDataset() { } public XYDataset(Collection collection) { super(collection); } @Override public List subList(int start, int end) { return super.subList(start, end); } /** * Generate a sublist containing the range of x values passed * @param x1 lower x value * @param x2 upper x value * @return sublist containing x values from x1 to x2 */ public List subList(float x1, float x2){ /** * Collections.binarySearch() returns the index of the search key, if it is contained in the list; * otherwise it returns (-(insertion point) - 1). * The insertion point is defined as the point at which the key would be inserted into the list: * the index of the first element greater than the key, or list.size() if all elements in the list * are less than the specified key. Note that this guarantees that the return value will be >= 0 if * and only if the key is found. */ int n1 = Collections.binarySearch(this, new PointValue(x1, 0), comparator); int n2 = Collections.binarySearch(this, new PointValue(x2, 0), comparator); /** * Example, we assume the list is sorted. Based on (https://stackoverflow.com/questions/19198586/search-sorted-listlong-for-closest-and-less-than) * * long X = 500; * List foo = new Arraylist<>(); * foo.add(450L); * foo.add(451L); * foo.add(499L); * foo.add(501L); * foo.add(550L); * * If we search for something that isn't in the list you can work backward from the return value * to the index you want. If you search for 500 in your example list, the algorithm would return (-3 - 1) = -4. * Thus, you can add 1 to get back to the insertion point (-3), and then multiply by -1 and subtract 1 to get * the index BEFORE the first element GREATER than the one you searched for, which will either be an index that * meets your 2 criteria OR -1 if all elements in the list are greater than the one you searched for. */ if(n1 < 0) n1 = -n1-1; if(n2 < 0) n2 = -n2-1; return this.subList(n1, n2); } }
PointValue只是一个包含x和y坐标的类。 所以现在我只是调用subList()传递我想要的x坐标范围。 在我的情况下，插入顺序也是排序的，这对于使用Collections.binarySearch()很重要