Java中Collection集合的元素存储位置及底层实现疑问

不同的Collection实现类，底层存储结构完全不同，常见实现的存储方式如下：

• ArrayList/Vector：基于动态扩容的Object数组存储元素
• LinkedList：基于双向链表存储元素（每个节点是内部类对象，包含前驱、后继指针和元素值）
• HashSet：依赖HashMap实现，把元素作为HashMap的Key存储（Value是固定的空对象）
• TreeSet：基于红黑树存储元素，保证元素的有序性

你写的这段代码：

Collection<Integer> intList= new ArrayList();
intList.add(3);

绝对不会为元素3创建新字段。ArrayList类的结构是固定的，它内部有几个核心字段：

• elementData：Object类型数组，用来存放所有添加的元素（实际存储的是Integer.valueOf(3)对象的引用）
• size：记录当前集合中实际元素的个数

执行add(3)时，是把自动装箱后的Integer对象引用放到elementData数组的第size位，然后size自增1。如果数组容量不足，会触发扩容逻辑——新建一个更大的数组，把原数组元素复制过去。

ArrayList的迭代器是内部类Itr，创建迭代器时：

Iterator<Integer> intIter = intList.iterator();

这个Itr对象会持有ArrayList的elementData数组引用，同时维护几个游标字段：

• cursor：下一个要访问的元素索引（初始值为0）
• lastRet：上一次访问的元素索引（初始值为-1）

调用intIter.hasNext()时，本质是判断cursor < size——如果游标还没走到实际元素个数的位置，就返回true，表示还有元素可访问。

List是有序集合，每个元素对应从0开始的索引，不同实现类的索引关联方式不同：

• ArrayList：索引直接对应底层数组的下标，get(index)可以直接通过elementData[index]获取元素，时间复杂度为O(1)
• LinkedList：本身是双向链表，没有下标概念。调用get(index)时，会先判断索引靠近头部还是尾部，再从对应方向遍历链表，计数到目标索引位置返回元素，时间复杂度为O(n)

内容的提问来源于stack exchange，提问作者hijit