5.HashSet、Set、Hash算法、List、LinkedList、ArrayList、Map、Collections

HashSet、Set、Hash算法、List、LinkedList、ArrayList、Map、Collections
包括我之前对数据结构的一些总结。树是从别人那里复制过来的，写的很详细。
还有网上一篇《40个Java集合面试问题和答案》，写的也很全面， 链接地址

1.HashSet和TreeSet有什么区别
2.HashSet 内部是如何工作的
3.WeakHashMap 是怎么工作的？
4.Set 里的元素是不能重复的，那么用什么方法来区分重复与否呢？是用 == 还是 equals()？ 它们有何区别?
5.TreeMap 是采用什么树实现的？TreeMap、HashMap、LindedHashMap的区别。
6.TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？
7.一个已经构建好的 TreeSet，怎么完成倒排序。
8.EnumSet 是什么
9.Hashcode 的作用
10.简述一致性 Hash 算法
11.有没有可能 两个不相等的对象有相同的 hashcode？当两个对象 hashcode 相同怎么办？如何获取值对象
12.为什么在重写 equals 方法的时候需要重写 hashCode 方法？equals与 hashCode 的异同点在哪里
13.a.hashCode() 有什么用？与 a.equals(b) 有什么关系
14.hashCode() 和 equals() 方法的重要性体现在什么地方
15.Object有哪些公用方法？Object类hashcode,equals 设计原则？ sun为什么这么设计？Object类的概述
16.如何在父类中为子类自动完成所有的 hashcode 和 equals 实现？这么做有何优劣。
17.可以在 hashcode() 中使用随机数字吗？
18.LinkedHashMap 和 PriorityQueue 的区别是什么
19.List, Set, Map三个接口，存取元素时各有什么特点
20.List, Set, Map 是否继承自 Collection 接口
21.遍历一个 List 有哪些不同的方式
22.LinkedList 是单向链表还是双向链表
23.LinkedList 、 ArrayList、Vector 有什么区别
24.描述下 Java 中集合（Collections），接口（Interfaces），实现（Implementations）的概念。
25.插入数据时，ArrayList, LinkedList, Vector谁速度较快？
26.ArrayList 和 HashMap 的默认大小是多少
27.Set，List，Map的区别，什么场景下使用
28.ArrayList如何实现扩容
29.Array 和 ArrayList 有何区别？什么时候更适合用Array
30.Map 接口提供了哪些不同的集合视图
31.为什么 Map 接口不继承 Collection 接口
32.介绍Java中的Collection FrameWork。集合类框架的基本接口有哪些
33.集合类框架的最佳实践有哪些
34.为什么 Collection 不从 Cloneable 和 Serializable 接口继承
35.什么是 B+树，B-树，列出实际的使用场景。

个人总结：

HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
java8改成 数组+链表+红黑树 的数据结构

Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

LinkedHashMap：LinkedHashMap是HashMap的一个子类，Entry是双向链表，按访问顺序迭代，访问多的放到链表尾。

TreeMap：TreeMap实现SortedMap接口，底层红黑树数据结构，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

TreeSet：树集，底层通过TreeMap实现，有序非同步集合，用红黑树数据结构，每次添加到树中时，都会添加到正确位置，迭代器可以按排好的顺序访问每个元素，比散列表插入慢，查询快。
可以实现Comparable接口的compareTo()方法在对象内实现比较方法，或者把Comparator对象传递给TreeSet构造器告诉树集使用不同的比较方法。

priority queue：优先级队列，可以任意顺序插入，但是按排序顺序检索，数据结构用堆（heap）自我调整的二叉树，add和remove操作会把最小的元素移动到根，非线程安全。

LinkedHashSet：用适配器模式包装了LinkedHashMap。

WeekHashMap：key用弱引用，与GC协同合作可以删除键值对。

EnumMap：是一个键类型为枚举类型的映射表，没有公共构造器可以使用静态工厂方法构造，在构造器中需要指定键类型。

