电子表格数据 - 链表还是哈希图？

Question

我正在寻找用java实现电子表格。使用单元格（列）链接列表的链接列表（行）来存储数据或哈希图（每个单元格映射到一个键，例如 A1 -> 1、A2-> 2 等）会更好吗？

或者有更好的数据结构可以使用吗？

谢谢！

Answer 1

另请查看 Guava 的表和实现类。

Answer 2

使用Map可以让您更快、更轻松地查找值。您不需要多个数据结构，一个 HashMap 就可以了。例如，你可以这样做：-

public class Location {
    private Integer x;
    private Integer y;

    public Location(Integer x, Integer y) {
        this.x = x;
        this.y = y;
    }

    // implement the equals and hashcode methods
}

public class MySpreadSheet {

    private Map<Location, String>   spreadsheet = new HashMap<Location, String>();

    public String getCellValue(Integer x, Integer y) {
        return spreadsheet.get(new Location(x, y));
    }

    public void setCellValue(Integer x, Integer y, String value) {
        spreadsheet.put(new Location(x, y), value);
    }
}

Answer 3

在设计此类问题的数据结构时，从定义 SpreadSheet 的接口开始会更容易。一旦定义了所有操作（读操作、创建操作、修改操作和删除操作），数据结构所需的特性（顺序访问、直接访问等）就会变得明显。

在电子表格中，需要一种机制来使用需要映射的索引/名称来直接访问列、行或单元格。还需要对行和列进行顺序访问（迭代），这需要列表。因此，您需要一个 MapList 接口。现在我们需要选择实现。由于删除可能发生在行或列列表中的任何位置，因此 LinkedList 实现似乎是最好的。它还允许对列表重新排列进行恒定时间操作。总而言之，LinkedListMap 将是行和列的最佳选择。

class SpreadSheet:

LinkedListMap<String,Row> rows; 
// RowKey --> Row. Row has data. This allows direct access and looping.
LinkedListMap<String,Col> cols; 
//only metadata - name,sort status, visible/invisible...
//This allows direct access and looping.

class Row:

LinkedListMap<String,Cell> cells; //colKey --> cell
//This allows direct access and looping. 

class Cell:

Object value;
EType dataType; //enum for data type

class Col:

String name;
ESortState sortState; //ASC, DESC, NONE
boolean visible; 

从工作表访问特定单元格：

rows.get(rowKey).getValue(cells.get(colKey).getName())

使用上述数据结构，您应该能够轻松实现复杂的操作，例如获取子电子表格（矩形选择）。

Answer 4

HashMap 作为基础数据结构（我说基础是因为你可以组合多个结构以获得最佳存储）可能是最好的解决方案。如果您需要访问其中一个单元格并实现了一个链表，则需要 O(n) 时间来迭代列表才能到达该单元格，而 HashMap 只需要 O(1) 时间即可访问您想要的内容。数据结构的插入和删除也是如此。

Answer 5

取决于您打算使用此电子表格做什么 - 如果仅迭代 - 那么链接列表会适合，但我真的怀疑电子表格是否需要使用它。为了实现对单元的快速且可扩展的访问，您应该使用带有内部哈希映射的 HashMap。如果您的电子表格列不是动态的并且您确切知道其数量，请不要忘记预设这些地图的大小。