2018-09-13 集合框架

1 集合和数组的不同点和相同点

共同点：都是存放数据的容器。
不同点：
1.数组长度不可变，集合长度可变
2.数组可放基本类型和引用类型；而集合只能放引用类型
3.数组所有的元素类型必须一致；集合元素类型可变
4.数组没有复写toString；集合复写了toString（输出中括号和所有元素）
5.数组有序可重复；集合（除list外）无序不可重复。

2 泛型

面试题

1 java中的泛型是什么？使用泛型的好处是什么？
答案：
1、泛型是一种参数化类型的机制。它可以使得代码使用于各种类型，从而编写更加通用的代码。
2、泛型是一种编译时类型确认机制。它提供了编译期的类型安全，确保在泛型类型上只能使用正确类型的对象，避免了在运行时出现ClassCastException。

2 Java的泛型是如何工作的？什么是类型檫除？
1、泛型的正常工作是依赖编译器在编译源码的时候，先进行类型检查，然后进行类型擦除并且在类型参数出现的地方插入强制转换的相关指令实现的。
2、编译器的编译时擦除了所有类型相关的信息，所以在运行时不存在任何类型相关的信息。例如，List<String>在运行时仅有一个List类型来表示。
3、为什么要进行擦除？为了避免类型膨胀。

3 Collection接口

• Collection接口是List接口和Set接口的父接口。
• Iterator接口是对 collection 进行迭代的迭代器。

3.1 List接口

• 有序可重复
  -重复：看哈希地址，不看实际地址。（完equals相同，哈希地址也会相同）
• 实现类：ArrayList，LinkedList，Vector。

ArrayList

底层采用的是数组来存储数据，适合查找，效率高；但插入删除不方便。

LinkedList

底层采用双向链表，适合增删改，方便；查找不方便。

Vector

数据结构与ArrayList相同，采用数组。

ArrayList和Vector区别：
ArrayList线程不安全，查找效率高；而Vector线程安全，效率低。

3.2 Set接口

• 无序不可重复。
• 子接口：SortedSet。
• 实现类：HashSet，LinkedHashSet，TreeSet。

SortedSet接口

底层是一个HashMap，是哈希表。

HashSet类

底层就是哈希表。

TreeSet

• 拥有比较的功能。是有序的。

往TreeSet类中放入的元素必须是实现了Comparable接口类型的数据。实现了Comparable接口的元素会自动调用compareTo方法。所有这些元素都必须是可互相比较的。存储进去的元素可以按照元素的大小自动排序。如果存放的元素不实现Comparable接口，则TreeSet不会进行排序。

4 Map接口

• key和value都是Object。key是无序不可重复的。

• Map的存储结构是哈希表。（一维数组加单向链表）

• Map的实现类和子接口中key集存储形式和对应Set集合中元素的存储形式完全相同。

• 子接口：SortedMap

  • 实现类：TreeMap

• 实现类：HashMap，HashTable

SortedMap接口

• SortedMap中的key等同于SortedSet。

TreeMap类

• TreeSet类实现了SortedMap接口。
• key值是有序的。TreeMap的key就是一个TreeSet。

HashMap类

• key值是无序的。
• 线程不安全的。性能高。
• 此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。
• HashMap有一个子类LinkedHashMap。该类底层用双向链表实现，可以维护key-value的次序，使得迭代顺序和插入顺序保持一致。

Hashtable类

• 线程安全的。性能低。
• key和value都不允许为null。如果试图把null放进Hashtable中，将会引发NullPointerException异常。
• 除了这两点不同，与HashMap没什么不同。

与Vector类似，尽量少用Hashtable实现类，即使需要创建线程安全的Map实现类，也可以通过Collections工具类把HashMap变成线程安全的，无需使用Hashtable实现类。

HashMap和Hashtable区别：
1 线程是否安全
2 key和value是否允许为null。

面试题

1 HashMap中的put方法和get方法在内存中是如何实现的？

