07-集合类

集合类

问：Java的集合类框架

Java集合类提供了一套设计良好的支持对一组对象(对于基本类型，必须要使用其包装类型)进行操作的接口和类。集合类接口的每一种具体的实现类都可以选择以它自己的方式对元素进行保存和操作(增、删、改、查)。有的集合类允许重复的元素，有些不允许。

Java集合类有两大接口：Collection和Map，一个是元素集合，另一个是键值对集合且键不能重复。

图 1

图 2

• Collection以单个对象的形式保存数据。List和Set接口继承了Collection接口。
  • List是有序元素集合(即每个元素都可以按index访问)，元素可以重复；
  • Set是无序元素集合(即每个元素都不可以按index访问)，元素不可以重复。
  • ArrayList、LinkedList和Vector实现了List接口，HashSet和TreeSet实现了Set接口，这几个都比较常用；
    • ArrayList和Vector都以数组的方式存储，增、删慢，查、改快；ArrayList:线程不安全，速度快；Vector:线程安全，速度慢；
    • LinkedList: 以双向链表的方式存储，操作慢。
  • Queue接口继承了Collection接口，模拟了队列先进先出的数据结构
  • Statck类为Vector的子类，模拟了栈后进先出的数据结构。
• Map以键值对的形式保存数据，key不可以重复。
  • HashMap和HashTable实现了Map接口。HashMap不是线程安全的，HashTable是线程安全的，但是HashMap性能更好；
• 由于Collection类继承Iterable类，所以，所有Collection的实现类都可以通过foreach的方式进行遍历。

问：List、Set和Map三个接口存取元素时，各有什么特点？

List和Set继承自Collection接口，是单列元素集合；Map是双列元素集合，即key/value对集合。

(1) List是有序元素集合(即每个元素都可以按index访问)，元素可以重复；

同一个对象可以被反复存储进List中，每调用一次add方法，这个对象就被插入进集合一次，size()也增大1。其实，并不是把这个对象本身存储进了集合中，而是在集合中用一个索引变量指向这个对象，当这个对象被add多次时，相当于在集合中有多个索引指向了这个对象。

• 可以使用add(Object obj)方法将元素放到集合的末尾；
• 可以使用add(int index, Object obj)方法将元素放到集合中的指定位置；
• 可以使用Iterator接口获得集合中的所有元素，再逐一遍历各个元素；
• 可以使用get(index i)方法获得集合中指定位置的元素。

(2) Set是无序元素集合(即每个元素都不可以按index访问)，元素不可以重复，元素重复与否是使用equals()方法进行判断的。

• 可以使用add(Object obj)方法将元素存储进集合。该方法有一个boolean类型的返回值，当集合中没有某个元素时，add方法可以成功加入该元素并且返回true；当集合已经含有与某个元素equals()相等的元素时，此时add方法无法加入该元素并且返回false；
• 由于Set中元素是无序的，无法按index访问，所以只能用Iterator接口取得所有的元素，再逐一遍历各个元素

(3) Map是key/value对集合，key不可以重复，这个重复的规则是根据equals()方法比较相等的

• 可以使用put(Object key, Object value)方法存储key/value对，key不可以重复
• 可以使用get(Object key)方法获得与key相对应的value；
• 可以使用keySet()方法获得所有key的集合；
• 可以使用values()方法获得所有value的集合；
• 可以使用entrySet()方法获得所有key和value组合成的Map.Entry对象的集合。

问：Java语言中的几种数组复制方法效率比较

System.arraycopy > clone > Arrays.copyOf > for循环

问：Java集合框架中线程安全的类

Vector、Stack(它继承了Vector)、Hashtable、Properties、Enumeration、(非集合类的StringBuffer)

问：ArrayList容量

ArrayList的构造函数总共有三个

• ArrayList()构造一个初始容量为 10 的空列表，动态增长时，容量增长到当前容量的1.5倍

• ArrayList(Collection<? extends E> c)
  构造一个包含指定collection的元素的列表，这些元素是按照该collection的迭代器返回它们的顺序排列的。

• ArrayList(int initialCapacity)构造一个具有指定初始容量的空列表。

问：数组(Array)和列表(ArrayList)的区别？什么时候应该使用Array而不是ArrayList？

(1) Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。(但是需要注意的是：Array数组中存放的一定是同种类型的元素；ArrayList就不一定了，因为ArrayList可以存储Object。)

(2) Array大小是固定的，ArrayList的大小是动态变化的。

(3) ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等。

对于基本类型数据，ArrayList使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。

注意：Arrays.asList()将一个数组转化为一个List对象，这个方法会返回一个ArrayList类型的对象，这个ArrayList类并非java.util.ArrayList类，而是Arrays类的静态内部类！对这个对象进行添加删除更新操作，会报UnsupportedOperationException异常。

问：ArrayList、Vector、LinkedList的异同

ArrayList、Vector、LinkedList都实现了List接口，并且三者都可以添加null元素。

public static void main(String[] args) {
    ArrayList<String> arrayList = new ArrayList<String>();
    arrayList.add(null);
    arrayList.add(null);
    System.out.println(arrayList.size());//2

    LinkedList<String> linkedList = new LinkedList<String>(); 
    linkedList.add(null);
    linkedList.add(null);
    System.out.println(linkedList.size());//2

    Vector<String> vectorList = new Vector<String>();
    vectorList.add(null);
    vectorList.add(null);
    System.out.println(vectorList.size());//2
}

Vector和ArrayList的异同

相同点：两者都实现了List接口，在功能上基本完全相同，其底层都是通过new出的Object[]数组实现。

(1) 由于两者的数据结构为数组，因此都是有序集合，即存储在这两个集合中的元素的位置都是有顺序的，可以按位置索引取出某个元素，并且其中的数据是允许重复的。

(2) 由于两者的数据结构为数组，因此当我们能够预估到数组大小的时候，我们可以指定数组的初始大小，这样可以减少后期动态扩充数组大小带来的消耗。

ArrayList<String> arrayList= new ArrayList<String>(20);
Vector<String> vector = new Vector<String>(15);

(3) 由于两者的数据结构为数组，因此在获取数据方面，即get()时比较高效，而在指定位置add()或remove()时，由于需要移动元素，效率相对不高。

不同点：

(1) Vector的大部分方法都加了synchronized，即Vector是同步的，而ArrayList不是同步的。即Vector是线程安全的，而ArrayList是线程不安全的。Vector是Java中的遗留容器。

因此如果只有一个线程会访问集合，最好使用ArrayList，因为它不考虑线程安全，效率会高些；如果有多个线程会访问集合，最好使用Vector，因为我们不需要自己去编写和线程安全相关的代码。大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。

(2) 在元素增加，容量需要增长时，Vector容量默认增长原来的一倍，而ArrayList增长原来的50%，这样，ArrayList就有利于节约内存空间。

(3) 如果涉及到堆栈、队列等操作，应该考虑用Vector；如果需要快速随机访问元素，应该使用ArrayList。

例1：如何去掉一个Vector集合中重复的元素？

private Vector<Integer> fun(Vector<Integer> oVector){
    Vector<Integer> vector = new Vector<Integer>();
    for (int i = 0; i < oVector.size(); i++) {
        Integer obj = oVector.get(i);
        if (!vector.contains(obj)) {
            vector.add(obj);
        }
    }
    return vector;
}

或者

private Vector<Integer> fun(Vector<Integer> oVector){
    Set<Integer> set = new HashSet<Integer>(oVector);
    Vector<Integer> vector=new Vector<Integer>(set);
    return vector;
}

ArrayList和LinkedList的区别

ArrayList和LinkedList都实现了List接口，两者都是线程不安全的，他们有以下的不同点：

(1) ArrayList是基于索引的数据结构，它的底层是数组，它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以双向链表的形式存储数据的，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。

(2) 相对于ArrayList，LinkedList的插入、删除时不需要移动元素，不需要像数组那样重新计算大小或者是更新索引，操作速度更快。

(3) LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

(4) LinkedList提供了一些方法，使得LinkedList可以被当作堆栈和队列来使用。

使用选择

• LinkedList适合于有大量的增加/删除操作和较少随机读取操作；
• ArrayList适合于大规模随机读取数据，而较少插入和删除元素情景下使用；Vector在要求线程安全的情况下使用。
• Vector属于遗留容器（Java早期的版本中提供的容器，除此之外，Hashtable、Dictionary、BitSet、Stack、Properties都是遗留容器），已经不推荐使用。但是由于ArrayList和LinkedListed都是非线程安全的，如果遇到多个线程操作同一个容器的场景，则可以通过工具类Collections中的synchronizedList方法将其转换成线程安全的容器后再使用（这是对装潢模式的应用，将已有对象传入另一个类的构造器中创建新的对象来增强实现）。

问：什么是Java优先级队列(Priority Queue)？

PriorityQueue是一个基于堆排序的无界队列，此队列按照在构造时所指定的顺序对元素排序，既可以根据元素的自然顺序来指定排序，也可以给它提供一个负责给元素排序的比较器来指定，这取决于使用哪种构造方法。

PriorityQueue不允许null值，因为他们没有自然顺序，或者说他们没有任何的相关联的比较器。

最后，PriorityQueue不是线程安全的，入队和出队的时间复杂度是O(log(n))。

问：什么是迭代器(Iterator)？

Iterator接口提供了很多对集合中元素进行迭代的方法，每一个集合类都包含了可以返回迭代器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素,但是不可以直接调用集合的remove(Object Obj)删除，可以通过迭代器的remove()方法删除。

问：Enumeration接口和Iterator接口的区别有哪些？

(1) Enumeration速度是Iterator的2倍，同时占用更少的内存。

(2) 但是，Iterator远远比Enumeration安全，因为其他线程不能够修改正在被iterator遍历的集合里面的对象。

(3) 同时，Iterator允许调用者删除底层集合里面的元素，这对Enumeration来说是不可能的。

例1：list是一个ArrayList的对象，为了能够在Iterator遍历的过程中正确并安全的删除一个list中保存的对象，//todo delete处可以可以填写什么代码？

Iterator it = list.iterator();
int index = 0;
while (it.hasNext()){
    Object obj = it.next();
    if (needDelete(obj)){//needDelete返回boolean，决定是否要删除
        //todo delete
    }
    index ++;
}

正确答案：it.remove();

问：Iterator和ListIterator的区别是什么？

(1) Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。

(2) Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。

(3) ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

问：快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

快速失败：当你在迭代一个集合的时候，如果有另一个线程正在修改你正在访问的那个集合时，就会抛出一个ConcurrentModification异常。

安全失败：你在迭代的时候会对底层集合做一个拷贝，所以有另一个线程在修改上层集合的时候，访问是不会受影响的，不会抛出ConcurrentModification异常。

• 迭代器的安全失败是基于对底层集合做拷贝，因此，它不受原集合上修改的影响。
• java.util包下面的所有的集合类都是快速失败的，而java.util.concurrent包下面的所有的类都是安全失败的。
• 快速失败的迭代器会抛出ConcurrentModificationException异常，而安全失败的迭代器永远不会抛出这样的异常。

问：List遍历过程中删除元素

List遍历过程中删除元素的推荐做法：在遍历的同时，使用Iterator删除底层集合里面的元素

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);list.add(2);list.add(2);list.add(3);list.add(4);
        System.out.println("size of list is "+list.size());
        Iterator<Integer> iterator = list.iterator();
        while(iterator.hasNext()){
            Integer num = iterator.next();
            if (num==2) {
                iterator.remove();
            }
        }
        System.out.println(list.toString()); // 输出： [1, 3, 4]
    }
}

注意： 对于iterator的remove()方法，也有需要我们注意的地方：

• 每调用一次iterator.next()方法，只能调用一次remove()方法；
• 调用remove()方法前，必须调用过一次next()方法；

会报错的删除方式

(1) 使用Iterator遍历list时，使用list.remove()方法删除元素

List<Integer> list = new ArrayList<Integer>();
list.add(1);list.add(2);list.add(2);list.add(3);list.add(4);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
    Integer value=iterator.next();
    list.remove(value); //报错！！！
}

(2) 使用foreach遍历list时，使用list.remove()方法删除元素

List<Integer> list = new ArrayList<Integer>();
list.add(1);list.add(2);list.add(2);list.add(3);list.add(4);
for(Integer value : list){  
    list.remove(value); //报错！！！  
}

上面两种情况都会报java.util.ConcurrentModificationException异常：Iterator是快速失败的迭代器，foreach实际上使用的是iterator进行遍历的。

通过索引下标的方式删除：不会报错，但是可能漏删或不能完全删除的方式

使用索引下标调用list.remove(index)方法后，list.size()一直在减少，同时后面的元素会往前移动，这样会导致list中的索引index指向的数据发生变化，导致删除的数据不是目标数据。

(1) 漏删