IdentityHashMap：标志散列映射表，散列值用System.identityHashCode计算，是Obeject.hashCode用对象的内存地址计算散列码时所使用的方式，IdentityHashMap比较对象用==，不同键的对象即使内容相同也会被视为不同的对象，实现对象遍历算法时（如对象序列化）时，可使用这个类跟踪每个对象的遍历情况。

可以使用Collections.synchronizedCollection/Map/Set/List 等实现对集合的同步

Iterator可用来遍历Set和List集合,但是ListIterator只能用来遍历List。
Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。
ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引。

二叉树：（遍历按根节点遍历顺序分前中后）
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
特点：排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插入节点集本身是大到小排列）；或所有节点只有右节点（如果插入节点集本身是小到大排列）。在这种情况下，排序二叉树就变成了普通链表，其检索效率就会很差。

红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

ConcurrentHashMap
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素， 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。

java8 ：
摒弃了Segment（锁段）的概念，而是启用了一种全新的方式实现,利用CAS算法。它沿用了与它同时期的HashMap版本的思想，底层依然由 数组+链表+红黑树 的方式思想，但是为了做到并发，又增加了很多辅助的类，例如TreeBin，Traverser等对象内部类。

答案：

1.HashSet和TreeSet有什么区别

相同点：
单列集合，元素不可重复
不同点
1. 底层存储的数据结构不同
    HashSet底层用的是HashMap哈希表结构存储，而TreeSet底层用的是TreeMap树结构存储
2.存储时保证数据唯一性依据不同
   HashSet是通过复写hashCode()方法和equals()方法来保证的，而HashSet通过Compareable接口的compareTo()方法来保证的
3.有序性不一样
 HashSet无序，TreeSet有序
 存储原理：
    HashSet:底层数据结构是哈希表，本质就是对哈希值的存储，通过判断元素的hashCode方法和equals方法来保证元素的唯一性，当hashCode值不相同，就直接存储了，不用在判断equals了，当hashCode值相同时，会在判断一次euqals方法的返回值是否为true，如果为true则视为用一个元素，不用存储，如果为false，这些相同哈希值不同内容的元素都存放一个桶里（当哈希表中有一个桶结构，每一个桶都有一个哈希值）
  TreeSet:底层的数据结构是二叉树，可以对Set集合中的元素进行排序,这种结构，可以提高排序性能, 根据比较方法的返回值确定的,只要返回的是0.就代表元素重复

2.HashSet 内部是如何工作的

HashSet 的内部采用 HashMap来实现。由于 Map 需要 key 和 value，所以所有 key 的都有一个默认 value。类似于 HashMap，HashSet 不允许重复的 key，只允许有一个null key，意思就是 HashSet 中只允许存储一个 null 对象。

3.WeakHashMap 是怎么工作的

WeakHashMap实现了Map接口，是HashMap的一种实现，他使用弱引用作为内部数据的存储方案，WeakHashMap可以作为简单缓存表的解决方案，当系统内存不够的时候，垃圾收集器会自动的清除没有在其他任何地方被引用的键值对。

4.Set 里的元素是不能重复的，那么用什么方法来区分重复与否呢？是用 == 还是 equals()？ 它们有何区别?

contains(Object o)方法即可，网上说的是iterator()方法来区分重复与否。equals()是判读两个Set是否相等。
equals()和==方法决定引用值是否指向同一对象equals()在类中被覆盖，为的是当两个分离的对象的内容和类型相配的话，返回真值

5.TreeMap 是采用什么树实现的？TreeMap、HashMap、LindedHashMap的区别。

