Данные электронной таблицы - связанный список или hashmap?

Question

Я хочу реализовать электронную таблицу в Java.Было бы лучше использовать связанный список (строки) связанного списка ячеек (столбцов) для хранения данных или хэш-карты (каждая ячейка отображается на ключ, например, A1 -> 1, A2-> 2 и т. Д.)?

Или есть еще лучшая структура данных для использования?

Спасибо!

Answer 1

Также взгляните на Таблица Гуавы и реализующие классы.

Answer 2

При проектировании структуры данных для таких задач проще начать с определения интерфейса для SpreadSheet. Как только все операции (операции чтения, операции создания, операции изменения и удаления) будут определены, требуемые характеристики (последовательный доступ, прямой доступ и т. Д.) Структуры данных станут очевидными.

В электронной таблице необходимы механизмы прямого доступа к столбцам, строкам или ячейкам с использованием индексов / имен, которые вызывают карту. Также потребуется последовательный доступ (итерация) по строкам и столбцам, который вызывает список. Итак, интерфейс MapList - это то, что вам нужно. Теперь нам нужно выбрать реализацию. Поскольку удаление может происходить в любом месте в списке строк или столбцов, реализация LinkedList кажется наилучшей. Это также позволило бы операции с постоянным временем для реорганизации списка. Подводя итог, LinkedListMap будет лучшим выбором для строк и столбцов.

класс 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.

класс Ряд:

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

класс ячейки:

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

класс Col:

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

Чтобы получить доступ к определенной ячейке из листа:

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

С указанными выше структурами данных вы сможете легко реализовать даже сложные операции, такие как получение электронной таблицы (прямоугольное выделение).

Answer 3

Использование 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 4

Зависит от того, что вы намереваетесь делать с этой электронной таблицей - если ТОЛЬКО итерации - тогда связанные списки подойдут, но я действительно сомневаюсь, что электронная таблица необходима для этого. Для достижения быстрого и масштабируемого доступа к ячейкам вы должны использовать HashMap с внутренними хеш-картами. Не забудьте предварительно задать размеры этих карт, если столбцы электронной таблицы не являются динамическими и вы точно знаете их число.

Answer 5

HashMap в качестве базовой структуры данных (я говорю «базовая», потому что вы можете объединить несколько структур, чтобы получить наиболее оптимальное хранилище), вероятно, будет лучшим решением.Если вам нужно было получить доступ к одной из ячеек и вы внедрили связанный список, потребуется время O (n) для итерации списка, чтобы добраться до этой ячейки, тогда как для HashMap потребуется только O (1) время для доступа к тому, что вы хотите,То же самое касается вставок и удалений в структуре данных.