List<Integer> list = new ArrayList<Integer>();
list.add(1);list.add(2);list.add(2);list.add(3);list.add(4);
for (int i = 0; i < list.size(); i++) {
    if (list.get(i)==2) {
        list.remove(i);
    }
}
System.out.println(list.toString()); //输出： [1, 2, 3, 4]

只删除了一个2，另一个没有被删除，原因是：删除了第一个2后，集合里的元素个数减1，后面的元素往前移了1位，此时，第二个2已经移到了索引index=1的位置，而此时i马上i++了，list.get(i)获得的是数据3。

(2) 不能完全删除数据

List<Integer> list = new ArrayList<Integer>();
list.add(1);list.add(2);list.add(2);list.add(3);list.add(4);
for (int i = 0; i < list.size(); i++) {  
    list.remove(i);  
}
System.out.println(list.toString()); // 输出： [2, 3]

从结果可以看出，使用索引方式删除并没有把所有数据都删除干净。原因是：在list.remove之后，list的大小发生了变化，也就是list.size()一直在变小，而i却一直在加大，当i=3时，list.size()=2，此时循环的判断条件不满足，退出了程序。

问：HashMap和Hashtable有什么区别？

HashMap和Hashtable都实现了Map接口，因此很多特性非常相似，里面存放的元素不保证有序，并且不存在相同元素。但是，他们有以下不同点：

(1) HashMap允许键和值是null（但是最多只能有一个键为null，可以有一个或多个键所对应的值都为null。当get()方法返回null值时，既可以表示HashMap中没有该键，又可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断）；而Hashtable不允许键或者值是null。

(2) Hashtable是同步的(使用synchronized)，而HashMap不是，即HashMap是非线程安全的，HashTable是线程安全的。因此，HashMap更适合于单线程环境，而Hashtable适合于多线程环境。因为线程安全的问题，HashMap效率比HashTable的要高。

(3) HashMap提供了可供应用于迭代键的Iterator，因此，HashMap是快速失败的。Hashtable也使用了Iterator，另一方面，由于历史原因，Hashtable还提供了对键的Enumeration，是安全失败的。

(4) 哈希值的使用不同，HashTable直接使用对象的hashCode，而HashMap重新计算hash值。

(5) Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式不同。HashTable中hash数组默认大小是11，增加的方式是old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数

一般现在不建议用HashTable：

• (1) HashTable是遗留类，内部实现很多没优化和冗余。
• (2) 即使在多线程环境下，现在也有同步的ConcurrentHashMap替代，没有必要因为是多线程而用HashTable。

例1，例2，看两道题的评论

注意：

(1) 影响HashMap(或HashTable)性能的因素有两个：初始容量和load factor；

当Hash表中数据记录的大小超过当前容量，Hash表会进行rehash操作，也就是自动扩容，这种操作一般比较耗时。所以当我们能够预估Hash表大小时，尽量在初始化的时候就指定初始容量，避免中途Hash表重新扩容操作。(类似可以指定容量的还有ArrayList、Vector)

(2) 在使用选择上，当我们需要保证线程安全时，优先选择HashTable；当我们程序本身就线程安全时，优先选择HashMap。

其实HashTable也只是保证在数据结构层面上的同步，对于整个程序还是需要进行多线程并发控制；在JDK后期版本中，对于HashMap，可以通过Collections获得同步的HashMap：

Map m = Collections.synchronizedMap(new HashMap(...)); //这种方式就可以获得具有同步能力的HashMap       

(3) 在JDK1.5以后，出现了ConcurrentHashMap，它可以很好地解决在并发程序中使用HashMap的问题，ConcurrentHashMap和HashTable功能很像，不允许为null的key或value，但它不是通过给方法加synchronized进行并发控制的。

ConcurrentHashMap中使用分段(Segment)锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据的时候，其他段的数据也能被其他线程访问，实现真正的并发访问，效率比HashTable好很多。

拓展：TreeMap和LinkedHashMap

HashMap、TreeMap、LinkedHashMap都是Map的一些具体实现类

• TreeMap实现了SortedMap接口，它保存的记录是根据键值key排序的，默认是按key升序排列。也可以指定排序的Comparator
• LinkedHashMap保存了数据的插入顺序，底层是通过一个双向链表的数据结构来维持插入顺序的。key和value都可以为null

问：Java中的HashMap的工作原理是什么？

Java中的HashMap是以键值对(key-value)的形式存储元素的。

HashMap需要一个hash函数，它使用hashCode()和equals()方法来向集合/从集合添加和检索元素。
当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值。

