码出高效java开发手册-小结01

数据结构与集合

数据结构分类

类型	备注
线性结构	0至1个直接前继和直接后继；顺序表、链表、栈、队列。note：栈、队列访问受限
树结构	0至1个直接前继和0至n个直接后继（n大于或等于2）
图结构	简单图、多重图、有向图、无向图
哈希结构	索引和值存储，查找效率高

算法复杂度排序

从最好到最坏：常数级O(1)、对数级O(log_n)、线性级O(n)、线性对数级O(nlog_n)、平方级O(n²)、立方级O(³)、指数级O(2ⁿ )等

集合框架

Collection接口：

List: 线性结构
Set
Map: 哈希结构
Queue: 特殊的线性结构

集合初始化

ArrayList

1、使用无参构造时，默认容量大小10

2、扩容计算公式：oldCapacity + (oldCapacity >> 1)

假如需要将1000个元素放置在ArrayList中，采用默认构造方法，需要被动扩容10*1.5ⁿ=1000，n=13次才能完成。如果初始化分配1000个存储空间，从而避免被动扩容数组复制的额外开销

HashMap

1、使用无参构造时，默认容量16

2、填充比例0.75

数组与集合

数组转集合

String[] strings = new String[]{"one", "two", "three"};
List<String> stringList = Arrays.asList(strings);
stringList.add("12"); // UnsupportedOperationException
stringList.remove(2); // UnsupportedOperationException
stringList.clear(); // UnsupportedOperationException

通过源码能看到一个内部私有的的ArrayList对象，并非Collection的子类，不能有add\remove\clear操作

集合转数组

List<String> list = new ArrayList<>(3);
list.add("one");
list.add("two");
list.add("three");

// 泛型丢失,不适用
Object[] array1 = list.toArray();

String[] array2 = new String[2];
list.toArray(array2); // null


String[] array3 = new String[3];
list.toArray(array3); // one two three

toArray源码解读：即将复制进去的数组容量如果不够，则弃用此数组

public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

如果数组初始化大小设置不当，不仅会降低性能，还会浪费空间；使用集合的toArray(T[] array) 方法，转换为数组时，注意需要传入类型完全一样的数组，并且它的容量大小为list.size()