如何将整数的小映射表示为数组？
假设我想构建一个小简单地图，其中键是 N 个整数（固定，通常为 1），值是 M 个整数（也是固定的，通常为 1）。
现在我想将数据存储在整数数组中，以提高空间效率。我正在 JVM 中编程，但它实际上应该没有什么区别，除非算法需要将指针存储为整数。
有没有人定义了一个可以做到这一点的简单数据结构？
[编辑] 到目前为止我得到的答案似乎表明没有人理解我的问题，所以我会尽力澄清。首先，忘掉M和N；想象一下我说的是一个 int 键和一个 int 值。 AFAIK，如果你想使用一个普通的 HashMap，其中键是整数，值是整数，那么你最终将得到至少 2 + 3 * N 对象，其中 N 是条目数。
我想知道的是，您能否将所有这些整数打包到一个原始整数数组中，将对象数量减少到两个，而与键的数量无关。一种用于 int[]，另一种用于包装对象，它为您提供一些类似地图的接口。我的键和值都不会为空。而且我也不需要完整的标准 java.util.Map 实现。我只需要获取、放置和删除、获取和返回原始整数而不是整数对象。访问不需要需要是 O(1)，就像在普通的 HashMap 中一样。
Let's say I want to build a small simple map, where the key is N integers (fixed, usually one) and the value is M integers (also fixed, usually one).
Now I would like to store the data an an integer array, for space efficiency. I am programming in the JVM, but it should not really make a difference, unless the algorithm would require storing pointers as integers.
Has anyone defined a simple data structure that can do that?
[EDIT] The answers I had so far seem to show that no one understands my question, so I'll try to clarify. Firstly, forget about the M and N; just imagine I said one int key and one int value. AFAIK, if you want to use a normal HashMap where the key is an integer and the value is an integer, then you will end up with at least 2 + 3 * N objects, where N is the number of entries.
What I want to know is, can you pack all those ints in a single array of primitive ints, reducing your object count to two, independent of the number of keys. One for the int[], and one for the wrapper object that gives you some map-like interface. Neither my keys nor my values will ever be null. And I don't need a full standard java.util.Map implementation either. I just need, get, put, and remove, taking and returning primitive ints not Integer objects. Access does not need to be O(1), like in a normal HashMap.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
据我所知，答案是否定的，至少在Java中不是。
但是您可以简单地将键和值保存在具有匹配索引的 int 数组（每个）中，并且如果保持键数组排序，则可以执行二分搜索。
Java 数组的问题在于它们是固定大小的结构，因此如果您想要存储的元素多于分配给数组的元素，则重新分配它们的成本非常高。
因此，您必须在数组的大小和重新分配的数量之间进行权衡，也许类似于 ArrayList 的做法。
另一个较小的问题是 int 是原始类型，没有 null 值，但您可以指定一个特殊的 int 值来表示 null。
As far as I know, the answer is no, at least not in Java.
But you can simply keep your keys and your values in an int array (each) with matching indexes, and if you keep the key array sorted, you can perform a binary search.
The trouble with Java arrays though is that they're fixed size structures, so if you want to store more elements than your arrays are allocated to, reallocating them is quite expensive.
So you'll have to make a trade-off between the size of the array and the number of reallocations, maybe something similar to how
ArrayListdoes it.The other, somewhat smaller problem is that int being a primitive type, there's no null value, but you can designate a special int value to denote null.
我想我理解这个问题，我会尝试一个解决方案：
实现你想要的非常简单的方法是保留一个二维数组
int array[NKeys][2]，其中 array[i][0] 是键，array[i][1] 是 M 值之一。然后，您可以迭代该数组，并针对key的每个查询，返回所有array[i][1]，使得array[i][0] ==键。当然，这适用于单个 int 键而不是一组 int 键。而且，这非常复杂。如果不添加更多 Java 对象/C 指针，我想不出任何其他方法可以做到这一点。I think I understand the problem, I'll take a shot at a solution:
The very simple way of achieving what you want is to keep a single two dimensional array
int array[NKeys][2], wherearray[i][0]is the key andarray[i][1]is one of the M values. You could, then iterate the array and for every query of akey, return allarray[i][1]such thatarray[i][0] == key. Of course, this works for a single int key rather than a set of int keys. Also, this is awful in complexity. I can't think of any other way of doing this without adding more Java objects/C pointers.由于 ArrayList（实际上是 AbstractList）类已适当重写了 equals 方法，因此您可以直接使用映射，如下所示：
Since the ArrayList(actually AbstractList) class has equals method overridden appropriately, you can directly use a map like so: