1. HashMap 排序题，上机题。

已知一个 HashMap<Integer，User>集合， User 有 name（String）和 age（int）属性。请写一个方法实现对HashMap 的排序功能，该方法接收 HashMap<Integer，User>为形参，返回类型为 HashMap<Integer，User>，要求对 HashMap 中的 User 的 age 倒序进行排序。排序时 key=value 键值对不得拆散。

注意：要做出这道题必须对集合的体系结构非常的熟悉。HashMap 本身就是不可排序的，但是该道题偏偏让给HashMap 排序，那我们就得想在 API 中有没有这样的 Map 结构是有序的，LinkedHashMap，对的，就是他，他是Map 结构，也是链表结构，有序的，更可喜的是他是 HashMap 的子类，我们返回 LinkedHashMap<Integer,User>即可，还符合面向接口（父类编程的思想）。

但凡是对集合的操作，我们应该保持一个原则就是能用 JDK 中的 API 就有 JDK 中的 API，比如排序算法我们不应该去用冒泡或者选择，而是首先想到用 Collections 集合工具类。

1. public class HashMapTest {
2. public static void main(String[] args) {
3. HashMap<Integer, User> users = new HashMap<>();
4. users.put(1, new User("张三", 25));
5. users.put(3, new User("李四", 22));
6. users.put(2, new User("王五", 28));
7. System.out.println(users);
8. HashMap<Integer,User> sortHashMap = sortHashMap(users);
9. System.out.println(sortHashMap);
10. /**
11. * 控制台输出内容
12. * {1=User [name=张三, age=25], 2=User [name=王五, age=28], 3=User [name=李四, age=22]}
13. {2=User [name=王五, age=28], 1=User [name=张三, age=25], 3=User [name=李四, age=22]}
14. */
15. }
16.
17. public static HashMap<Integer, User> sortHashMap(HashMap<Integer, User> map) {
18. // 首先拿到 map 的键值对集合
19. Set<Entry<Integer, User>> entrySet = map.entrySet();
20.
21. // 将 set 集合转为 List 集合，为什么，为了使用工具类的排序方法
22. List<Entry<Integer, User>> list = new ArrayList<Entry<Integer, User>>(entrySet);
23. // 使用 Collections 集合工具类对 list 进行排序，排序规则使用匿名内部类来实现
24. Collections.sort(list, new Comparator<Entry<Integer, User>>() {
25.
26. @Override
27. public int compare(Entry<Integer, User> o1, Entry<Integer, User> o2) {
28. //按照要求根据 User 的 age 的倒序进行排
29. return o2.getValue().getAge()-o1.getValue().getAge();
30. }
31. });
32. //创建一个新的有序的 HashMap 子类的集合
33. LinkedHashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User>();
34. //将 List 中的数据存储在 LinkedHashMap 中
35. for(Entry<Integer, User> entry : list){
36. linkedHashMap.put(entry.getKey(), entry.getValue());
37. }
38. //返回结果
39. return linkedHashMap;
40. }
41. }
42.

2. 集合的安全性问题

请问 ArrayList、HashSet、HashMap 是线程安全的吗？如果不是我想要线程安全的集合怎么办？

我们都看过上面那些集合的源码（如果没有那就看看吧），每个方法都没有加锁，显然都是线程不安全的。话又说过来如果他们安全了也就没第二问了。

在集合中 Vector 和 HashTable 倒是线程安全的。你打开源码会发现其实就是把各自核心方法添加上了synchronized 关键字。

Collections 工具类提供了相关的 API，可以让上面那 3 个不安全的集合变为安全的。

1. // Collections.synchronizedCollection(c)
2. // Collections.synchronizedList(list)
3. // Collections.synchronizedMap(m)
4. // Collections.synchronizedSet(s)

上面几个函数都有对应的返回值类型，传入什么类型返回什么类型。打开源码其实实现原理非常简单，就是将集合的核心方法添加上了 synchronized 关键字。

3. ArrayList 内部用什么实现的？

（回答这样的问题，不要只回答个皮毛，可以再介绍一下 ArrayList 内部是如何实现数组的增加和删除的，因为数组在创建的时候长度是固定的，那么就有个问题我们往 ArrayList 中不断的添加对象，它是如何管理这些数组呢？）
ArrayList 内部是用 Object[]实现的。接下来我们分别分析 ArrayList 的构造、add、remove、clear 方法的实现原理。
一、构造函数
1）空参构造

/**
 * Constructs a new {@code ArrayList} instance with zero initial capacity.
 */
 public ArrayList() {
 array = EmptyArray.OBJECT;
}

array 是一个 Object[]类型。当我们 new 一个空参构造时系统调用了 EmptyArray.OBJECT 属性，EmptyArray 仅仅是一个系统的类库，该类源码如下：

public final class EmptyArray {
 private EmptyArray() {}
 public static final boolean[] BOOLEAN = new boolean[0];
 public static final byte[] BYTE = new byte[0];
 public static final char[] CHAR = new char[0];
 public static final double[] DOUBLE = new double[0];
 public static final int[] INT = new int[0];
 public static final Class<?>[] CLASS = new Class[0];
 public static final Object[] OBJECT = new Object[0];
 public static final String[] STRING = new String[0];
 public static final Throwable[] THROWABLE = new Throwable[0];
 public static final StackTraceElement[] STACK_TRACE_ELEMENT = new StackTraceElement[0];
}

也就是说当我们 new 一个空参 ArrayList 的时候，系统内部使用了一个 new Object[0]数组。
2）带参构造 1

/**
 * Constructs a new instance of {@code ArrayList} with the specified
 * initial capacity.
 *
 * @param capacity
 * the initial capacity of this {@code ArrayList}.
 */
 public ArrayList(int capacity) {
 if (capacity < 0) {
 throw new IllegalArgumentException("capacity < 0: " + capacity);
 }
 array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}

该构造函数传入一个 int 值，该值作为数组的长度值。如果该值小于 0，则抛出一个运行时异常。如果等于 0，则使用一个空数组，如果大于 0，则创建一个长度为该值的新数组。

3）带参构造 2

/**
 * Constructs a new instance of {@code ArrayList} containing the elements of
 * the specified collection.
 *
 * @param collection
 * the collection of elements to add.
 */
 public ArrayList(Collection<? extends E> collection) {
 if (collection == null) {
 throw new NullPointerException("collection == null");
 }
 Object[] a = collection.toArray();
 if (a.getClass() != Object[].class) {
 Object[] newArray = new Object[a.length];
 System.arraycopy(a, 0, newArray, 0, a.length);
 a = newArray;
 }
 array = a;
 size = a.length;
 }

如果调用构造函数的时候传入了一个 Collection 的子类，那么先判断该集合是否为 null，为 null 则抛出空指针异常。如果不是则将该集合转换为数组 a，然后将该数组赋值为成员变量 array，将该数组的长度作为成员变量 size。这里面它先判断 a.getClass 是否等于 Object[].class，其实一般都是相等的，我也暂时没想明白为什么多加了这个判断，toArray 方法是 Collection 接口定义的，因此其所有的子类都有这样的方法，list 集合的 toArray 和 Set 集合的 toArray返回的都是 Object[]数组。
这里讲些题外话，其实在看 Java 源码的时候，作者的很多意图都很费人心思，我能知道他的目标是啥，但是不知道他为何这样写。比如对于 ArrayList， array 是他的成员变量，但是每次在方法中使用该成员变量的时候作者都会重新在方法中开辟一个局部变量，然后给局部变量赋值为 array，然后再使用，有人可能说这是为了防止并发修改 array，毕竟 array 是成员变量，大家都可以使用因此需要将 array 变为局部变量，然后再使用，这样的说法并不是都成立的，也许有时候就是老外们写代码的一个习惯而已。

