1.java集合框架
使用Array存储对象有一定的弊端。java集合就是一种容器，动态地存储多个对象，存储主要是内存层面的存储，不涉及到持久化的存储(txt,avi,数据库)。
①一旦初始化好，数组的长度就确定了，不能够再修改。
②数组一旦定义好，数组的类型就确定了，我们只能使用该类型的数据。
③数组提供功能较少
④数组存储特点有序可重复
Collection <--extends-- List <--implements-- AbstractList <--extends-- ArrayList
1.1 Collection
| contains(Object obj) | 判断集合中是否存在元素 |
| add(Object obj) | |
| containsAll(Collection coll) | |
| remove(Object obj) | |
| boolean removeAll(Collection coll1) | 其实是计算两个集合的差集(集合减去交集)，集合与自身的差集为空，是对当前集合的修改 |
| boolean retain(Collection coll1) | 求两个集合的交集，是对当前集合的修改 |
| equals(Object obj) | 注意：ArrayList有序，元素顺序不同判断为false |
| Object[] toArray() | 集合转换为数组 |
| List Arrays.asList(T... a) | 数组转换为集合 |
| Iterator iterator() | 遍历集合元素，内部方法：next()、hasnext() |
contains、remove:调用obj对象所在类的equals，判断是否相同
coll.add("QQ");
coll.add(new String("123"));
coll.add(new Person("Tom", 24));
System.out.println(coll.contains("QQ"));//true
System.out.println(coll.contains(new String("123")));//true
System.out.println(coll.contains(new Person("Tom", 24)));//false
对于String，由于String对equals进行了重写，所以比较的是String的字符串值，而自定义的Person类并没有，所以继承了Object类的equals方法，比较的是地址值。所以，向collection接口的实现类的对象中添加数据obj、移除数据obj时，需要重写obj所在类的equals方法。
ContainsAll：
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new String("789"));
Collection coll1 = Arrays.asList(123, 456);//Arrays.asList返回的是
//List，List是Collection的子接口，此处体现了多态
System.out.println(coll.containsAll(coll1));
List Arrays.asList(T... a)：形参为可变数据
List arr = Arrays.asList(new String[]{"123", "456"});
System.out.println(arr);//[123, 456]
List arr1 = Arrays.asList(123, 456);
System.out.println(arr1);//[123, 456]
List arr2 = Arrays.asList(new int[]{123, 456});
System.out.println(arr2);//[[I@677327b6]
List arr3 = Arrays.asList(new Integer[]{123, 456});
System.out.println(arr3);//[123, 456]
当形参为基本数据类型的数组时，Arrays.asList会将整个数组作为集合的一个元素。
遍历方式一：Iterator iterator()
每次调用该方法都会返回一个指向第一个元素的迭代器，内部方法hasnext()判断不会移动指针。内部方法remove()可以在遍历的时候删除当前集合的元素，不同于集合的remove方法。
Collection coll = new ArrayList();
coll.add("123");
coll.add("456");
System.out.println(coll);//[123, 456]
Iterator iterator = coll.iterator();
while(iterator.hasNext()) {
Object obj = iterator.next();
if("456".equals(obj)) {
iterator.remove();
}
}
remove:
1:如果未调用next()或者上一次调用next()方法之后又调用了remove()方法，会报IllegalStateException异常
2:List集合的迭代器调用iterator内部方法抛出UnsupportedOperationException异常
List coll = Arrays.asList(new String[]{"123", "456"});
System.out.println(coll);//[123, 456]
Iterator iterator = coll.iterator();
while(iterator.hasNext()) {
Object obj = iterator.next();
if("456".equals(obj)) {
iterator.remove();
}
}
iterator = coll.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
程序实际执行到了AbstractList中，不允许对集合进行新增和删除：
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
程序能够执行到AbstractList的增删方法，是因为asList方法返回的是一个ArrayList<>,如下所示它继承于AbstractList且没有重写增删方法：
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
/**
* @serial include
*/
private static class ArrayList<E> extends AbstractList<E>
同时，ArrayList对增删方法进行了重写。所以迭代器能够执行ArrayList的Override方法。
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
解决方法，对Arrays.asList()返回的List进行ArrayList包装:
List coll = new ArrayList(Arrays.asList(new String[]{"123", "456"}));
Iterator iterator = coll.iterator();
while(iterator.hasNext()) {
Object obj = iterator.next();
if("456".equals(obj)) {
iterator.remove();
}
}
iterator = coll.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
遍历方式二：for-each/增强for循环
for(Object obj : coll) {
System.out.println(obj);
}
obj为局部变量
1.2 List接口实现类：相较于Collection有了索引
面试：ArrayList、LinkedList、Vector三者的异同？
答：相同点：三者都实现了List接口，存储的数据的特点相同：存储有序的可重复的数据
不同点：
1.2.1 ArrayList 作为List的主要实现类，线程不安全，效率高，底层仍使用Object[] elementdata存储
jdk7.0之前的扩容
默认集合大小为10，每次add都判断扩容，默认扩容为原来的1.5倍，如果还小就直接使用最小要求扩容，并将原来数组数据拷贝到新数组。所以建议开发中使用：ArrayList list = new ArrayList(int capacity);
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
jdk8的变化
底层的Object[] elementdata初始化为{}，并没有创建长度为10的数组，只有在第一次add时进行了初始化数组长度10的操作。延迟了数组创建的时间，两种方法类似于单例模式的饿汉和懒汉式，节省了内存。
1.2.2 LinkedList 对于频繁的插入删除操作，使用此类效率较高，底层使用的是双向链表存储，不涉及到扩容
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList list = new LinkedList();内部声明了Node型的first和last属性，默认值为null。其中Node为双向链表。add时将元素封装到Node进行添加节点操作。
1.2.3 Vector List的古老实现类，线程安全，效率低，底层仍使用Object[] elementdata存储
默认element数组长度为10，默认扩容大小为2倍。
| List接口方法（8） | |
|---|---|
| void add(int index, Object element) | |
| boolean addAll(int index, Collection eles) | |
| Object get(int index) | |
| int indexof(Object obj) | obj在集合中的位置 |
| int lastIndexOf(Object obj) | |
| Object remove(int index) | 按照索引删除，重载了Collection中的按照元素删除，并返回删除的元素。和重载方法优先考虑索引，而不去装箱，若想删除值则应将基本数据类型封装成包装类。 |
| boolean set(index, Object obj) | |
| List subList(int start, int end) | 提供子List，本身list不发生变化 |
1.4 Set接口实现类：可存储无序的、不可重复的数据
无序性：不等于随机性，存储的数据在底层数组中并不是按照数组索引的顺序添加，而是根据数据的哈希值确定位置。
不可重复性：保证添加的元素按照equals()判断时，不能返回true，即相同的元素只能添加一个。
1.4.1 HashSet：作为Set接口的主要实现类，线程不安全，可以存储null
HashSet中添加元素的过程:
HashSet底层也是数组，初始容量为16，当使用量超过0.75(12)，就会扩容为原来的两倍。HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，根据计算a的哈希值，然后根据哈希函数得到在HashSet底层数组中的存放位置（即索引位置），判断数组在此位置上是否已经有其他元素：
如果没有其他元素，则添加成功。（情况一）
否则将a的哈希值与已经存在的元素b（或元素结成的链表）的哈希值进行比较：
如果哈希值均不同，则表明a元素没有重复，添加到链表底部，添加成功。（情况二）
否则调用a.equals(b):
true:添加失败。
false:添加到链表底部，添加成功。（情况三）
对于情况二和情况三：（七上八下）
jdk7:元素a放到数组，指向原来的元素。
jdk8:原来的元素在数组，链表末端元素指向a。
为什么复写hashCode方法，有31这个数字？
减少哈希冲突
添加元素的要求: 向HashSet中添加的元素所在的类需要重写hashCode()和equals()方法，并且两个方法要求具有一致性：相同的对象必须具有相等的散列码，即使用相同的哈希函数。
面试题目
Person p1 = new Person(18, "AA");
Person p2 = new Person(19, "BB");
HashSet set = new HashSet();
set.add(p1);
set.add(p2);
System.out.println(set);//AA 和 BB
p1.name = "CC";
System.out.println(set);//CC 和 BB
set.remove(p1);
System.out.println(set);//CC 和 BB
set.add(new Person(18, "AA"));
System.out.println(set);//AA BB CC
AA改名为CC后对象的哈希值仍是(18,AA)，remove p1时先根据p1(18,CC)的哈希值找不到相应的元素，故没有删除元素。同理添加(18,AA)先根据其哈希值找到现名为CC的对象，equals后发现不相同，表明set中没有相同元素故添加成功，此时set中有AA BB CC三个元素。
1.4.2 LinkedHashSet：extends于HashSet，看似像有序的，可按照添加的顺序遍历
LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据的前一个数据和后一个数据。对于频繁的遍历操作，LinkedHashSet效率高于HashSet。
1.4.3 TreeSet：要求放入数据是同一个类的实例对象，可按照添加对象的指定属性进行排序
两种排序方式：自然排序(实现Comparable接口)和定制排序(Comparator)
自然排序中，比较两个对象是否相同的标准是compareTo是否返回0，而不再是equals()方法。
定制排序中，比较两个对象是否相同的标准是compare()是否返回0，而不再是equals()方法。
2 Map接口：存储key-value双列数据，类似于函数的概念
Key：无序，不可重复，用Set存储,key所在类需要重写equals和hasCode方法(以hashSet为例)
Value：无序，可以重复，使用Collection存储，value所在类要重写equals方法
一个键值对：key-value构成了一个entry实体，使用Set存储所有的entry
| Map中的常用方法： | |
|---|---|
| Object put(Object key, Object value) | 添加或修改（key相同但value不同的）key-value键值对到当前map |
| void putAll(Map m) | 将m中所有的数据添加到当前map |
| Object remove(Object key) | 根据key移除key-value键值对，并返回value，不存在则返回null |
| void clear() | 清楚map中的数据 |
| 元素查询操作 | |
|---|---|
| Object get(Object key) | 返回key对应的value |
| boolean containsKey(Object key) | 是否包含指定的key |
| boolean containsValue(Object value) | 是否包含指定的value |
| int size() | 返回map中key-value键值对的个数 |
| boolean isEmpty() | 判断map是否为空 |
| boolean equals(Objection obj) | 判断map和对象obj是否相等 |
| 元视图操作的方法 | 得到Collection后可用iterator遍历 |
|---|---|
| Set keySet() | 返回所有key构成的Set集合 |
| Collection values() | 返回所有value构成的Collection集合 |
| Set entrySet() | 返回所有key-value对构成的Set集合 |
2.1 HashMap：作为Map的主要实现类，线程不安全，效率高
HashMap底层结构：jdk7之前：数组+链表
jdk8：数组+链表+红黑树
HashMap的底层实现原理？
以jdk7为例
HashMap hashmap = new HashMap();
map.put(key1, value1)
首先调用key1所在类的hashCode()计算key1的哈希值，此哈希值经过某种算法计算后得到在Entry数组的存放位置：
如果此位置上的数据为空，则数据添加成功；情况一
如果数据不为空（意味着此位置上存在一个或多个数据（以链表的形式存在）），则比较key与一个或则多个数据的哈希值：
如果key1的哈希值和已经存在的数据的哈希值都不相同，则key1-value1i添加成功；情况二
如果key1的哈希值和已经存在的一个数据的哈希值相同，继续比较，调用key1所在类的equals(key2)：
如果equals返回false：则key1-value1i添加成功；情况三
如果equals返回true：则使用value1替换value2.
情况二和情况三，此时的数据和原来的数据以链表的形式存储。
默认的扩容方式：扩容为原来的两倍，并将原来的数据复制过来。
jdk8相较于jdk7在底层结构上的不同
(1)new HashMap()：底层没有创建一个长度为16的数组
(2)jdk 8的底层数组不是entry而是node
(3)在首次调用put()时才创建默认长度为16的数组
(4)jdk7的底层结构为数组加链表
jdk8的底层结构为数组加链表加红黑树，当数组的某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组长度>64时，此时此索引位置上的所有数据改为红黑树存储。
HashMap和Hashtable的异同？
2.1.1 子类LinkedHashMap：保证在遍历map元素时，按照添加的顺序进行遍历。原理：在原有的HashMap底层结构基础上，添加了一对指针，可以指向前面和后面的元素。对于频繁的遍历操作，此类效率高于HashMap。
2.2 Hashtable：作为Map的古老实现类，线程安全，效率低，不能存储null的key和value
2.2.1 子类Properities：常用来处理配置文件，其key-value都是String类型
Properties pros = new Properties();
FileInputStream fis = new FileInputStream("./jdbc.properties");
pros.load(fis);
String name = pros.getProperty("name");
String password = pros.getProperty("password");
System.out.println(name + " " + password);
2.3 TreeMap：保证按照添加的key-value对进行排序，实现排序遍历，此时考虑key的自然排序或者定制排序。底层使用红黑树。
向TreeMap中添加key-value数据要保证key值所在的类实现了Comparable的compareTo()方法或者Comparator的compare(o1, o2).
3.Collections：操作Collection、Map的工具类
| Collections | |
|---|---|
| void reverse(list) | |
| shuffe(list) | 打乱顺序 |
| sort(list) | 自定义类需要重写compareTo |
| swap(int index1, int index2) | |
| Object max、min(Collection) | 根据自然排序返回最大、小值 |
| Object max、min(Collection, Comparator) | 根据定制排序返回最大、小值 |
| int frequency(list, Objection obj) | |
| void copy(list dest, list src) | 将src中的内容复制到dest中 |
| synchronizedXXX() |
定制排序sort
Collections.sort(list, new Comparator<Object>() {
@Override
public int compare(Object o1, Object o2) {
Integer i1 = (Integer) o1;
Integer i2 = (Integer) o2;
return -i1.compareTo(i2);
}
});
copy()方法注意点
List list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
//IndexOutOfBoundsException
// List dest = new ArrayList();
List dest = Arrays.asList(new Object[list.size()]);
Collections.copy(dest, list);
System.out.println(dest);
线程安全
Collections类中提供了多个synchronizedXXX()方法，该方法可以将指定集合包装成线程安全的集合，从而解决多线程并发访问集合时的线程安全问题。
List list1 = Collections.synchronizedList(list);