put方法：
首先放入第一个元素，元素的key调用hashCode方法得到哈希值，这个值就是一维数组的下标，就是桶的位置。向桶的单向链表中插入该元素。
放入第二个元素，key调用hashCode方法得到哈希值，发现与第一个元素的哈希值是一样的，说明在同一个桶中，之后调用equals方法，比较第一个元素的key值和第二个元素的key值，看是否相同。如果是true，则第二个元素覆盖第一个元素而存在，键值对entry会发生变化；如果返回false，则把第二个元素插入到链表头（即把最新的元素放到链表头），旧的数据会被最新的元素的next变量引用着。
get方法：
通过key调用hashCode方法，算出元素在数组中的下标（即找到桶的位置），之后key通过调用equals方法找与寻找key相同的对应的节点。

2、Java中ArrayList和LinkedList区别。

• 1. ArrayList底层是基于数组实现的，而LinkedList底层基于循环双向链表实现的。
• 2. 对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
• 3. 对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

3 set为什么能够保证唯一性，了解集合怎么去重？

？？？？？
底层实现了HashMap
对于HashSet中保存的对象，主要要正确重写equals方法和hashCode方法，以保证放入Set对象的唯一性
虽说是Set是对于重复的元素不放入，倒不如直接说是底层的Map直接把原值替代了（这个Set的put方法的返回值真有意思）
HashSet没有提供get()方法，愿意是同HashMap一样，Set内部是无序的，只能通过迭代的方式获得

4 HashMap与Hashtable的区别与联系。

区别：1、线程是否安全与效率高低：HashMap
是线程不安全的，效率高；而Hashtable是线程安全的，效率低。
2、是否允许为null：HashMap允许key和value为null，而Hashtable不允许。

5 Hashtable和ConCurrentHashMap的区别。

答案1：
参考：https://www.cnblogs.com/sikewang/p/5542026.html
Hashtable是synchronized，但是ConcurrentHashMap的同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。
ConCurrentHashMap提供更强的线程安全性。
答案2：
参考：https://www.cnblogs.com/supertang/p/4149786.html
ConcurrentHashMap和Hashtable主要区别就是围绕着锁的粒度以及如何锁。
1、Hashtable的实现方式--锁整个hash表。
2、ConcurrentHashMap的实现方式--锁桶。而且 只有写线程才需要锁定，而读线程几乎不受限制，大大提升并发性。

6 Java集合类框架的基本接口有哪些？

Collection：代表一组对象，每个对象都是它的子元素。
Set：不包括重复元素的Collection。
List：有序可重复的Collection。
Map：键值对。

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

1、HashMap基于哈希原理，通过put和get发存储和获取对象。当将键值对传递给put方法时，它调用键对象的hashCode方法来计算hashcode，然后找到bucket位置来存储值对象。
2、当获取对象时，通过键对象的equals方法找到正确的键值对，然后返回值对象。
3、HashMap使用LinkedList来解决碰撞问题，当发生碰撞了，对象将会存储在下一个节点中。HashMap在每个LinkedList节点中存储键值对对象。
4、当两个不同的键对象的hashcode相同时会发生什么？他们会存储在同一个bucket位置的LinkedList中。可以通过键对象的equals方法用来找到键值对。

HashMap的工作原理？

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用 hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。

“当两个对象的hashcode相同会发生什么？”

因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用LinkedList存储对象，这个 Entry(包含有键值对的Map.Entry对象)会存储在LinkedList中。

“如果两个键的hashcode相同，你如何获取值对象？”

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，找到bucket位置之后，会调用key.equals()方法去找到链表中正确的节点，最终找到要找的值对象。

“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”

capacity：桶的数量
size：链表元素的个数大小
负载因子=size/capacity
默认负载因子为0.75
默认初始化容量：16
负载因子越大，碰撞多。

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时 候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放 入新的bucket数组中。

8 集合类的扩容？

参考：https://www.jianshu.com/p/29c3cdeaa410