二、add 方法
add 方法有两个重载，这里只研究最简单的那个。

 /**
 * Adds the specified object at the end of this {@code ArrayList}.
 *
 * @param object
 * the object to add.
 * @return always true
 */
 @Override public boolean add(E object) {
 Object[] a = array;
 int s = size;
 if (s == a.length) {
 Object[] newArray = new Object[s +
 (s < (MIN_CAPACITY_INCREMENT / 2) ?
 MIN_CAPACITY_INCREMENT : s >> 1)];
 System.arraycopy(a, 0, newArray, 0, s);
 array = a = newArray;
 }
 a[s] = object;
 size = s + 1;
 modCount++;
 return true;
 }

1、首先将成员变量 array 赋值给局部变量 a，将成员变量 size 赋值给局部变量 s。
2、判断集合的长度 s 是否等于数组的长度（如果集合的长度已经等于数组的长度了，说明数组已经满了，该重新分配新数组了），重新分配数组的时候需要计算新分配内存的空间大小，如果当前的长度小于MIN_CAPACITY_INCREMENT/2（这个常量值是 12，除以 2 就是 6，也就是如果当前集合长度小于 6）则分配 12 个长度，如果集合长度大于 6 则分配当前长度 s 的一半长度。这里面用到了三元运算符和位运算，s >> 1，意思就是将s 往右移 1 位，相当于 s=s/2，只不过位运算是效率最高的运算。
3、将新添加的 object 对象作为数组的 a[s]个元素。
4、修改集合长度 size 为 s+1
5、modCotun++,该变量是父类中声明的，用于记录集合修改的次数，记录集合修改的次数是为了防止在用迭代器迭代集合时避免并发修改异常，或者说用于判断是否出现并发修改异常的。
6、return true，这个返回值意义不大，因为一直返回 true，除非报了一个运行时异常。

三、remove 方法
remove 方法有两个重载，我们只研究 remove（int index）方法。

 /**
 * Removes the object at the specified location from this list.
 *
 * @param index
 * the index of the object to remove.
 * @return the removed object.
 * @throws IndexOutOfBoundsException
 * when {@code location < 0 || location >= size()}
 */
 @Override public E remove(int index) {
 Object[] a = array;
 int s = size;
 if (index >= s) {
 throwIndexOutOfBoundsException(index, s);
 }
 @SuppressWarnings("unchecked")
 E result = (E) a[index];
 System.arraycopy(a, index + 1, a, index, --s - index);
 a[s] = null; // Prevent memory leak
 size = s;
 modCount++;
 return result;
 }

1、先将成员变量 array 和 size 赋值给局部变量 a 和 s。
2、判断形参 index 是否大于等于集合的长度，如果成了则抛出运行时异常
3、获取数组中脚标为 index 的对象 result，该对象作为方法的返回值
4、调用 System 的 arraycopy 函数，拷贝原理如下图所示。

image.png

5、接下来就是很重要的一个工作，因为删除了一个元素，而且集合整体向前移动了一位，因此需要将集合最后一个元素设置为 null，否则就可能内存泄露。
6、重新给成员变量 array 和 size 赋值
7、记录修改次数
8、返回删除的元素（让用户再看最后一眼）

四、clear 方法

 /**
 * Removes all elements from this {@code ArrayList}, leaving it empty.
 *
 * @see #isEmpty
 * @see #size
 */
 @Override public void clear() {
 if (size != 0) {
 Arrays.fill(array, 0, size, null);
 size = 0;
 modCount++;
 }
 }

如果集合长度不等于 0，则将所有数组的值都设置为 null，然后将成员变量 size 设置为 0 即可，最后让修改记录
加 1。

4. 并发集合和普通集合如何区别？

并发集合常见的有 ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentLinkedDeque 等。并发集合
位 于 java.util.concurrent 包 下 ， 是 jdk1.5 之 后 才 有 的 ， 主 要 作 者 是 DougLea（http://baike.baidu.com/view/3141057.htm）完成的。

