1.为什么要有集合

世间上本来没有集合,但有人想要,所以有了集合

有人想有可以自动扩展的数组,所以有了List

有的人想有没有重复的数组,所以有了set

有人想有自动排序的数组,所以有了TreeSet

因为集合是对数组做的封装,所以,数组永远比任何一个集合要快

但任何一个集合,比数组提供的功能要多

数组是一种可读/可写数据结构－－－没有办法创建一个只读数组。然而可以使用collections提供的UnmodifiableCollection方法，以只读方式来使用集合。该方法将返回一个集合的只读版本(final修饰)。

集合类型主要有3种：set(集）、list(列表）和map(映射)。

几个常用类的区别

1．ArrayList: 元素单个，效率高，多用于查询

2．Vector: 元素单个，线程安全，多用于查询

3．LinkedList:元素单个，多用于插入和删除

4．HashMap: 元素成对，元素可为空

5．HashTable: 元素成对，线程安全，元素不可为空

问题

1.HashSet为什么无序，ArrayList为什么有序

2.HashMap是如何解决Hash冲突（下标冲突）的

3.ArrayList和Vector有何不同

4.HashMap初始容量是多少，什么时候会扩容，会扩容多少

---

自动扩容

初始大小:调用无参构造函数时默认的容量

加载因子:超过 (当前容量*加载因子) 时会进行扩容

扩容因子:扩容时增加的容量为 (当前容量*扩容因子)

容器          初始容量                  加载因子              扩容因子

ArrayList:        10                              1                      0.5

HashMap:      16                            0.75                    1

HashSet:    同HashMap

一般而言, 以哈希表 (链表+数组) 作为底层数据结构的容器, 当元素超过加载因子，同时每个Entry(或者叫桶)里面至少有一个元素的时候就会进行扩容(1.7)。,如HashMap,HashSet(默认16，超过12时扩容两倍)

以数组作为底层数据结构的容器, 当元素超过数组大小时会进行扩容,如ArrayList

以链表作为底层数据结构的容器, 容量没有限制, 不会进行扩容,如LinkedList,TreeMap

---

2.map

子类:hashmap,hashtable,linkedhashmap,TreeMap

2.1hashmap与hashtable

--HashMap和Hashtable的区别

线程安全性，同步(synchronization)，以及速度。

HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行

Hashtable是synchronized，这意味着Hashtable是线程安全的，Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好

HashMap可以使用collections.synchronizedMap实现同步

存放数据

indexFor是通过key的hash值&当前数组长度-1获得元素下标

计算下标

元素个数超过临界值，扩容并重新计算下标

重新计算临界值，最大容量为int类型的最大值（2的31次方-1）

hash冲突

,hashmap底层是散列表，散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。HashMap采用的链表法的方式，链表是单向链表。这也是为什么用散列表

下标下取出元素，将旧元素放到新元素的next中

hashcode相同的字符串 存放的位置

存放空key

永远放在数组的第一位

获取数据

通过key的hash值&当前数组长度-1获得元素下标,下标中的entry可能是多个元素，所以用的是循环，比对key相同并且hash值相同的元素取出

LinkedHashMap

LinkedHashMap是HashMap的子类，与HashMap有着同样的存储结构，但它加入了一个双向链表的头结点，将所有put到LinkedHashmap的节点一一串成了一个双向循环链表，因此它保留了节点插入的顺序，可以使节点的输出顺序与输入顺序相同，put方法用的父类hashmap的put方法，重写了recordAccess方法

TreeMap

TreeMap 的实现使用了红黑树数据结构，也就是一棵自平衡的排序二叉树，这样就可以保证快速检索指定节点。对于 TreeMap 而言，它采用一种被称为“红黑树”的排序二叉树来保存 Map 中每个 Entry —— 每个 Entry 都被当成“红黑树”的一个节点对待。

因此它便有一些扩展的方法，比如firstKey(),lastKey()等

---

3.List

3.1ArrayList与linkedList

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

arraylist

先对元素数量+1

当前元素位置-元素数量>0,就是数据位置不够了，开始扩容

>>1相当于除以2

LinkedList

Linkedlist有add,addFirst和addLast方法，add和adLast方法相同

3.2ArrayList与Vector

Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。

CopyOnWriteArrayList

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器

添加的时候是需要加锁的，否则多线程写的时候会Copy出N个副本出来

读的时候不需要加锁，如果读的时候有多个线程正在向CopyOnWriteArrayList添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的

Stack

Stack实际上也是通过数组去实现的。

执行push时(即，将元素推入栈中)，是通过将元素追加的数组的末尾中。

执行peek时(即，取出栈顶元素，不执行删除)，是返回数组末尾的元素。

执行pop时(即，取出栈顶元素，并将该元素从栈中删除)，是取出数组末尾的元素，然后将该元素从数组中删除。

Stack继承于Vector，意味着Vector拥有的属性和功能，Stack都拥有

出栈 出栈最底 入栈 ，与AarrayList相同

---

3.Set

子类:HashSet,LinkedHashSet,TreeSet 与List不同的是set底层是map实现的，所以不可重复

HsahSet

HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。

它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

---

4.Collections和Arrays

想必大家不会忘记“折半查找”、“排序”等经典算法吧，Collections类提供了丰富的静态方法帮助我们轻松完成这些烦人的工作：

binarySearch：折半查找。传入list和要寻找的值，返回元素下标,需要保证是有序的，也就是需要先排序sort(List list)

j>>>i 与 j/(int)(Math.pow(2,i))的结果相同

sort(List list)：对List里的元素根据自然升序排序

调用aray.sort()

reverse(List list)：反转指定List集合中元素的顺序

shuffle(List list)：对List中的元素进行随机排序（洗牌）

sort(List list, Comparator c)：自定义比较器进行排序

swap(List list, int i, int j)：将指定List集合中i处元素和j出元素进行交换

rotate(List list, int distance)：将所有元素向右移位指定长度，如果distance等于size那么结果不变

max(Collection coll)：返回最大元素

max(Collection coll, Comparator comp)：根据自定义比较器，返回最大元素

min(Collection coll)：返回最小元素

min(Collection coll, Comparator comp)：根据自定义比较器，返回最小元素

fill(List list, Object obj)：使用指定对象填充

frequency(Collection Object o)：返回指定集合中指定对象出现的次数

replaceAll(List list, Object old, Object new)：替换

Collections还有一个重要功能就是“封装器”（Wrapper），它提供了一些方法可以把一个集合转换成一个特殊的集合，如下：

unmodifiableXXX：转换成只读集合，这里XXX代表六种基本集合接口：Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作，将会抛出UnsupportedOperationException异常。

synchronizedXXX：转换成同步集合。

singleton：创建一个仅有一个元素的集合，这里singleton生成的是单元素Set，

singletonList和singletonMap分别生成单元素的List和Map。

空集：由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。

---

6.commons collectionUtils

集合判断：

例1: 判断集合是否为空:

CollectionUtils.isEmpty(null): true

CollectionUtils.isEmpty(new ArrayList()): true

CollectionUtils.isEmpty({a,b}): false

例2: 判断集合是否不为空:

CollectionUtils.isNotEmpty(null): false

CollectionUtils.isNotEmpty(new ArrayList()): false

CollectionUtils.isNotEmpty({a,b}): true

2个集合间的操作：

集合a: {1,2,3,3,4,5}

集合b: {3,4,4,5,6,7}

CollectionUtils.union(a, b)(并集): {1,2,3,3,4,4,5,6,7}

CollectionUtils.intersection(a, b)(交集): {3,4,5}

CollectionUtils.disjunction(a, b)(交集的补集): {1,2,3,4,6,7}

CollectionUtils.disjunction(b, a)(交集的补集): {1,2,3,4,6,7}

CollectionUtils.subtract(a, b)(A与B的差): {1,2,3}

CollectionUtils.subtract(b, a)(B与A的差): {4,6,7}

3.其他

CollectionUtils.unmodifiableCollection(c);  不可修改的集合

---

问题

1.HashSet为什么无序，ArrayList为什么有序

2.HashMap是如何解决Hash冲突（下标冲突）的

3.ArrayList和Vector有何不同

4.HashMap初始容量是多少，什么时候会扩容，会扩容多少