HashMap的一些重要的特性是它的容量(capacity)，负载因子(load factor)和扩容极限(threshold resizing)。

HashMap中解决哈希冲突的方法是链地址法。HashMap的底层结构是一个数组，数组中的每一项是一条链表。

例1

HashMap的遍历方式

(1) 推荐方式：foreach

通过map.entrySet()方式获取Entry集合，然后通过foreach方式进行遍历。

public static void main(String[] args) {
    Map<String, Integer> map = new HashMap<String, Integer>(20);
    map.put("key1", 1); map.put("key2", 2); map.put("key3", 3);
    for (Map.Entry<String, Integer> entry : map.entrySet()) { // 直接遍历出Entry
        System.out.println("key-->" + entry.getKey() + ", value-->" + map.get(entry.getKey()));
    }
}

(2) 普通方式：iterator

public static void main(String[] args) {
    Map<String, Integer> map = new HashMap<String, Integer>(20);
    map.put("key1", 1); map.put("key2", 2); map.put("key3", 3);
    Iterator<String> keySet = map.keySet().iterator(); 
    while(keySet.hasNext()){  
        Object key = keySet .next();  
        System.out.println("key-->" + key + ", value-->" + map.get(key));
    }  
}

问：HashSet

HashSet子类依靠hashCode()和equal()方法来区分重复元素

HashSet内部使用Map保存数据，即将HashSet的数据作为Map的key值保存，这也是HashSet中元素不能重复的原因。而Map中保存key值前，会去判断当前Map中是否含有该key对象，内部是先通过key的hashCode，确定有相同的hashCode之后，再通过equals方法判断是否相同。

例1

问：HashSet和TreeSet有什么区别？

HashSet的底层是由哈希表来实现的，因此，它的元素是无序的。add()，remove()，contains()方法的时间复杂度是O(1)。

TreeSet的底层是由红黑树来实现的，它里面的元素是有序的。因此，add()，remove()，contains()方法的时间复杂度是O(logn)。

问：TreeMap和TreeSet在排序时如何比较元素？

TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。

TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。

import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<Student> set = new TreeSet<Student>();
        set.add(new Student("Hao LUO", 33));
        set.add(new Student("XJ WANG", 32));
        set.add(new Student("Bruce LEE", 60));
        set.add(new Student("Bob YANG", 22));

        for (Student stu : set) {
            System.out.println(stu);
        }
    }
}

class Student implements Comparable<Student> {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student [name=" + name + ", age=" + age + "]";
    }

    public int compareTo(Student o) {
        return this.age - o.age;
    }
}

输出：
Student [name=Bob YANG, age=22]
Student [name=XJ WANG, age=32]
Student [name=Hao LUO, age=33]
Student [name=Bruce LEE, age=60]

问：HashMap、Hashtable、HashSet和ConcurrentHashMap的比较

• ConcurrentHashMap使用segment来分段和管理锁，而不是用synchronized

推荐阅读

问：Set中的元素不可重复

Set中的元素是不允许重复的。因此Set再插入或删除元素时，需要对两个元素进行比较。比较时，Set会先调用hashCode方法，判断两个元素是否有相同的hashCode，如果不相同，证明不相等；如果hashcode相同，再调用equals方法，如果equals方法判断返回true，则两个元素是相同的，否则两个元素不相同。

判断Set中是否包含某一个元素是通过contains来判断的。

问：hashCode()和equals()方法在HashMap的重要性体现在什么地方？

推荐阅读：浅谈Java中的hashcode方法

Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。

(1) 没有重写hashCode()时会出什么问题

hashCode()方法的返回值一般是对象的存储地址或与对象存储地址相关联的hash散列值。

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object obj) {
        return this.name.equals(((Person) obj).name) && this.age == ((Person) obj).age;
    }
}

Person类重写了equals()方法，但是没有重写hashCode()方法，如果我们按平常的方式调用equals()方法来判断元素是否相等并不会出什么问题，如：

public static void main(String[] args) {
    Person p1 = new Person("p", 18);
    Person p2 = new Person("p", 18);
    System.out.println(p1.equals(p2));//输出：true
}

但是当我们使用HashMap来保存Person对象的时候就会出问题了，如下：

public static void main(String[] args) {
    HashMap<Person, Integer> hashMap = new HashMap<Person, Integer>();
    Person p1 = new Person("p1", 18);
    hashMap.put(p1, 1);
    System.out.println(hashMap.get(new Person("p1", 18)));//输出：null
}