在 java 中有普通集合、同步（线程安全）的集合、并发集合。普通集合通常性能最高，但是不保证多线程的安全性和并发的可靠性。线程安全集合仅仅是给集合添加了 synchronized 同步锁，严重牺牲了性能，而且对并发的效率就更低了，并发集合则通过复杂的策略不仅保证了多线程的安全又提高的并发时的效率。

参考阅读：
ConcurrentHashMap 是线程安全的 HashMap 的实现，默认构造同样有 initialCapacity 和 loadFactor 属性，
不过还多了一个 concurrencyLevel 属性，三属性默认值分别为 16、0.75 及 16。其内部使用锁分段技术，维持这锁Segment 的数组，在 Segment 数组中又存放着 Entity[]数组，内部 hash 算法将数据较均匀分布在不同锁中。

• put 操作：并没有在此方法上加上 synchronized，首先对 key.hashcode 进行 hash 操作，得到 key 的 hash 值。hash操作的算法和 map也不同，根据此 hash 值计算并获取其对应的数组中的 Segment对象(继承自ReentrantLock)，接着调用此 Segment 对象的 put 方法来完成当前操作。ConcurrentHashMap 基于 concurrencyLevel 划分出了多个 Segment 来对 key-value 进行存储，从而避免每次 put 操作都得锁住整个数组。在默认的情况下，最佳情况下可允许 16 个线程并发无阻塞的操作集合对象，尽可能地减少并发时的阻塞现象。
• get(key)：首先对 key.hashCode 进行 hash 操作，基于其值找到对应的 Segment 对象，调用其 get 方法完成当前操作。而 Segment 的 get 操作首先通过 hash 值和对象数组大小减 1 的值进行按位与操作来获取数组上对应位置的HashEntry。在这个步骤中，可能会因为对象数组大小的改变，以及数组上对应位置的 HashEntry 产生不一致性，那么 ConcurrentHashMap 是如何保证的？

对象数组大小的改变只有在 put 操作时有可能发生，由于 HashEntry 对象数组对应的变量是 volatile 类型
的，因此可以保证如 HashEntry 对象数组大小发生改变，读操作可看到最新的对象数组大小。在获取到了 HashEntry 对象后，怎么能保证它及其 next 属性构成的链表上的对象不会改变呢？这点ConcurrentHashMap 采用了一个简单的方式，即 HashEntry 对象中的 hash、key、next 属性都是 final 的，这也就意味着没办法插入一个 HashEntry 对象到基于 next 属性构成的链表中间或末尾。这样就可以保证当获取到 HashEntry对象后，其基于 next 属性构建的链表是不会发生变化的。

ConcurrentHashMap 默认情况下采用将数据分为 16 个段进行存储，并且16 个段分别持有各自不同的锁
Segment，锁仅用于 put 和 remove 等改变集合对象的操作，基于 volatile 及 HashEntry 链表的不变性实现了读取的不加锁。这些方式使得 ConcurrentHashMap 能够保持极好的并发支持，尤其是对于读远比插入和删除频繁的 Map而言，而它采用的这些方法也可谓是对于 Java 内存模型、并发机制深刻掌握的体现。

5. List 的三个子类的特点

ArrayList 底层结构是数组,底层查询快,增删慢。
LinkedList 底层结构是链表型的,增删快,查询慢。
voctor 底层结构是数组 线程安全的,增删慢,查询慢。

6. List 和 Map、Set 的区别

6.1 结构特点

• List 和 Set 是存储单列数据的集合，Map 是存储键和值这样的双列数据的集合；
• List 中存储的数据是有顺序，并且允许重复；Map 中存储的数据是没有顺序的，其键是不能重复的，它的值是可以有重复的，Set 中存储的数据是无序的，且不允许有重复，但元素在集合中的位置由元素的 hashcode 决定，位置是固定的（Set 集合根据 hashcode 来进行数据的存储，所以位置是固定的，但是位置不是用户可以控制的，所以对于用户来说 set 中的元素还是无序的）；

6.2 实现类