红黑树，
(1).HashMap里面存入的键值对在取出的时候是随机的,也是我们最常用的一个Map.它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。  
(2).TreeMap取出来的是排序后的键值对。但如果您要搜索按自然顺序或自定义顺序遍历键，那么TreeMap会更好。  
(3).LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现.  (应用场景：购物车等需要顺序的

6.TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？

TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。
TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。
Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象必须实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

7.一个已经构建好的 TreeSet，怎么完成倒排序。 参考链接

通过TreeSet构造函数传入一个比较器，指定比较器进行排序为原排序的倒叙。
TreeSet的自然排序是根据集合元素的大小，TreeSet将他们以升序排列。如果需要实现定制排序，例如降序，则可以使用Comparator接口。该接口里包含一个int compare（T o1，T o2）方法，该方法用于比较o1和o2的大小。
如果需要实现定制排序，则需要在创建TreeSet集合对象时，并提供一个Comparator对象与该TreeSet集合关联，由该Comparator对象负责集合元素的排序逻辑。

8.EnumSet 是什么 参考链接

是一个键类型为枚举类型的映射表，没有公共构造器可以使用静态工厂方法构造，在构造器中需要指定键类型。

9.Hashcode 的作用 参考链接

(1)、HashCode的存在主要是为了查找的快捷性，HashCode是用来在散列存储结构中确定对象的存储地址的
(2)、如果两个对象equals相等，那么这两个对象的HashCode一定也相同
(3)、如果对象的equals方法被重写，那么对象的HashCode方法也尽量重写
(4)、如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置

10.简述一致性 Hash 算法 参考链接

通过环形Hash空间把数据、机器等通过一定的hash算法处理后映射到环上，通过虚拟节点保证平衡性
一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：
1、平衡性(Balance)
2、单调性(Monotonicity)
3、分散性(Spread)
4、负载(Load)
普通的哈希算法（也称硬哈希）采用简单取模的方式，将机器进行散列，这在cache环境不变的情况下能取得让人满意的结果，但是当cache环境动态变化时，这种静态取模的方式显然就不满足单调性的要求（当增加或减少一台机子时，几乎所有的存储内容都要被重新散列到别的缓冲区中）。
一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。当有一个写入缓存的请求到来时，计算Key值k对应的哈希值Hash(k)，如果该值正好对应之前某个机器节点的Hash值，则直接写入该机器节点，如果没有对应的机器节点，则顺时针查找下一个节点，进行写入，如果超过2^32还没找到对应节点，则从0开始查找(因为是环状结构)。  

11.有没有可能 两个不相等的对象有相同的 hashcode？当两个对象 hashcode 相同怎么办？如何获取值对象 参考链接

有可能。hashcode相同也称为hash碰撞，不同场景由不同策略：JDK中hashcode相等equels()方法不一定相等，hashMap用链表解决hash冲突。
值对象（Value Object）模式：
针对一些数据对象，我们更强调的是这个对象的值而不是这个对象本身的时候，就可以使用值对象模式。意思就是两个对象判定相等的时候应该是两个对象的"值"相等，而不是它俩必须是同一个对象。在编写值对象模式的时候，应该注意以下几点（以java为例）：
1、必须重写equals()、hashCode()，且重写的原则是两个对象的"值"相等的化，equal()和hashCode()必然相等。
2、值对象一般不可修改，因此成员变量应用final修饰。
3、应该提供getters方法获取成员变量的值。
4、两个对象使用equal()比较而不是==

12.为什么在重写 equals 方法的时候需要重写 hashCode 方法？equals与 hashCode 的异同点在哪里 参考链接 参考链接 

如果不这样做的话，就会违反Object.hashCode的通用约定，从而导致该类无法结合所有基于散列的集合一起正常运作，这样的集合包括HashMap、HashSet和Hashtable。
在应用程序的执行期间，只要对象的equals方法的比较操作所用到的信息没有被修改，那么对这同一个对象调用多次，hashCode方法都必须始终如一地返回同一个整数。在同一个应用程序的多次执行过程中，每次执行所返回的整数可以不一致。
如果两个对象根据equals()方法比较是相等的，那么调用这两个对象中任意一个对象的hashCode方法都必须产生同样的整数结果。
如果两个对象根据equals()方法比较是不相等的，那么调用这两个对象中任意一个对象的hashCode方法，则不一定要产生相同的整数结果。但是程序员应该知道，给不相等的对象产生截然不同的整数结果，有可能提高散列表的性能。
不同点：
1.若重写了equals(Object obj)方法，则有必要重写hashCode()方法。
2.若两个对象equals(Object obj)返回true，则hashCode（）有必要也返回相同的int数。
3.若两个对象equals(Object obj)返回false，则hashCode（）不一定返回不同的int数。
4.若两个对象hashCode（）返回相同int数，则equals（Object obj）不一定返回true。
5.若两个对象hashCode（）返回不同int数，则equals（Object obj）一定返回false。
6.同一对象在执行期间若已经存储在集合中，则不能修改影响hashCode值的相关信息，否则会导致内存泄露问题。
7.hashCode是为了提高在散列结构存储中查找的效率，在线性表中没有作用

13.a.hashCode() 有什么用？与 a.equals(b) 有什么关系

hashCode() 方法是相应对象整型的 hash 值。它常用于基于 hash 的集合类，如 Hashtable、HashMap、LinkedHashMap等等。它与 equals() 方法关系特别紧密。根据 Java 规范，两个使用 equal() 方法来判断相等的对象，必须具有相同的 hash code。

14.hashCode() 和 equals() 方法的重要性体现在什么地方

Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。
在查找算法里，equals是判断查找条件和对比数据的关键，而hashCode可以加速查找，这是因为hashCode不同，则对象一定不同（hashCode相同才需要继续调用equals，前者的调用时间一般更短）
比较两个对象是否相同的时候，就需要重写hashCode()和equals()，用来保证只要对象的内容相等，就是两个相同的对象。否通比较的话，默认就是按照地址来比较的。

15.Object有哪些公用方法？Object类hashcode,equals 设计原则？ sun为什么这么设计？Object类的概述

clone、equals、hashCode、getClass、wait、notify、notifyAll、toString
hashCode：该方法用于哈希查找，重写了equals方法一般都要重写hashCode方法。这个方法在一些具有哈希功能的Collection中用到
equals：在Object中与==是一样的，子类一般需要重写该方法
参考上一题
类层次结构的根类，所有类都直接或者间接的继承自该类，构造方法 public Object()，是所有子类默认访问的无参构造方法

16.如何在父类中为子类自动完成所有的 hashcode 和 equals 实现？这么做有何优劣。

父类重写hashcode 和 equals方法，子类也重写，通过super调用父类的方法即可。
这题不太会

17.可以在 hashcode() 中使用随机数字吗？

不可以。Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。      

18.LinkedHashMap 和 PriorityQueue 的区别是什么

PriorityQueue保证最高或者最低优先级的的元素总是在队列头部，但是LinkedHashMap维持的顺序是元素插入的顺序。当遍历一个PriorityQueue 时，没有任何顺序保证，但是LinkedHashMap 课保证遍历顺序是元素插入的顺序。

19.List, Set, Map三个接口，存取元素时各有什么特点

Set里面不允许有重复的元素，
    存元素：add方法有一个boolean的返回值，当集合中没有某个元素，此时add方法可成功加入该元素时，则返回true；当集合含有与某个元素equals相等的元素时，此时add方法无法加入该元素，返回结果为false。
    取元素：没法说取第几个，只能以Iterator接口取得所有的元素，再逐一遍历各个元素。
List表示有先后顺序的集合，
    存元素：多次调用add(Object)方法时，每次加入的对象按先来后到的顺序排序，也可以插队，即调用add(int index,Object)方法，就可以指定当前对象在集合中的存放位置。
    取元素：方法1：Iterator接口取得所有，逐一遍历各个元素
        方法2：调用get(index i)来明确说明取第几个。
Map是双列的集合，
    存放用put方法:put(obj key,obj value)，每次存储时，要存储一对key/value，不能存储重复的key，这个重复的规则也是按equals比较相等。
    取元素：用get(Object key)方法根据key获得相应的value。
        也可以获得所有的key的集合，还可以获得所有的value的集合，
        还可以获得key和value组合成的Map.Entry对象的集合。

20.List, Set, Map 是否继承自 Collection 接口

List，Set是，Map不是。

21.遍历一个 List 有哪些不同的方式

传统的for循环遍历，基于计数器的、迭代器遍历，Iterator、foreach循环遍历、java8使用Stream

22.LinkedList 是单向链表还是双向链表

双向

23.LinkedList 、 ArrayList、Vector 有什么区别

(1)、一个是Array(动态数组)的数据结构，一个是Link(链表)的数据结构，此外，它们两个都是对List接口的实现。前者是数组队列，相当于动态数组；后者为双向链表结构，也可当作堆栈、队列、双端队列
(2)、当随机访问List时（get和set操作），ArrayList比LinkedList的效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。
(3)、当对数据进行增加和删除的操作时(add和remove操作)，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动。
(4)、从利用效率来看，ArrayList自由性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而LinkedList自由性较高，能够动态的随数据量的变化而变化，但是它不便于使用。
(5)、ArrayList主要控件开销在于需要在lList列表预留一定空间；而LinkList主要控件开销在于需要存储结点信息以及结点指针信息。
Vector线程安全。效率低
1.ArrayList在内存不够时默认是扩展50% + 1个，Vector是默认扩展1倍。
2.Vector提供indexOf(obj, start)接口，ArrayList没有。
3.Vector属于线程安全级别的，但是大多数情况下不使用Vector，因为线程安全需要更大的系统开销。

24.描述下 Java 中集合（Collections），接口（Interfaces），实现（Implementations）的概念。

略

25.插入数据时，ArrayList, LinkedList, Vector谁速度较快？

LinkedList>ArrayList>Vector

26.ArrayList 和 HashMap 的默认大小是多数 参考链接

在Java7中，ArrayList的默认大小是10个元素，HashMap的默认大小是16个元素（必须是2的幂）
ArrayList:内部实现是一个Object的数组。初始默认大小为0，当然也可以在其构造方法中设置。当添加一个Object时，默认扩充数组容量为10。然后每次扩充的新的数组大小等于，（原始容量*3/2）和（数组的长度+1）之间的较大值。根据每次增加一个Object，可得该情况每次扩充的固定大小为3/2。当初始大小为手动设置的时候，每次扩充的新的数组大小等于，（原始容量*3/2）和（数组的长度+1）之间的较大值。
HashMap:内部实现是一个Entry的数组，默认大小是空的数组。初始化的容量是16，负载因子是0.75(当数组元素数量大于总容量的负载因子的时候，扩充数组)。当默认不是空的数组时，当达到负载因子的比例的时候，每次扩充初始容量的2倍。

27.Set，List，Map的区别，什么场景下使用

1) 重复性
List 允许有重复元素。任何数量的重复元素都可以在不影响现有重复元素的值及其索引的情况下插入到 List。
Set 不允许重复。Set 以及所有实现了 Set 接口的类都不允许重复值的插入。
Map 以键值对的形式对元素进行存储。Map 不允许重复键但允许重复值。
2) 空值
List 允许任意数量的空值。
Set 最多允许一个空值的出现。
Map 只允许出现一个空键但允许任意数量的空值。
3) 排序
List 及其所有实现类保持了每个元素的插入顺序。
Set 中的元素都是无序的；但某些 Set 的实现类以某种顺序对其中的元素进行排序，比如 LinkedHashSet 按照元素的插入顺序进行排序。
Map 跟 Set 一样对元素进行无序存储，但其某些实现类对元素进行了排序。比如，TreeMap 依据键对其中的元素进行升序排序而 LinkedHashMap 则按照每个元素的插入次序进行排序。
4) 常用实现类
List：ArrayList、LinkedList 等等。
Set：HashSet、LinkedHashSet、TreeSet、SortedSet 等等。
Map：HashMap、TreeMap、WeakHashMap、LinkedHashMap、IdentityHashMap 等等。
什么时候使用 Java 里的 List、Set 和 Map？
1) 如果你的数据不允许有重复值，Set 是最适合的选择，因为其所有实现类都不允许有重复值。
2) 如果需要经常根据元素的索引值进行一些查询操作，那么 List(ArrayList)将是一个不错的选择。
3) 如果需要保留每个元素的插入次序，那么还是首选 List。
4) 如果你的数据需要进行 key - value 映射，那么就是 Map 了

28.ArrayList如何实现扩容

在JDK1.7中，如果通过无参构造的话，初始数组容量为0，当真正对数组进行添加时，才真正分配容量。
每次按照1.5倍（位运算）的比率通过copeOf的方式扩容。
在JKD1.6中，如果通过无参构造的话，初始数组容量为10.每次通过copeOf的方式扩容后容量为原来的1.5倍加1.以上就是动态扩容的原理。

29.Array 和 ArrayList 有何区别？什么时候更适合用Array

存储内容比较：
Array数组可以包含基本类型和对象类型，
ArrayList却只能包含对象类型。
但是需要注意的是：Array数组在存放的时候一定是同种类型的元素。ArrayList就不一定了，因为ArrayList可以存储Object。
空间大小比较：
它的空间大小是固定的，空间不够时也不能再次申请，所以需要事前确定合适的空间大小。
ArrayList的空间是动态增长的，如果空间不够，它会创建一个空间比原空间大一倍的新数组，然后将所有元素复制到新数组中，接着抛弃旧数组。而且，每次添加新的元素的时候都会检查内部数组的空间是否足够。（比较麻烦的地方）。
方法上的比较：
ArrayList作为Array的增强版，当然是在方法上比Array更多样化，比如添加全部addAll()、删除全部removeAll()、返回迭代器iterator()等。
适用场景：
如果想要保存一些在整个程序运行期间都会存在而且不变的数据，我们可以将它们放进一个全局数组里，但是如果我们单纯只是想要以数组的形式保存数据，而不对数据进行增加等操作，只是方便我们进行查找的话，那么，我们就选择ArrayList。

30.Map 接口提供了哪些不同的集合视图

Map接口提供三个集合视图：
（1）Set keyset()：返回map中包含的所有key的一个Set视图。集合是受map支持的，map的变化会在集合中反映出来，反之亦然。当一个迭代器正在遍历一个集合时，若map被修改了（除迭代器自身的移除操作以外），迭代器的结果会变为未定义。集合支持通过Iterator的Remove、Set.remove、removeAll、retainAll和clear操作进行元素移除，从map中移除对应的映射。它不支持add和addAll操作。
（2）Collection values()：返回一个map中包含的所有value的一个Collection视图。这个collection受map支持的，map的变化会在collection中反映出来，反之亦然。当一个迭代器正在遍历一个collection时，若map被修改了（除迭代器自身的移除操作以外），迭代器的结果会变为未定义。集合支持通过Iterator的Remove、Set.remove、removeAll、retainAll和clear操作进行元素移除，从map中移除对应的映射。它不支持add和addAll操作。
（3）Set<Map.Entry<K,V>> entrySet()：返回一个map钟包含的所有映射的一个集合视图。这个集合受map支持的，map的变化会在collection中反映出来，反之亦然。当一个迭代器正在遍历一个集合时，若map被修改了（除迭代器自身的移除操作，以及对迭代器返回的entry进行setValue外），迭代器的结果会变为未定义。集合支持通过Iterator的Remove、Set.remove、removeAll、retainAll和clear操作进行元素移除，从map中移除对应的映射。它不支持add和addAll操作。