这是因为，我们没有重写Person的hashCode()方法，此时的Person对象调用的hashCode()方法还是父类的默认实现，即返回的是和对象内存地址相关的int值，这个时候，p1对象和new Person(“p1”,18);对象因为内存地址不一致，所以其hashCode()返回值也是不同的。故HashMap会认为这是两个不同的key，故返回null。

所以，我们想要正确的结果，只需要重写hashCode()方法，让equals()方法和hashCode()方法始终在逻辑上保持一致性。

(2) hashCode()方法设计原则

设计hashCode()时需要注意的问题：无论何时，对同一个对象调用hashCode()都应该产生同样的值。如果用put()将一个对象添加进HashMap时产生一个hashCode值，而用get()取出时却产生了另一个hashCode值，那么就无法获取该对象了。所以如果你的hashCode()方法依赖于对象中易变的数据，那么就需要当心了，因为此数据发生变化时，hashCode()方法就会生成一个不同的hashCode值。

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Person p1 = new Person("p1", 18);
        System.out.println("before update: "+p1.hashCode());
        HashMap<Person, Integer> hashMap = new HashMap<Person, Integer>();
        hashMap.put(p1, 1);
        p1.setAge(13);// 改变依赖的一个值
        System.out.println("after update: "+p1.hashCode());
        System.out.println(hashMap.get(p1)); // 此时还是返回为null,这是因为我们p1的hashCode值已经改变了
    }
}

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int hashCode() {
        return name.hashCode() * 37 + age; // hashCode的返回值依赖于对象中的易变数据
    }

    @Override
    public boolean equals(Object obj) {
        return this.name.equals(((Person) obj).name) && this.age == ((Person) obj).age;
    }
}

(3) hashCode()和equals()应该满足的关系

在HashMap中判断两个对象是否相同取决于equals()方法，而两个对象的hashCode值是否相等是两个对象是否相同的必要条件。所以有以下结论：

• (1) 如果两个对象的hashCode值不等，那么这两个对象一定不是同一个对象，即他们的equals()方法一定要返回false；
• (2) 如果两个对象的hashCode值相等，这两个对象也不一定是同一个对象，即他们的equals()方法返回值不确定；

反过来，

• (1) 如果equals()方法返回true，两个对象是同一个对象，它们的hashCode值一定相等；
• (2) 如果equals()方法返回false，hashCode值也不一定不相等，即是不确定的；

例1：两个对象值相同(x.equals(y)==true)，但却可以有不同的hashcode，这句话对不对?

对。

如果对象保存在HashSet或HashMap中，它们equals()相等，那么它们的hashcode值就必须相等。
如果对象不是保存在HashSet或HashMap，则equals()与hashcode就没有什么关系了，这时候hashcode不相等也是可以的。例如ArrayList中存储的对象就不用实现hashcode()方法，当然，我们没有理由不实现，通常都会去实现的。

问：Comparable和Comparator接口是干什么的？列出它们的区别。

Java提供了只包含一个compareTo()方法的Comparable接口。

• 这个方法可以个给两个对象排序。具体来说，它返回负数，0，正数来表明输入对象小于，等于，大于已经存在的对象。

Java提供了包含compare()和equals()两个方法的Comparator接口。

• compare()方法用来给两个输入参数排序，返回负数，0，正数表明第一个参数是小于，等于，大于第二个参数。
• equals()方法需要一个对象作为参数，它用来决定输入参数是否和comparator相等。只有当输入参数也是一个comparator并且输入参数和当前comparator的排序结果是相同的时候，这个方法才返回true。

(1) Comparable和Comparator都是用来实现集合中元素的比较、排序的，只是Comparable是在集合内部定义方法实现排序，Comparator是在集合外部定义方法实现排序，所以，如果想要实现对集合中元素的排序，就需要在集合外定义实现Comparator接口的方法或在集合内实现Comparable接口的方法compareTo()。Comparator位于包java.util下，而Comparable位于包java.lang下。

(2) Comparable是一个对象本身就已经支持自比较所需要实现的接口（如 String、Integer自己就可以完成比较大小操作，已经实现了Comparable接口），自定义的类要在加入list容器中后能够排序，可以实现Comparable接口，在用Collections类的sort方法排序时，如果不指定Comparator，那么就以自然顺序排序，这里的自然顺序就是实现Comparable接口设定的排序方式。