• List 接口有三个实现类（LinkedList：基于链表实现，链表内存是散乱的，每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快，查找慢；ArrayList：基于数组实现，非线程安全的，效率高，便于索引，但不便于插入删除；Vector：基于数组实现，线程安全的，效率低）。
• Map 接口有三个实现类（HashMap：基于 hash 表的 Map 接口实现，非线程安全，高效，支持 null 值和 null键；HashTable：线程安全，低效，不支持 null 值和 null 键；LinkedHashMap：是 HashMap 的一个子类，保存了记录的插入顺序；SortMap 接口：TreeMap，能够把它保存的记录根据键排序，默认是键值的升序排序）。
• Set 接口有两个实现类（HashSet：底层是由 HashMap 实现，不允许集合中有重复的值，使用该方式时需要重写 equals()和 hashCode()方法；LinkedHashSet：继承与 HashSet，同时又基于 LinkedHashMap 来进行实现，底层使用的是 LinkedHashMp）。

6.3 区别

• List 集合中对象按照索引位置排序，可以有重复对象，允许按照对象在集合中的索引位置检索对象，例如通过list.get(i)方法来获取集合中的元素；
• Map 中的每一个元素包含一个键和一个值，成对出现，键对象不可以重复，值对象可以重复；
• Set 集合中的对象不按照特定的方式排序，并且没有重复对象，但它的实现类能对集合中的对象按照特定
  的方式排序，例如 TreeSet 类，可以按照默认顺序，也可以通过实现 Java.util.Comparator<Type>接口来自定义排序方式。

7. HashMap 和 HashTable 有什么区别?

• HashMap 是线程不安全的,HashMap 是Map 的一个子接口,是将键映射到值得对象,不允许键值重复,允许空键和空值;由于非线程安全,HashMap 的效率要较 HashTable 的效率高一些.
• HashTable 是线程安全的一个集合,不允许 null 值作为一个 key 值或者 Value 值;
• HashTable 是 sychronize,多个线程访问时不需要自己为它的方法实现同步,而 HashMap 在被多个线程访问的时候需要自己为它的方法实现同步

8. 数组和链表分别比较适合用于什么场景，为什么？

8.1 数组和链表简介

在计算机中要对给定的数据集进行若干处理，首要任务是把数据集的一部分（当数据量非常大时，可能只能一部分一部分地读取数据到内存中来处理）或全部存储到内存中，然后再对内存中的数据进行各种处理。
例如，对于数据集 S{1，2，3，4，5，6}，要求 S 中元素的和，首先要把数据存储到内存中，然后再将内存中的数据相加。
当内存空间中有足够大的连续空间时，可以把数据连续的存放在内存中，各种编程语言中的数组一般都是按这种方式存储的（也可能有例外），如图 1（b）；当内存中只有一些离散的可用空间时，想连续存储数据就非常困难了，这时能想到的一种解决方式是移动内存中的数据，把离散的空间聚集成连续的一块大空间，如图 1（c）所示，这样做当然也可以，但是这种情况因为可能要移动别人的数据，所以会存在一些困难，移动的过程中也有可能会把一些别人的重要数据给丢失。另外一种，不影响别人的数据存储方式是把数据集中的数据分开离散地存储到这些不连续空间中，如图（d）。这时为了能把数据集中的所有数据联系起来，需要在前一块数据的存储空间中记录下一块数据的地址，这样只要知道第一块内存空间的地址就能环环相扣地把数据集整体联系在一起了。C/C++中用指针实现的链表就是这种存储形式。

image.png

由上可知，内存中的存储形式可以分为连续存储和离散存储两种。因此，数据的物理存储结构就有连续存储和离散存储两种，它们对应了我们通常所说的数组和链表。

8.2 数组和链表的区别

• 数组是将元素在内存中连续存储的；它的优点：因为数据是连续存储的，内存地址连续，所以在查找数据的时候效率比较高；它的缺点：在存储之前，我们需要申请一块连续的内存空间，并且在编译的时候就必须确定好它的空间的大小。在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的，当数据量比较大的时候，有可能会出现越界的情况，数据比较小的时候，又有可能会浪费掉内存空间。在改变数据个数时，增加、插入、删除数据效率比较低；