31.为什么 Map 接口不继承 Collection 接口

尽管Map接口和它的实现也是集合框架的一部分，但Map不是集合，集合也不是Map。因此，Map继承Collection毫无意义，反之亦然。
如果Map继承Collection接口，那么元素去哪儿？Map包含key-value对，它提供抽取key或value列表集合的方法，但是它不适合“一组对象”规范。

32.介绍Java中的Collection FrameWork。集合类框架的基本接口有哪些

总共有两大接口：Collection 和Map ，一个元素集合，一个是键值对集合； 其中List和Set接口继承了Collection接口，一个是有序元素集合，一个是无序元素集合； 而ArrayList和 LinkedList 实现了List接口，HashSet实现了Set接口，这几个都比较常用； HashMap 和HashTable实现了Map接口，并且HashTable是线程安全的，但是HashMap性能更好；
java.util.Collection [I]
|—java.util.List [I]
    |—java.util.ArrayList [C]
    |—java.util.LinkedList [C]
    |—java.util.Vector [C]
        |—java.util.Stack [C]
|—java.util.Set [I]
    |—java.util.HashSet [C]
    |—java.util.SortedSet [I]
        |—java.util.TreeSet [C]
java.util.Map [I]
|—java.util.SortedMap [I]
    |—java.util.TreeMap [C]