(3) Comparator是一个专用的比较器，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较。

例1：Collections工具类中的sort()方法如何比较元素？

Collections工具类的sort方法有两种重载的形式：

(1) 第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；

(2) 第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Student> list = new ArrayList<>();
        list.add(new Student("Hao LUO", 33));
        list.add(new Student("XJ WANG", 32));
        list.add(new Student("Bruce LEE", 60));
        list.add(new Student("Bob YANG", 22));

        Collections.sort(list, new Comparator<Student> () {
            public int compare(Student o1, Student o2) {
                return o1.getName().compareTo(o2.getName());
            }
        });

        for(Student stu : list) {
            System.out.println(stu);
        }
    }
}

class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Student [name=" + name + ", age=" + age + "]";
    }
}

输出：
Student [name=Bob YANG, age=22]
Student [name=Bruce LEE, age=60]
Student [name=Hao LUO, age=33]
Student [name=XJ WANG, age=32]

问：Collection和Collections

Collection是java.util下的接口，它是各种集合类的父接口，继承于它的接口有set及list

Collections是java.util下的类，是针对集合类的一个帮助类，它提供了一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

问：Java集合类框架的最佳实践有哪些？

根据应用的需要正确选择要使用的集合的类型对性能非常重要

(1) 假如元素的大小是固定的，而且能事先知道，我们就应该用Array而不是ArrayList。

(2) 有些集合类允许指定初始容量。因此，如果我们能估计出存储的元素的数目，我们可以设置初始容量来避免重新计算hash值或者是扩容。

(3) 为了类型安全、可读性和健壮性的原因总是要使用泛型。同时，使用泛型还可以避免运行时的ClassCastException。

(4) 使用JDK提供的不变类(immutable class)作为Map的键可以避免为我们自己的类实现hashCode()和equals()方法。

(5) 编程的时候接口优先于实现。

(6) 底层的集合实际上是空的情况下，返回长度是0的集合或者是数组，不要返回null。

问：为什么集合类没有实现Cloneable和Serializable接口？

克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的，因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。

问：泛型

来源：Java笔试面试题整理第八波

泛型在集合中使用广泛，在JDK1.5之后集合框架就全部加入了泛型支持。泛型在编译时期进行严格的类型检查，消除了绝大多数的类型转换。在没有使用泛型之前，我们可以往List集合中添加任何类型的元素数据，因为此时List集合默认的元素类型为Object，而在我们使用的时候需要进行强制类型转换，这个时候如果我们往List中加入了不同类型的元素，很容易导致类型转换异常。

例如：

public static void main(String[] args) {
    List list = new ArrayList();  
    list.add(18);  
    list.add("str");  
    for(Object obj : list){  
        int i = (int) obj;//此处运行后，将会报错  
    }
}

上面代码在编译时不会出错，但在将”str”转换成int类型时，会报ClassCastException (运行时异常，也即非检查性异常)。

泛型允许我们在创建集合时就可以指定元素类型，当加入其他数据类型时，编译不能通过。在我们使用泛型之后，可以避免不必要的转型，以及避免可能出现的ClassCastException。例如：

public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();  
    list.add(18);  
    list.add("str");    //此时，编译就不能通过，报错！！！  
}

类型擦除

泛型只作用于编译阶段，在编译阶段严格检查类型是否匹配，类型检查通过后，JVM会将泛型的相关信息擦出掉(即泛型擦除)，也就是说，成功编译过后的class文件中是不包含任何泛型信息的，泛型信息不会进入到运行时阶段。

class Person<T> {
    private T character;// 人物特征

    public Person(T character) {
        this.character = character;
    }

    public T getCharacter() {
        return character;
    }

    public void setCharacter(T character) {
        this.character = character;
    }
}

public static void main(String[] args) {
    Person<String> p1 = new Person<String>("nice");
    Person<Integer> p2 = new Person<Integer>(18);
    System.out.println("p1--->" + p1.getClass());
    System.out.println("p2--->" + p2.getClass());
}

// 输出：
p1--->class Person
p2--->class Person

虽然我们传入了两种数据类型，但是在编译时并没有生成这两种类型，而都是Person类型，这正是因为我们上面所说的，泛型在编译通过后，确保了类型正确，此后就擦除了相关泛型信息，把所有元素都作为Person数据类型。也就是说，泛型类型在逻辑上我们可以看成是多个不同的数据类型，但是在本质上它只是同一种数据类型。