• 链表是动态申请内存空间，不需要像数组需要提前申请好内存的大小，链表只需在用的时候申请就可以，根据需要来动态申请或者删除内存空间，对于数据增加和删除以及插入比数组灵活。还有就是链表中数据在内存中可以在任意的位置，通过应用来关联数据（就是通过存在元素的指针来联系）

8.3 链表和数组使用场景

数组应用场景：数据比较少；经常做的运算是按序号访问数据元素；数组更容易实现，任何高级语言都支持；构建的线性表较稳定。
链表应用场景：对线性表的长度或者规模难以估计；频繁做插入删除操作；构建动态性比较强的线性表。
参考博客：http://blog.csdn.net/u011277123/article/details/53908387

8.4 跟数组相关的面试题

用面向对象的方法求出数组中重复 value 的个数，按如下个数输出：
1 出现：1 次
3 出现：2 次
8 出现：3 次
2 出现：4 次
int[] arr = {1,4,1,4,2,5,4,5,8,7,8,77,88,5,4,9,6,2,4,1,5};

public static void main(String[] args){
        int[] arr = {1,4,1,4,2,5,4,5,8,7,8,77,88,5,4,9,6,2,4,1,5};
        Map<Integer, Integer> map = new HashMap<>();
        for (int value : arr) {
            if (map.containsKey(value)) {
                map.put(value, map.get(value) + 1);
            } else {
                map.put(value, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            System.out.println(entry.getKey() + "出现:" + entry.getValue() + "次");
        }
    }

9. Java 中 ArrayList 和 Linkedlist 区别？

• ArrayList 和 Vector 使用了数组的实现，可以认为 ArrayList 或者 Vector 封装了对内部数组的操作，比如向数组中添加，删除，插入新的元素或者数据的扩展和重定向。
• LinkedList 使用了循环双向链表数据结构。与基于数组的 ArrayList 相比，这是两种截然不同的实现技术，这也决定了它们将适用于完全不同的工作场景。

LinkedList 链表由一系列表项连接而成。一个表项总是包含 3 个部分：元素内容，前驱表和后驱表，如图所示：

image.png

在下图展示了一个包含 3 个元素的 LinkedList 的各个表项间的连接关系。在 JDK 的实现中，无论 LikedList 是否为空，链表内部都有一个 header 表项，它既表示链表的开始，也表示链表的结尾。表项 header 的后驱表项便是链表中第一个元素，表项 header 的前驱表项便是链表中最后一个元素。

image.png

10. List a=new ArrayList()和 ArrayList a =new ArrayList()的区别？
    List list = new ArrayList();这句创建了一个 ArrayList 的对象后上溯到了 List。此时它是一个 List 对象了，有些
    ArrayList 有但是 List 没有的属性和方法，它就不能再用了。而 ArrayList list=new ArrayList();创建一对象则保留了ArrayList 的所有属性。 所以需要用到 ArrayList 独有的方法的时候不能用前者。实例代码如下：

1．List list = new ArrayList();
2．ArrayList arrayList = new ArrayList();
3．list.trimToSize(); //错误，没有该方法。
4．arrayList.trimToSize(); //ArrayList 里有该方法。

11. 要对集合更新操作时，ArrayList 和 LinkedList 哪个更适合？

1. ArrayList 是实现了基于动态数组的数据结构，LinkedList 基于链表的数据结构。
2. 如果集合数据是对于集合随机访问 get 和 set，ArrayList 绝对优于 LinkedList，因为 LinkedList 要移动指针。
3. 如果集合数据是对于集合新增和删除操作 add 和 remove，LinedList 比较占优势，因为 ArrayList 要移动数
   据。

ArrayList 和 LinkedList 是两个集合类，用于存储一系列的对象引用(references)。例如我们可以用 ArrayList 来存储一系列的 String 或者 Integer。那 么 ArrayList 和 LinkedList 在性能上有什么差别呢？什么时候应该用 ArrayList什么时候又该用 LinkedList 呢？

一．时间复杂度

首先一点关键的是，ArrayList 的内部实现是基于基础的对象数组的，因此，它使用 get 方法访问列表中的任意一个元素时(random access)，它的速度要比 LinkedList 快。LinkedList 中的 get 方法是按照顺序从列表的一端开始检查，直到另外一端。对 LinkedList 而言，访问列表中的某个指定元素没有更快的方法了。

假设我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是 ArrayList 类型的也可能是 LinkedList类型的，现在我们对这个列表来进行二分查找(binary search)，比较列表是 ArrayList 和 LinkedList 时的查询速度，看下面的程序：

1．public class TestList{
2． public static final int N=50000; //50000 个数
3． public static List values; //要查找的集合
4． //放入 50000 个数给 value；
5． static{
6． Integer vals[]=new Integer[N];
7． Random r=new Random();
8． for(int i=0,currval=0;i<N;i++)...{
9． vals=new Integer(currval);
10． currval+=r.nextInt(100)+1;
11． }
12． values=Arrays.asList(vals);
13． }
14． //通过二分查找法查找
15． static long timeList(List lst){
16． long start=System.currentTimeMillis();
17． for(int i=0;i<N;i++)...{
18． int index=Collections.binarySearch(lst, values.get(i));
19． if(index!=i)
20． System.out.println("***错误***");
21． }
22． return System.currentTimeMillis()-start;
23． }
24． public static void main(String args[])...{
25． System.out.println("ArrayList 消耗时间："+timeList(new ArrayList(values)));
26． System.out.println("LinkedList 消耗时间："+timeList(new LinkedList(values)));
27． }
28．}

得到的输出是：

1. ArrayList 消耗时间：15
2. LinkedList 消耗时间：2596

这个结果不是固定的，但是基本上 ArrayList 的时间要明显小于 LinkedList 的时间。因此在这种情况下不宜用
LinkedList。二分查找法使用的随机访问(random access)策略，而 LinkedList 是不支持快速的随机访问的。对一个LinkedList 做随机访问所消耗的时间与这个 list 的大小是成比例的。而相应的，在 ArrayList 中进行随机访问所消耗的时间是固定的。

这是否表明 ArrayList 总是比 LinkedList 性能要好呢？这并不一定，在某些情况下 LinkedList 的表现要优于
ArrayList，有些算法在 LinkedList 中实现 时效率更高。比方说，利用 Collections.reverse 方法对列表进行反转时，其性能就要好些。看这样一个例子，加入我们有一个列表，要对其进行大量的插入和删除操作，在这种情况下 LinkedList就是一个较好的选择。请看如下一个极端的例子，我们重复的在一个列表的开端插入一个元素：

1．import java.util.*;
2．public class ListDemo {
3． static final int N=50000;
4． static long timeList(List list){
5． long start=System.currentTimeMillis();
6． Object o = new Object();
7． for(int i=0;i<N;i++)
8． list.add(0, o);
9． return System.currentTimeMillis()-start;
10． }
11． public static void main(String[] args) {
12． System.out.println("ArrayList 耗时："+timeList(new ArrayList()));
13． System.out.println("LinkedList 耗时："+timeList(new LinkedList()));
14． }
15．}

这时我的输出结果是

1. ArrayList 耗时：2463
2. LinkedList 耗时：15

二．空间复杂度

在 LinkedList 中有一个私有的内部类，定义如下：

1．private static class Entry {
2． Object element;
3． Entry next;
4． Entry previous;
5． }

每个 Entry 对象 reference 列表中的一个元素，同时还有在 LinkedList 中它的上一个元素和下一个元素。一个
有 1000 个元素的 LinkedList 对象将有 1000 个链接在一起 的 Entry 对象，每个对象都对应于列表中的一个元素。这样的话，在一个 LinkedList 结构中将有一个很大的空间开销，因为它要存储这 1000 个Entity 对象的相关信息。

ArrayList 使用一个内置的数组来存储元素，这个数组的起始容量是 10.当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长 50%。 这就意味着，如果你有一个包含大量元素的 ArrayList 对象，那么最终将有很大的空间会被浪费掉，这个浪费是由 ArrayList 的工作方式本身造成 的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。如果我们知道一个 ArrayList 将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过 trimToSize 方法在 ArrayList 分配完毕之后去掉浪 费掉的空间。

三．总结

ArrayList 和 LinkedList 在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：

1. 对 ArrayList 和 LinkedList 而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList 而言，主
   要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对 LinkedList 而言，这个开销是统一的，分配一个内部 Entry 对象。
2. 在 ArrayList 的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在 LinkedList 的中间
   插入或删除一个元素的开销是固定的。
3. LinkedList 不支持高效的随机元素访问。
4. ArrayList 的空间浪费主要体现在在 list 列表的结尾预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList 会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用 LinkedList 了。

12. 请用两个队列模拟堆栈结构（2017-2-24）

两个队列模拟一个堆栈，队列是先进先出，而堆栈是先进后出。模拟如下
队列 a 和 b
（1）入栈：a 队列为空，b 为空。例：则将”a,b,c,d,e”需要入栈的元素先放 a 中，a 进栈为”a,b,c,d,e”
（2）出栈：a 队列目前的元素为”a,b,c,,d,e”。将 a 队列依次加入 Arraylist 集合 a 中。以倒序的方法，将 a 中的集合取出，放入 b 队列中，再将 b 队列出列。代码如下：

1． public static void main(String[] args) {
2． Queue<String> queue = new LinkedList<String>(); //a 队列
3． Queue<String> queue2=new LinkedList<String>(); //b 队列
4． ArrayList<String> a=new ArrayList<String>(); //arrylist 集合是中间参数
5． //往 a 队列添加元素
6． queue.offer("a");
7． queue.offer("b");
8． queue.offer("c");
9． queue.offer("d");
10． queue.offer("e");
11． System.out.print("进栈：");
12． //a 队列依次加入 list 集合之中
13． for(String q : queue){
14． a.add(q);
15． System.out.print(q);
16． }
17． //以倒序的方法取出（a 队列依次加入 list 集合）之中的值，加入 b 对列
18． for(int i=a.size()-1;i>=0;i--){
19． queue2.offer(a.get(i));
20． }
21． //打印出栈队列
22． System.out.println("");
23． System.out.print("出栈："); 
24． for(String q : queue2){
25． System.out.print(q);
26． }
27． }

打印结果为（遵循栈模式先进后出）：

进栈：a b c d e
出栈：e d c b a

13. Collection 和 Map 的集成体系

image.png

image.png

14. Map 中的 key 和 value 可以为 null 么？

HashMap 对象的 key、value 值均可为 null。
HahTable 对象的 key、value 值均不可为 null。
且两者的的 key 值均不能重复，若添加 key 相同的键值对，后面的 value 会自动覆盖前面的 value，但不会报错。
测试代码如下：

1. public class Test {
2.
3. public static void main(String[] args) {
4. Map<String, String> map = new HashMap<String, String>();//HashMap 对象
5. Map<String, String> tableMap = new Hashtable<String, String>();//HashTable 对象
6.
7. map.put(null, null);
8. System.out.println("hashMap 的[key]和[value]均可以为 null:" + map.get(null));
9.
10. try {
11. tableMap.put(null, "3");
12. System.out.println(tableMap.get(null));
13. } catch (Exception e) {
14. System.out.println("【ERROR】：hashTable 的[key]不能为 null");
15. }
16.
17. try {
18. tableMap.put("3", null); 
19. System.out.println(tableMap.get("3"));
20. } catch (Exception e) {
21. System.out.println("【ERROR】：hashTable 的[value]不能为 null");
22. }
23. }
24.
25. }

运行结果：

hashMap 的[key]和[value]均可以为 null:null
【ERROR】：hashTable 的[key]不能为 null
【ERROR】：hashTable 的[value]不能为 null