英文:
Java data structure for an arbitrary large number of elements and larger than Integer.MAX_VALUE
问题
有没有一种Java数据结构可以存储任意大数量的元素？
假设这些元素也都是BigIntegers，为了简单起见。
从理论上讲，使用带有BigInteger索引的数组是可以的，因为设置和获取值将是唯一需要的操作。
但是数组的容量不能超过Integer.MAX_VALUE。（甚至更少，取决于虚拟机，参见这个问题）。
为了实现这样的数据结构，一个简单（朴素）的解决方案是从LinkedList创建一个，并使用外部的BigInteger计数器。
类似这样：
class MyArray{
private final BigInteger size;
private final LinkedList<BigInteger> list;
MyArray(BigInteger size){
//为简单起见省略了
}
public BigInteger get(BigInteger index){
//为简单起见省略了
//使用BigInteger计数器遍历LinkedList并获取元素
}
public void set(BigInteger index,BigInteger element){
//为简单起见省略了
//使用BigInteger计数器遍历LinkedList并设置元素
}
public BigInteger getSize(){
return size;
}
}
然而，有可能进行多种优化。
例如，不初始化未设置或获取的元素，或者缓存经常请求的元素。在这种情况下，Map<BigInteger,BigInteger>的实现也可以是一个很好的选择。然而，映射返回int类型的大小，我无法找到有关映射是否能处理超过Integer.MAX_VALUE的参考资料。我搜索了TreeMap和HashMap。
是否有这样一个可用的任意大小的数据结构呢？
其他一些限制条件。
1 - 内存大小不被视为约束，但节省内存会是一个加分项。
2 - 数据结构最好存储在内存中，因此不考虑基于数据库的解决方案。例如，上述问题也可以通过将值保存在数据库中，其中元素的索引被转换为字符串并用作字符串键来实现。
英文:
Is there a java data-structure that can store an arbitrary large number of elements?
Let's suppose that the elements are also BigIntegers for simplicity.
Theoretically using an array with a BigInteger index would be OK since setting and getting values will be the only operations required.
But an array cannot contain more than Integer.MAX_VALUE.(Or even less depending on the VM dependent, see this question).
To implement such a data structure a simple (naive) solution would be to create one from a LinkedList and have an external BigInteger counter.
Something like that:
class MyArray{
private final BigInteger size;
private final LinkedList<BigInteger> list;
MyArray(BigInteger size){
//ommited for simplicity
}
public BigInteger get(BigInteger index){
//ommited for simplicity
//traverse the LinkedList using a BigInteger counter and get the element
}
public void set(BigInteger index,BigInteger element){
//ommited for simplicity.
//traverse the LinkedList using a BigInteger counter and set the element
}
public BigInteger getSize(){
return size;
}
}
However it should be possible to make several optimizations.
For instance not initializing elements that have not been set or get, or caching frequently requested elements. In that sense a Map<BigInteger,BigInteger> implementation could also be a good implementation. However maps return an int size and I could not find a reference on whether a map can handle more than Integer.MAX_VALUE. I searched for TreeMap and HashMap.
Is there such an arbitrary size data structure available?
Some other constraints.
1 - The memory size is not considered as a constraint, however saving memory would be a plus.
2 - The data-structure would preferably be stored in memory, so databased backed solutions are not considered. For instance the above could also be implemented by saving the values in a database with the index of the element converted to a String and used as a String key.
答案1
得分: 0
问题背后的动机是寻找一种简单的解决方案，而不依赖于内存数据库。例如，当使用64位数组是一个不错的解决方案时。
内存数据库提供了更多的功能，可能并非都是必需的，也许可以避免使用。
没有任何答案，也没有找到一种易于实施和高效的解决方案，我会说使用内存数据库是最简单的方法。
可以在维基百科上找到内存数据库列表。
英文:
The motivation behind the question was to identify a simple solution without relying to an in memory database. E.g when a 64bit array would be a good solution.
An in memory database offers more features that may not be needed and perhaps can be avoided.
Without any answers, and not having found a solution that would be easy to implement and efficient myself I would say that using an in memory database is the simplest way to go.
A list of in memory databases can be found in Wikipedia.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论