类型通配符

泛型在编译成功后，泛型信息就会被擦除，变成了同一种类型。那么该如何区分原本具有父子关系的泛型类型呢？

例如：

public static void main(String[] args) {
    Person<Number> p1 = new Person<Number>(12);
    Person<Integer> p2 = new Person<Integer>(18);

    getCharacter(p1);
    getCharacter(p2);// 报错！！！编译不能通过，提示参数类型不符合
}

public static void getCharacter(Person<Number> person) {
    System.out.println(person.getCharacter());
}

Integer是继承自Number的，按照我们的想法，根据Java的多态特性，我们调用getCharacter(p2)应该是没有问题的，但是因为泛型擦除的特点，泛型在编译通过后被擦除了泛型类型，在运行时，JVM根本不知道有Number和Integer这两个类型存在，内存中只会有Person对象存在。这也正是上面不能编译通过的原因。

为了解决这个问题，也就是在使用泛型的时候为了能够体现出父子关系(或者说兼容多态特性)，提出了类型通配符的概念。类型通配符用?来代替参数类型，代表任何类型的父类。例如Person<?>就是Person和Person的父类，而Person和Person是体现不出父类关系的，现在就可以继续使用多态特性了。

public static void main(String[] args) {
    Person<Number> p1 = new Person<Number>(12);
    Person<Integer> p2 = new Person<Integer>(18);

    getCharacter(p1);
    getCharacter(p2);
}

//将参数类型改成通配符之后，我们调用getCharacter(p2)就不会出错了
public static void getCharacter(Person<?> person) {
    System.out.println(person.getCharacter());
}

类型通配符上界

在上面的例子中，我们的本意是getCharacter方法中只能传入数字类型的参数，也就是说希望传入的类型参数是Number类型或它的子类，类型通配符上界提供了这种约束。

定义：Person<? extends Number>，表示我们的参数类型最大是Number类型或者它的子类。

public static void main(String[] args) {
    Person<Number> p1 = new Person<Number>(12);
    Person<Integer> p2 = new Person<Integer>(18);
    Person<String> p3 = new Person<String>("nice");

    getCharacter(p1);
    getCharacter(p2);
    getCharacter(p3); //报错！！！编译不通过，提示参数类型不符合
}

public static void getCharacter(Person<? extends Number> person) {
    System.out.println(person.getCharacter());
}

因为String不是Number的子类，因此上面也就不能编译通过了。

类型通配符下界

定义：Person<? super Number>，表示我们的参数类型最小是Number类型，或者是它的超类类型。

例1：重要的题目

class A {}
class B extends A {}
class C extends A {}
class D extends B {}
Which four statements are true?

(A) The type List<A> is assignable to List.
(B) The type List<B> is assignable to List<A>.
(C) The type List<Object> is assignable to List<?>.
(D) The type List<D> is assignable to List<?extends B>.
(E) The type List<?extends A> is assignable to List<A>.
(F) The type List<Object> is assignable to any List reference.
(G) The type List<?extends B> is assignable to List<?extends A>.

正确答案：ACDG
A正确: 任何使用了泛型的数据类型，都可以赋值给没有使用泛型的数据类型，此时数据类型相当于是Object。例如下面代码可以通过。
    public static void main(String[] args) {
        Person<Number> p1 = new Person<Number>(12);
        Person<Integer> p2 = new Person<Integer>(18);
        Person<String> p3 = new Person<String>("nice");

        getCharacter(p1);
        getCharacter(p2);
        getCharacter(p3);
    }

    public static void getCharacter(Person person) {
        System.out.println(person.getCharacter());
    }
BE错误，CDG正确：由于使用泛型之后，父子关系必须要使用通配符来解决。
F错误：和B一样的错误，虽然Object是任何类型的父类(需要跟A区别开来，A是用没用泛型的比较，这里是都用了泛型之后的比较)，但是使用了泛型后，父子关系要有通配符来体现，例如List<String>不能转化为List<Object>。

问：JDK7中泛型

JDK1.7以后，泛型实例的创建可以通过类型推断来简化 可以去掉new后面部分的泛型类型，只需要用<>就可以了。

例如：

一般情况下，泛型按如下方式使用：

List<String> strList = new ArrayList<String>(); 

在JDK7及以后，可以简化成如下：

List<String> strList = new ArrayList<>();