|—java.util.Hashtable [C]
|—java.util.HashMap [C]
    |—java.util.LinkedHashMap [C]
|—java.util.WeakHashMap [C]

Java集合类里最基本的接口有：
Collection：单列集合的根接口
List：元素有序  可重复
ArrayList：类似一个长度可变的数组 。适合查询，不适合增删
LinkedList：底层是双向循环链表。适合增删，不适合查询。
Set：元素无序，不可重复
HashSet：根据对象的哈希值确定元素在集合中的位置
TreeSet: 以二叉树的方式存储元素，实现了对集合中的元素排序
Map：双列集合的根接口，用于存储具有键（key）、值（value）映射关系的元素。
HashMap：用于存储键值映射关系，不能出现重复的键key
TreeMap：用来存储键值映射关系，不能出现重复的键key，所有的键按照二叉树的方式排列

33.集合类框架的最佳实践有哪些

(1).假如元素的大小是固定的，而且能事先知道，我们就应该用Array而不是ArrayList。
(2).有些集合类允许指定初始容量。因此，如果我们能估计出存储的元素的数目，我们可以设置初始容量来避免重新计算hash值或者是扩容。
(3).为了类型安全，可读性和健壮性的原因总是要使用泛型。同时，使用泛型还可以避免运行时的ClassCastException。
(4).使用JDK提供的不变类(immutable class)作为Map的键可以避免为我们自己的类实现hashCode()和equals()方法。
(5).编程的时候接口优于实现。
(6).底层的集合实际上是空的情况下，返回长度是0的集合或者是数组，不要返回null。

34.为什么 Collection 不从 Cloneable 和 Serializable 接口继承

Collection接口指定一组对象，对象即为它的元素。如何维护这些元素由Collection的具体实现决定。例如，一些如List的Collection实现允许重复的元素，而其它的如Set就不允许。很多Collection实现有一个公有的clone方法。然而，把它放到集合的所有实现中也是没有意义的。这是因为Collection是一个抽象表现。重要的是实现。
当与具体实现打交道的时候，克隆或序列化的语义和含义才发挥作用。所以，具体实现应该决定如何对它进行克隆或序列化，或它是否可以被克隆或序列化。
在所有的实现中授权克隆和序列化，最终导致更少的灵活性和更多的限制。特定的实现应该决定它是否可以被克隆和序列化。

35.什么是 B+树，B-树，列出实际的使用场景。 参考链接

二叉查找树

简介

二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质:

• 任意节点左子树不为空,则左子树的值均小于根节点的值.
• 任意节点右子树不为空,则右子树的值均大于于根节点的值.
• 任意节点的左右子树也分别是二叉查找树.
• 没有键值相等的节点.

局限性及应用

一个二叉查找树是由n个节点随机构成,所以，对于某些情况,二叉查找树会退化成一个有n个节点的线性链.如下图: 
 
