容器
当我们在谈论容器时，我们在谈些什么？
用简单的话来说，容器一种编程语言内置的用来容纳对象并提供相对应处理方法的对象。我们关注容器的两个层面：
- 底层实现：内置的容器类型使用了什么数据结构？容器的某项操作的执行逻辑，复杂度是多少？
- 高层抽象：什么决定了某个对象是不是容器？哪些行为定义了容器？
Python中的四种基本容器分别是List,tuple,Set,Dict
Java中的提供的不同容器类型更多，按照顶层划分有三种List,Set和Map，下图是Java中容器关系示意图。
)
Python or Java
Python 是一门高级编程语言，它所提供的内置容器类型，都是经过高度封装和抽象后的结果。和“链表”、“红黑树”、“哈希表”这些名字相比，所有 Python 内建类型的名字，都只描述了这个类型的功能特点，其他人完全没法只通过这些名字了解它们的哪怕一丁点内部细节。
这是 Python 编程语言的优势之一。相比 C 语言这类更接近计算机底层的编程语言，Python 重新设计并实现了对编程者更友好的内置容器类型，屏蔽掉了内存管理等额外工作。为我们提供了更好的开发体验。
但如果这是 Python 语言的优势的话，为什么我们还要费劲去了解容器类型的实现细节呢？答案是：关注细节可以帮助我们编写出更快的代码。
Java 在容器的抽象性这点上则相反，如上图中所给出顶层的三种容器只是作为接口，底层有多种不同数据结构组成的各种容器，比如在初学数据结构时我们熟悉的列表的数据结构有顺序表和单链表两种实现方法，你在使用时可以做出选择到底用哪个。我们需要对每一种容器的底层实现都了解才能选择出适合我们的容器，而对于Python来说你没有这个顾虑。
Python:List
在 Python 语言的实现细节里，列表的内存是按需分配的，当某个列表当前拥有的内存不够时，便会触发内存扩容逻辑list_resize。
Python中的列表是由对其它对象的引用组成的连续数组。这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。幸运的是，Python在创建这些数组时采用了指数过分配，所以并不是每次操作都需要改变数组的大小。但是，也因为这个原因添加或取出元素的平摊复杂度较低。
所以我们知道了Python中的list实际上是顺序表而不是链表，而顺序表相比于链表来说，修改查询以及在尾部添加较快时间复杂度为O(1)，而在指定位置插入和删除元素时间复杂度为O(N)。还有更多的操作可以参考数据结构链表和线性表章节。
python中的List是用下边的C语言结构来表示的, ob_item是用来保存元素的指针数组,allocated是ob_item预先分配的内存总量
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
实际上Python的List长度增长是按照0，4，8，16，25，35，46，58，72，88,… 规律有点难找哈，看源码我们知道
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
结合C源码我们来举个例子，当一个list长度为4时，发生append操作后：
- new_size = 原有的size ＋ append一个对象 = 4 + 1 = 5
- newsize为5，二进制是 101，5 » 3 = 0
- new_allocated = 5 » 3 + 3 = 3
- new_allocated += new_size，为5 + 3 ＝ 8
- 列表的最终大小为Py_SIZE = 8
过程如下图所示：
resize的成本是很高的，因为他需要完全销毁过去的引用数组，然后重新申请新的大小的内存空间来存放引用。
Java:List
Java中的List是Collection的子接口，是有序的Collection。
List 常用实现类有ArrayList和LinkedList两种，LinkedList不存在内存分配问题因为每次add都需要额外分配内存，而线性表ArrayList和Python一样存在着内存分配和扩容问题。
我们看一下Java的ArrayList实现的源代码来分析其内存分配机制
public class ArrayList<E> extends AbstractList<E> implements List<E> {
private transient Object[] elementData;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
//Constructs an empty list with an initial capacity of ten.
public ArrayList() {
this(10);
}
public boolean add(E e) {
ensureCapacity(size + 1); // 扩充长度
elementData[size++] = e; // 先赋值，后进行size++。所以是从[0]开始存。
return true;
}
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length; // 旧集合长度
if (minCapacity > oldCapacity) {
Object oldData[] = elementData; // 旧集合数据
int newCapacity = (oldCapacity * 3)/2 + 1; // 计算新长度，旧长度的1.5倍+1
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); // 用新长度复制原数组。
}
}
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
}
add方法中先调用ensureCapacity方法对原数组长度进行扩充，扩充方式为，通过Arrays类的copyOf方法对原数组进行拷贝，长度为原数组的1.5倍+1。 然后把扩容后的新数组实例对象地址赋值给elementData引用类型变量。扩容完毕。
如果数据很大，那么有必要为集合初始化一个默认大小，防止多次扩容，但如果数据增长很慢，那么就会浪费内存了，具体怎么做，还是要看实际应用场景。这里只做初步分析。
小结
Python使用线性表实现List容器，不允许预先规定大小，查找修改时间复杂度低，增删时间复杂度高，存在扩容机制，扩容的公式是(newsize >> 3) + (newsize < 9 ? 3 : 6),即原容量除三再加一个常数。
Java实现了线性表和链表两种列表容器，线性表允许预先规定大小，扩容公式为(oldCapacity * 3)/2 + 1;即旧长度的1.5倍+1。
