面试题：Java中ArrayList性能优化之内存占用与数据结构结合

设计思路

结合优点：
- ArrayList 具有快速随机访问的优点，但在频繁添加和删除元素时，尤其是在列表中间位置操作，需要移动大量元素，性能较差且可能导致频繁内存重分配。
- LinkedList 则在添加和删除元素时具有较好的性能，因为只需调整节点的指针，不需要移动大量数据。然而，LinkedList 的随机访问性能较差，且每个节点除了存储数据外，还需要额外存储指针信息，内存占用相对较高。
- 设计一个新的数据结构，结合 ArrayList 的随机访问优势和 LinkedList 的添加删除优势。
分层结构：
- 可以设计一个基于块的结构。外层使用 LinkedList 来管理多个数据块，每个数据块内部使用 ArrayList。这样，当进行添加和删除操作时，如果是块间操作，可以利用 LinkedList 的优势；如果是块内操作，可以利用 ArrayList 的优势。
- 例如，当添加一个元素时，如果当前块未满，直接添加到当前块（即当前 ArrayList）中；如果当前块已满，则在 LinkedList 中新增一个块，并将元素添加到新块中。删除元素时类似，如果删除后块内元素过少，可以考虑合并相邻块以减少内存占用。

实现要点

数据块类：

定义一个数据块类，例如 Block，内部包含一个 ArrayList 用于存储数据。同时可以记录块的容量、当前元素数量等信息。

class Block {
    private ArrayList<Object> data;
    private int capacity;
    private int size;
    public Block(int capacity) {
        this.data = new ArrayList<>(capacity);
        this.capacity = capacity;
        this.size = 0;
    }
    public void add(Object element) {
        if (size < capacity) {
            data.add(element);
            size++;
        }
    }
    public Object remove(int index) {
        if (index < size) {
            size--;
            return data.remove(index);
        }
        return null;
    }
    public Object get(int index) {
        if (index < size) {
            return data.get(index);
        }
        return null;
    }
    public int getSize() {
        return size;
    }
}

主数据结构类：

定义主数据结构类，例如 HybridList，内部使用 LinkedList<Block> 来管理数据块。
实现添加元素方法：

import java.util.LinkedList;
public class HybridList {
    private LinkedList<Block> blocks;
    private int blockCapacity;
    public HybridList(int blockCapacity) {
        this.blocks = new LinkedList<>();
        this.blockCapacity = blockCapacity;
        blocks.add(new Block(blockCapacity));
    }
    public void add(Object element) {
        Block lastBlock = blocks.getLast();
        if (lastBlock.getSize() == blockCapacity) {
            Block newBlock = new Block(blockCapacity);
            newBlock.add(element);
            blocks.add(newBlock);
        } else {
            lastBlock.add(element);
        }
    }
}

实现删除元素方法：

public Object remove(int index) {
    int blockIndex = 0;
    int localIndex = index;
    for (Block block : blocks) {
        if (localIndex < block.getSize()) {
            Object removed = block.remove(localIndex);
            if (block.getSize() == 0) {
                blocks.remove(blockIndex);
            }
            return removed;
        } else {
            localIndex -= block.getSize();
            blockIndex++;
        }
    }
    return null;
}

实现获取元素方法：

public Object get(int index) {
    int blockIndex = 0;
    int localIndex = index;
    for (Block block : blocks) {
        if (localIndex < block.getSize()) {
            return block.get(localIndex);
        } else {
            localIndex -= block.getSize();
            blockIndex++;
        }
    }
    return null;
}
}

内存管理：
- 在删除元素后，检查块内元素数量，如果过少（例如低于块容量的一定比例），可以考虑与相邻块合并。这样可以减少块的数量，从而减少 LinkedList 节点和指针的内存占用。
- 例如，在 remove 方法中，删除元素后检查块的大小，如果块大小小于块容量的 1/4 且相邻块有空间，则可以将当前块的元素合并到相邻块，并从 LinkedList 中移除当前块。
优化块容量：
- 块容量的选择很关键。容量过小，会导致 LinkedList 中块的数量过多，增加指针的内存占用；容量过大，在删除元素后可能造成较多的内存浪费。可以根据应用场景的实际数据量和操作频率进行调优。

通过这种设计，可以在频繁添加和删除元素的内存敏感场景中，较好地平衡性能和内存占用。

星途面试题库

面试题：Java中ArrayList性能优化之内存占用与数据结构结合

知识考点

面试题答案

设计思路

实现要点