b图为一个普通的二叉查找树,大家看a图,如果我们的根节点选择是最小或者最大的数,那么二叉查找树就完全退化成了线性结构,因此,在二叉查找树的基础上,又出现了AVL树,红黑树,它们两个都是基于二叉查找树,只是在二叉查找树的基础上又对其做了限制.

AVL树

简介

AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。 
 
从上面这张图我们可以看出,任意节点的左右子树的平衡因子差值都不会大于1.

局限性

由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树.当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树.

应用

Windows NT内核中广泛存在.

红黑树

简介

一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black. 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍.它是一种弱平衡二叉树(由于是若平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索,插入,删除操作多的情况下,我们就用红黑树.

性质

• 每个节点非红即黑.
• 根节点是黑的。
• 每个叶节点(叶节点即树尾端NUL指针或NULL节点)都是黑的.
• 如果一个节点是红的,那么它的两儿子都是黑的.
• 对于任意节点而言,其到叶子点树NIL指针的每条路径都包含相同数目的黑节点. 
   
  每条路径都包含相同的黑节点.

应用

• 广泛用于C++的STL中,map和set都是用红黑树实现的.
• 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.
• IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查.
• ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
• java中TreeMap的实现.

B/B+树

注意B-树就是B树,-只是一个符号.

简介

B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到).B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成,而CPU的速度非常快,所以B树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少.

B树的性质

• 定义任意非叶子结点最多只有M个儿子；且M>2；
• 根结点的儿子数为[2, M]；
• 除根结点以外的非叶子结点的儿子数为[M/2, M]；
• 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
• 非叶子结点的关键字个数=指向儿子的指针个数-1；
• 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
• 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
• 所有叶子结点位于同一层； 
  
  这里只是一个简单的B树,在实际中B树节点中关键字很多的.上面的图中比如35节点,35代表一个key(索引)，而小黑块代表的是这个key所指向的内容在内存中实际的存储位置.是一个指针.

B+树

B+树是应文件系统所需而产生的一种B树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保存数据.),非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中.这不就是文件系统文件的查找吗?我们就举个文件查找的例子:有3个文件夹,a,b,c, a包含b,b包含c,一个文件yang.c, a,b,c就是索引(存储在非叶子节点), a,b,c只是要找到的yang.c的key,而实际的数据yang.c存储在叶子节点上. 
所有的非叶子节点都可以看成索引部分

B+树的性质(下面提到的都是和B树不相同的性质)

• 非叶子节点的子树指针与关键字个数相同;
• 非叶子节点的子树指针p[i],指向关键字值属于[k[i],k[i+1]]的子树.(B树是开区间,也就是说B树不允许关键字重复,B+树允许重复)；
• 为所有叶子节点增加一个链指针.
• 所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的);
• 非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层.
• 更适合于文件系统; 
  看下图: 
  
  非叶子节点(比如5,28,65)只是一个key(索引),实际的数据存在叶子节点上(5,8,9)才是真正的数据或指向真实数据的指针.

应用　　

B和B+树主要用在文件系统以及数据库做索引.比如Mysql;

B/B+树性能分析　

• n个节点的平衡二叉树的高度为H(即logn),而n个节点的B/B+树的高度为log_t((n+1)/2)+1; 　　
• 若要作为内存中的查找表,B树却不一定比平衡二叉树好,尤其当m较大时更是如此.因为查找操作CPU的时间在B-树上是O(mlog_tn)=O(lgn(m/lgt)),而m/lgt>1;所以m较大时O(mlog_tn)比平衡二叉树的操作时间大得多. 因此在内存中使用B树必须取较小的m.（通常取最小值m=3，此时B-树中每个内部结点可以有2或3个孩子，这种3阶的B-树称为2-3树）。

为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据索引.　　

• B+-tree的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对IO读写次数就降低了.
• 由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。 
  ps:我在知乎上看到有人是这样说的,我感觉说的也挺有道理的: 
  他们认为数据库索引采用B+树的主要原因是:B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生.B+树只需要去遍历叶子节点就可以实现整棵树的遍历.而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）.