集合与数据结构常见知识点总结_常用的数据结构及对应的特点及对应的集合类

集合和数据结构

常用集合的分类：

Collection 接口的接口 对象的集合（单列集合）
├——-List 接口：元素按进入先后有序保存，可重复
│—————-├ LinkedList 接口实现类， 链表， 插入删除， 没有同步， 线程不安全
│—————-├ ArrayList 接口实现类， 数组， 随机访问， 没有同步， 线程不安全
│—————-└ Vector 接口实现类 数组， 同步， 线程安全
│ ———————-└ Stack 是Vector类的实现类
└——-Set 接口： 仅接收一次，不可重复，并做内部排序
├—————-└HashSet 使用hash表（数组）存储元素
│————————└ LinkedHashSet 链表维护元素的插入次序
└ —————-TreeSet 底层实现为二叉树，元素排好序

Map 接口 键值对的集合 （双列集合）
├———Hashtable 接口实现类， 同步， 线程安全
├———HashMap 接口实现类 ，没有同步， 线程不安全-
│—————–├ LinkedHashMap 双向链表和哈希表实现
│—————–└ WeakHashMap
├ ——–TreeMap 红黑树对所有的key进行排序
└———IdentifyHashMap

List,Set都是继承自Collection接口，Map则不是，map是继承自map接口

Set：无序集合，不可重复，最多允许一个null值
List：有序集合，可重复
Map：映射集合

list是一个有序的容器，保持了每个元素的插入顺序。即输出顺序就是输入顺序，而set方法是无序容器，无法保证每个元素的存储顺序，TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序

数据结构

ArrayXxx:底层数据结构是数组，查询快，增删慢
LinkedXxx:底层数据结构是链表，查询慢，增删快
HashXxx:底层数据结构是哈希表。依赖两个方法：hashCode()和equals()
TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序**

List：

1. ArrayList：底层数据结构是数组，查询快，增删慢，线程不安全，效率高，可以存储重复元素
2. LinkedList 底层数据结构是链表，查询慢，增删快，线程不安全，效率高，可以存储重复元素
3. Vector:底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素

Map:

1. TreeMap：TreeMap的底层结构就是一个数组,数组中每一个元素又是一个红黑树.当添加一个元素(key-value)的时候,根据key的hash值来确定插入到哪一个桶中(确定插入数组中的位置),当桶中有多个元素时,使用红黑树进行保存;当一个桶中存放的数据过多,那么根据key查找的效率就会降低
2. HashMap：Node对象数组来存放数据，Hash冲突时会形成Node链表，在链表长度超过8，Node数组超过64时会将链表结构转换为红黑树，HashMap中的元素也不可以重复
3. HashTable：HashTable和hashMap底层实现原理一样，都是哈希表数据结构，hashMap线程不安全，hashTable线程安全
   HashMap是非同步的，没有对读写等操作进行锁保护，所以是线程不安全的，在多线程场景下会出现数据不一致的问题。
   而HashTable是同步的，所有的读写等操作都进行了锁（synchronized）保护，在多线程环境下没有安全问题。但是锁保护也是有代价的，会对读写的效率产生较大影响。

Set:

1. HashSet：HashSet内部基于HashMap来实现的，底层采用HashMap来保存元素。Set集合无序并不可重复。HashSet中的元素都存放在HashMap的key上面，而value中的值都是统一的一个private static final Object PRESENT = new Object();。HashSet跟HashMap一样，都是一个存放链表的数组。
2. TreeSet：底层是基于TreeMap来实现的，所以底层结构也是红黑树，因为他和HashSet不同的是不需要重写hashCode()和equals()方法，因为它去重是依靠比较器来去重，因为结构是红黑树，所以每次插入都会遍历比较来寻找节点插入位置，如果发现某个节点的值是一样的那就会直接覆盖。

线程安全(Thread-safe)的集合对象：

Vector 线程安全：
HashTable 线程安全：
StringBuffer 线程安全：
ConcurrentHashMap 线程安全

非线程安全的集合对象：

ArrayList：
LinkedList：
HashMap：
HashSet：
TreeMap：
TreeSet：
StringBulider：

Java 排序方式

• 自然排序：java.lang.Comparable
  Comparable接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序。 实现 Comparable接口 的类必须重写compareTo(Object obj) 方法，两个对象即通过 compareTo(Object obj) 方法的返回值来比较大小。如果当前对象this大于形参对象obj，则返回正整数， 如果当前对象this小于形参对象obj，则返回负整数，如果当前对象this等于形参对象obj，则返回零。 实现Comparable接口的对象列表（和数组）可以通过Collections.sort或Arrays.sort进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。
• 定制排序（比较器排序）：java.util.Comparator
  当元素的类型没有实现java.lang.Comparable接口而又不方便修改代码，或者实现了java.lang.Comparable接口的排序规则不适合当前的操作，那么可以考虑使用Comparator 接口的对象来排序，强行对多个对象进行整体排序的比较。 重写compare(Object o1,Object o2)方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。 可以将Comparator 传递给 sort 方法（如 Collections.sort 或Arrays.sort），从而允许在排序顺序上实现精确控制。 还可以使用 Comparator 来控制某些数据结构（如有序set或有序映射）的顺序，或者为那些没有自然顺序的对象 collection 提供排序。

hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表

常见集合区别

Array和ArrayList的区别：

Array类型的变量在声明的同时必须进行实例化(至少得初始化数组的大小)，而ArrayList可以只是先声明

Array只能存储相同类型的对象，而ArrayList可以存储不同类型的对象

Array对象的初始化必须只定指定大小，且创建后的数组大小是固定的，而ArrayList的大小可以动态指定，其大小可以在初始化时指定，也可以不指定，也就是说该对象的空间可以任意增加

Array不能够随意添加和删除其中的项，而ArrayList可以在任意位置插入和删除项

HashMap和TreeMap的区别**：

1. HashMap是通过hashcode()对其内容进行快速查找的；HashMap中的元素是没有顺序的；
   TreeMap中所有的元素都是有某一固定顺序的，如果需要得到一个有序的结果，就应该使用TreeMap；
2. HashMap和TreeMap都不是线程安全的；
3. HashMap继承AbstractMap类；重写了hashcode() 和equals() 方法，以确保两个相等的映射返回相同的哈希值；
   TreeMap继承SortedMap类；他保持键的有序顺序；
4. HashMap：基于hash表实现的；使用HashMap要求添加的键类明确定义了hashcode() 和equals()
   （可以重写该方法）；为了优化HashMap的空间使用，可以调优初始容量和负载因子；
   TreeMap：基于红黑树实现的；TreeMap就没有调优选项，因为红黑树总是处于平衡的状态；
5. HashMap：适用于Map插入，删除，定位元素； TreeMap：适用于按自然顺序或自定义顺序遍历键（key）

Hashmap和hashtable有什么区别：**

1. Hashtable是线程安全的，hashmap不安全
2. Hashtable的键值对都不能为null，hashmap可以（hashmap的key也是不能重复的）
3. Hashmap是非synchronized的，hashtable是

ArrayList和HashSet有什么区别：

1. HashSet实现的是Set接口，ArrayList实现的List接口，而Set和List接口都是继承Collection接口;
2. ArrayList存放的是对象的引用，HashSet存放之前检索对象的hashCode，没有相等，存入对象，所以当对象存入HashSet的时候，要对比域的话就需要重写hashCode()，如果只是比较对象的话，只需重写equals()方法。如果你看源码你就会知道，HashSet的构造器默认是new
   HashMap()。
3. ArrayList可以重复引用，HashSet是不重复存放。
4. ArrayList是有序存放，HashSet无序存放。
5. ArrayList是数组存储。HashSet存储对象，具有HashMap的特性。

HashMap 和 HashTable 的区别

HashMap 是线程不安全的，HashTable 是线程安全的；
由于线程安全，所以 HashTable 的效率比不上 HashMap；
HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null，而 HashTable 不 允许；
HashMap 默认初始化数组的大小为 16，HashTable 为 11，前者扩容时，扩大两倍， 后者扩大两倍+1
HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

HashMap，TreeMap，LinkedHashMap 使用场景

一般情况下，使用最多的是 HashMap。
HashMap：在 Map 中插入、删除和定位元素时，hashmap中key的值没有顺序，常用来做统计；
TreeMap：在需要按自然顺序或自定义顺序遍历键的情况下；
LinkedHashMap：在需要输出的顺序和输入的顺序相同的情况下，它比 HashMap 多维护了一个双向链表，因此可以按照插入的顺序从头部或者从尾部迭代，是有序的，LinkedHashMap 保证了元素是按照插入的顺序排列。
HashMap内部节点是无序的，根据 hash 值随机插入
有序的 Map：LinkedHashMap 和 TreeMap

HashMap存放了对象，如何根据对象的某个属性进行排序？

Map是Java中最常用的存储对象的集合类之一，存储在HashMap中的对象在取出时是无序的，下文以示例介绍了如果对HashMap中存储的对象根据成员进行自定义排序。

应用说明：计算缓存对象的点击次数按次数排序输出。
1.定义CacheObj类
定义了一个简单的对象，这个对象将存储在一个HashMap中，希望根据CacheObj中的整型成员变量cachedCounter进行排序输出。
2. 自定义HotItemComparator
HotItemComparator实现了Comparator 接口， 实现的方法非常简单就是根据cachedCounter进行比较返回比较结果
正序：return obj1.getCachedCounter() - obj2.getCachedCounter();
倒序：return obj2.getCachedCounter() - obj1.getCachedCounter();

加载因子

加载因子是表示Hsah表中元素的填满的程度，若加载因子越大，填满的元素越多，好处是，空间利用率高了，但冲突的机会加大了。反之，加载因子越小，填满的元素越少，好处是冲突的机会减小了，但空间浪费多了
冲突的机会越大，则查找的成本越高。反之，查找的成本越小。因而，查找时间就越小；

加载因子 = 填入表中的元素个数 / 散列表的长度
1

因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷；

ArrayList

为什么ArrayList查询速度快？

ArrayList底层是基于数组实现，可以根据元素下标进行查询，查询方式为（数组首地址+元素长度*下标，基于这个位置读取相应的字节数就可以了），如果数组存的是对象，怎么根据下标定位元素所在位置？（对象数组每个元素存放的是对象的引用，而引用类型如果开启指针压缩占用4字节，不开启则占用8字节，所以对象数组同样适用上面的公式

ArrayList的扩容？

ArrayList底层是基于数组实现，所以创建ArrayList会给数组指定一个初始容量，默认值为10，因为必须指明数组的长度才能给数组分配空间；由于数组的特性，ArrayList扩容是创建一个更大的数组，然后将原来的元素拷贝到更大的数组中，扩容的核心方法是Arrays.copyOf方法

ArrayList和LinkedList的区别，添加一个元素的时间复杂度各是多少，既然ArrayList添加元素效率没有LinkedList高，为什么我们平时用的比较多的还是ArrayList？

ArrayList访问源码：复杂度为O(1)，LinkedList访问源码：访问的复杂度为O(n)
性能问题的话也不能完全说前者比后者好,插入的时候确实是,都是,但读取的时候就不如后者了,后者是类似数组的方式读取,所以速度很快,所以如果插入删除做的比较多的话,我们应该选择前者,但如果读取比较多的话,多用后者

一般什么情况下会用ArrayList，什么情况用LinkedList？

如果只是普通的存取元素多用ArrayList，LinkedList一般用作栈、队列

将一个Map集合变成栈，如何实现？

我的思路是用TreeMap去实现，key存的是要入栈的元素，value存的是可以记录他们入栈的一个先后顺序的，例如时间戳，然后重写Comparator比较器，根据value进行排序，遍历Map时，先进的后面出

Map集合有迭代器吗？遍历输出Map中所有元素有哪些方法？

Map集合没有迭代器
Set keySet：将map中所有的键存入到Set集合。因为set具备迭代器。
所有可以迭代方式取出所有的键，在根据get方法。获取每一个键对应的值。
Map集合的取出原理：将map集合转成set集合。在通过迭代器取出。
遍历Map的两种方式：
第一种：Set keySet()
返回此映射中包含的键的Set视图，将Map集合中所有的键存入Set集合，然后再通过Set集合的
迭代器取出所有的键，再根据get方法获取每个键的值；
第二种：Set<Map.Entry<K,V>> entrySet()
返回此映射中包含的映射关系的Set视图，将Map集合中的映射关系存入到Set集合中，
这个映射关系的数据类型是Map.entry,再通过Map.Entry类的方法再要取出关系里面的键和值
Map.Entry的方法摘要：
boolean equals(Object o) 比较指定对象与此项的相等性。
K getKey() 返回与此项对应的键。
V getValue() 返回与此项对应的值。
int hashCode() 返回此映射项的哈希码值。
V setValue(V value) 用指定的值替换与此项对应的值(特有！！！)

数组和链表区别？

数组是顺序结构，即在物理层面，数据之间存储是相邻的；链表是链式存储结构，它会存储下一个数据所在地址；在查询上数组支持随即查找，效率更高，插入和删除操作需要移动空间，效率相对较低；而链表则相反。

从计算机原理的角度说一下为什么数组查找更快？

CPU和内存的读取速度差异使得Cache（高速缓冲存储器）出现，Cache会把一片连续的内存空间读入， 因为数组结构是连续的内存地址，而链表的节点是分散在堆空间里面的，所以数组全部或者部分元素被连续存在Cache，而链表则需要去内存查找，速度较慢。

HashMap

HashMap中的加载因子

HashMap默认的加载因子是0.75，最大容量是16，因此可以得出HashMap的默认容量是：0.75*16=12。
用户可以自定义最大容量和加载因子。
选择0.75作为默认的加载因子，跟泊松分布有关，完全是时间和空间成本上寻求的一种折衷选择。
泊松分布是统计学和概率学常见的离散概率分布，适用于描述单位时间内随机事件发生的次数的概率分布。

HashMap的底层结构

Node对象数组来存放数据，Hash冲突时会形成Node链表，在链表长度超过8，Node数组超过64时会将链表结构转换为红黑树，Node对象：

为什么HashMap集合是线程不安全的？

主要原因是没加锁
① 同时put碰撞导致数据丢失：多个线程同时执行put操作，计算出来的hashcode值相等，插入到同一位置导致有的数据被覆盖
② 同时put扩容导致数据丢失：多个线程执行put操作时同时发现需要扩容，也会发生数据丢失
③ 死循环导致CPU100%：所以在并发的情况，发生扩容时，可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap，并发环境下要使用ConcurrentHashmap。
JDK8以前是头插法，JDK8后是尾插法

HashMap怎么遍历

一、HashMap概述：
1.HashMap是一个散列表，它存储的是键值对（key-value）映射；
2.HashMap继承AbstractMap，实现了Map，Cloneable，Serializable接口；
3.HashMap的实现不是同步的，线程不安全，但是效率高；
4.HashMap允许null键和null值，是基于哈希表的Map接口实现；
5.哈希表的作用是用来保证键的唯一性；
6.HashMap的实例有两个参数影响其性能：初试容量和加载因子，当哈希表中的条目数超出加载因子与当前容量的乘积时，要对哈希表进行rehash操作（即重建内部数据结构），容量扩大约为之前的两倍，加载因子默认值为0.75；
二、HashMap的三种遍历方式：
在内部，HashMap使用一个Entry数组保存key、value数据，当一对key、value被加入时，会通过一个hash算法得到数组的下标index，算法很简单，根据key的hash值，对数组的大小取模 hash & (length-1)，并把结果插入数组该位置，如果该位置上已经有元素了，就说明存在hash冲突，这样会在index位置生成链表。
第一种：遍历HashMap的entrySet键值对集合
1.通过**HashMap.entrySet()得到键值对集合；
2.通过迭代器Iterator遍历键值对集合得到key值和value值；
第二种：遍历HashMap键的Set集合获取值；
1.通过HashMap.keySet()获得键的Set集合；
2.遍历键的Set集合获取值；
第三种：遍历HashMap“值”的集合；
1.通过HashMap.values()**得到“值”的集合
2.遍历“值”的集合；

ConcurrentHashMap如何保证线程安全

在ConcurrentHashMap中还定义了三个原子操作，用于对指定位置的节点进行操作。这三种原子操作被广泛的使用在ConcurrentHashMap的get和put等方法中，
正是这些原子操作保证了ConcurrentHashMap的线程安全
JDK 1.7
在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成

JDK1.7保证线程安全的机制： 使用的是分段锁，也就是为每一个segment加上ReentrantLock锁

JDK 1.8（借鉴了jdk1.8的HashMap结构）
JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本
ConcurrentHashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树是为了提高查找效率。

JDK1.8保证线程安全的机制： 使用的是CAS机制加上synchronized锁

CAS是乐观锁和自旋锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS是英文单词Compare And Swap的缩写，翻译过来就是比较并替换。
CAS机制当中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。
更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B。

这样说或许有些抽象，我们来看一个例子：

1.在内存地址V当中，存储着值为10的变量。

2.此时线程1想要把变量的值增加1。对线程1来说，旧的预期值A=10，要修改的新值B=11。

3.在线程1要提交更新之前，另一个线程2抢先一步，把内存地址V中的变量值率先更新成了11。

4.线程1开始提交更新，首先进行A和地址V的实际值比较（Compare），发现A不等于V的实际值，提交失败。

5.线程1重新获取内存地址V的当前值，并重新计算想要修改的新值。此时对线程1来说，A=11，B=12。这个重新尝试的过程被称为自旋。

6.这一次比较幸运，没有其他线程改变地址V的值。线程1进行Compare，发现A和地址V的实际值是相等的。

7.线程1进行SWAP，把地址V的值替换为B，也就是12。

从思想上来说，Synchronized属于悲观锁，悲观地认为程序中的并发情况严重，所以严防死守。CAS属于乐观锁，乐观地认为程序中的并发情况不那么严重，所以让线程不断去尝试更新。

ConcurrentHashMap以put操作为例，CAS方式确定key的数组下标，synchronized保证链表节点的同步效果。

乐观锁
总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和CAS算法实现。

为什么HashMap链表会变成红黑树

何链表长度为8才转变为红黑树呢，下面结合源码一起来分析一下。
我们都知道，链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的
因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。

HashMap新增数据的过程

put方法
put方法的第一步，就是计算出要put元素在hash桶数组中的索引位置，得到索引位置需要三步，去put元素key的hashcode值，高位运算，取模运算，高位运算就是用第一步得到的值h，用h的高16位和低16位进行异或操作，第三步为了使hash桶数组元素分布更均匀，采用取模运算，取模运算就是用第二步得到的值和hash桶数组长度-1的值取与。这样得到的结果和传统取模运算结果一致，而且效率比取模运算高

jdk1.8中put方法的具体步骤
先判断hashmap是否为空，为空的话扩容，不为空计算出key的hash值i，然后看table[i]是否为空，为空就直接插入，不为空判断当前位置的key和table[i]是否相同，相同就覆盖，不相同就查看table[i]是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于8，转为红黑树结构，执行完成后看size是否大于阈值threshold，大于就扩容，否则直接结束
get方法就是计算出要获取元素的hash值，去对应位置取即可。

扩容机制
hashmap的扩容中主要进行两步，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算hash插入到新数组中，在jdk1.8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。

HashMap 是否线程安全

不是，在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题，以1.8为例，当A线程判断index位置为空后正好挂起，B线程开始往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；还有++size这个地方也会造成多线程同时扩容等问题。
解决线程不安全方法
Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。
HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大
Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现
ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。

什么时候HashMap会扩容？并且还要描述扩容过程中数据是如何迁移的

HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，并且要存放的位置已经有元素了（hash碰撞），必须满足这两个条件，才要对该哈希表进行 rehash 操作，会将容量扩大为原来两倍。通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本。

ConcurrentHashMap

ConcurrentHashMap 类（是 Java 并发包 java.util.concurrent 中提供的一个线程安全且高效 的 HashMap 实现）。 HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）； 而针对 ConcurrentHashMap，在 JDK 1.7 中采用 分段锁的方式；JDK 1.8 中直接采用了 CAS （无锁算法）+ synchronized。
为什么 ConcurrentHashMap 比 HashTable 效率要高
HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞； ConcurrentHashMap JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分 成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。
JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry）。锁粒度降低了。

ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock

①粒度降低了； ②JVM 开发团队没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大， 更加自然。 ③、在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。

ConcurrentHashMap 的并发度是什么？

程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16， 且可以在构造函数中设置。 当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小 2 幂指数作为实际并 发度（假如用户设置并发度为 17，实际并发度则为 32）

ConcurrentHashMap底层采用的结构（分jdk1.7和jdk1.8），jdk1.7和jdk1.8分别采用什么方式实现线程安全？

jdk1.7采用分段锁，也就是为每一个segment加上ReentrantLock锁；jdk1.8使用的是CAS机制加上synchronized锁

ConcurrentMap中的size方法是如何实现的？多线程操作下，如果一个线程在查size方法，一个线程在执行put方法，底层是如何控制每次计算出来的值是正确的？

在 JDK1.7 中，第一种方案他会使用不加锁的模式去尝试多次计算 ConcurrentHashMap 的 size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的。 第二种方案是如果第一种方案不符合，他就会给每个 Segment 加上锁，然后计算 ConcurrentHashMap 的 size 返回

baseCount 记录元素数量的，每次元素元素变更之后，将会使用 CAS方式更新该值。
如果多个线程并发增加新元素，baseCount 更新冲突，将会启用 CounterCell，通过使用 CAS 方式将总数更新到 counterCells 数组对应的位置

JDK1.8 size 是通过对 baseCount 和 counterCell 进行 CAS 计算，最终通过 baseCount 和 遍历 CounterCell 数组得出 size。
JDK 8 推荐使用mappingCount 方法，因为这个方法的返回值是 long 类型，不会因为 size 方法是 int 类型限制最大值

ConcurrentMap中的size方法是如何实现的？

1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount

1、初始化时counterCells为空，在并发量很高时，如果存在两个线程同时执行CAS修改baseCount值，则失败的线程会继续执行方法体中的逻辑，使用CounterCell记录元素个数的变化；
2、如果CounterCell数组counterCells为空，调用fullAddCount()方法进行初始化，并插入对应的记录数，通过CAS设置cellsBusy字段，只有设置成功的线程才能初始化CounterCell数组；
3、如果通过CAS设置cellsBusy字段失败的话，则继续尝试通过CAS修改baseCount字段，如果修改baseCount字段成功的话，就退出循环，否则继续循环插入CounterCell对象；
所以在1.8中的size实现比1.7简单多，因为元素个数保存baseCount中，部分元素的变化个数保存在CounterCell数组中，通过累加baseCount和CounterCell数组中的数量，即可得到元素的总个数；
在没有并发的情况下，使用一个 baseCount volatile 变量就足够了，当并发的时候，CAS 修改 baseCount 失败后，就会使用 CounterCell 类了，会创建一个这个对象，通常对象的 volatile value 属性是 1。在计算 size 的时候，会将 baseCount 和 CounterCell 数组中的元素的 value 累加，得到总的大小；
JDK 8 推荐使用mappingCount 方法，因为这个方法的返回值是 long 类型，不会因为 size 方法是 int 类型限制最大值，而size()会；

将一个Map集合变成栈，如何实现？
（我的思路是用TreeMap去实现，key存的是要入栈的元素，value存的是可以记录他们入栈的一个先后顺序的，例如时间戳，然后重写Comparator比较器，根据value进行排序，遍历Map时，先进的后面出）
参考文章：https://blog.csdn.net/can_chen/article/details/108722624

HashMap的Put方法的执行流程：

红黑树：

红黑树的概述：
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下图中这棵树，就是一颗典型的红黑树：

红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。红黑树比较平衡，不会出现二叉树那种一边倒的特殊情况。

而且实际应用中，很多语言都实现了红黑树的数据结构。比如 TreeMap, TreeSet(Java )、 STL(C++)等。

1.HashMap底层实现（JDK1.7使用数组+链表；JDK1.8使用数组+链表+红黑树）
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

红黑树的转换

红黑树选择和颜色变换规则：所有插入点默认为红色

1. 变颜色情况：当前节点的父亲节点、叔叔节点均为红色
   （1）把父亲节点设为黑色
   （2）叔叔节点设为黑色
   （3）祖父节点设为红色
   （4）指针定位到祖父节点

2. 左旋：当前节点的父节点为红色，叔叔节点为黑色，且当前节点是右子树。
   左旋以父节点作为左旋

3. 右旋：当前节点的父节点为红色，叔叔节点为黑色，且当前节点是左子树。
   （1）把父节点变为黑色
   （2）祖父节点变为红色
   （3）以祖父节点右旋
   
   

HashMap为什么要引进红黑树？为什么不用其他的平衡二叉树之类的？红黑树的优势在哪里

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。加快检索速率
AVL树：平衡二叉树
AVL树的旋转比红黑树的旋转更加难以平衡和调试，需要更高的旋转次数

链表会转化为红黑树的两个条件是

①链表的长度达到8；②HashMap底层使用的table数组长度length达到64；如果不满足后者，将会触发扩容方法

链表长度大于8转化为红黑树，小于6红黑树转化为链表；为什么不直接设置成大于8转化成红黑树，小于8转化成链表
中间有个差值7进行过渡是为了避免链表和树频繁转换，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低

把链表转化为红黑树的阈值是8，为什么不设置成其他值
遵循泊松分布，链表长度超过8的概率非常小

HashMap扩容机制，即resize方法？

什么时候扩容：当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值(知道这个阈字怎么念吗？不念fa值，念yu值四声)—即当前数组的长度乘以**加载因子（0.75）**的值的时候，就要自动扩容啦。

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。

HashMap添加元素的步骤（put方法）、计算集合元素个数（size方法）

HashMap默认的加载因子是0.75，为什么不设置成1或者0.5

（从容量和性能考虑）

HashMap发生哈希冲突，新节点是插入到链表头部还是链表的尾部，头部倒序插入死循环是怎么产生的？

头插法是新增节点总是插在头部
尾插法就是插入到链表最后一个节点之后
jdk1.7采用头部倒序插入，会导致死循环；jdk1.8使用尾部正序插入
比如有两个线程同时进行rehash，要将链表进行重新排列
rehash前链表结构为：A --> B

线程1进行操作：遍历原链表，首先获得节点A，操作挂起，线程2进入。（线程1数据不会提交）
线程2进行操作：遍历原链表，以头插方式遍历执行，执行完成 B – > A。（线程2数据未提交）
线程1继续执行：遍历原链表，头插方式执行，完成 B – > A，此时线程2数据提交，线程1发现 B.next 不为null，继续遍历执行，又将B.next = A插入，形成A --> B – > A循环结构。

而JDK1.8采用尾插法就保证了顺序不会错乱

Hashtable怎么控制key value 不能为null？

当调用put方法时，首先会判断value是否为null，为null的话直接抛出空指针异常；对于key，由于Hashtable计算hash值是int hash = key.hashCode();直接取对象的hashcode，key为null就会报空指针异常；而HashMap计算hash值是return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)，key为null则hash值为0

深度优先遍历和广度优先遍历：

1.1　无向图的深度优先遍历图解
以下"无向图"为例：

　对上无向图进行深度优先遍历，从A开始：
第1步：访问A。
第2步：访问B(A的邻接点)。 在第1步访问A之后，接下来应该访问的是A的邻接点，即"B,D,F"中的一个。但在本文的实现中，顶点ABCDEFGH是按照顺序存储，B在"D和F"的前面，因此，先访问B。
第3步：访问G(B的邻接点)。 和B相连只有"G"(A已经访问过了)
第4步：访问E(G的邻接点)。 在第3步访问了B的邻接点G之后，接下来应该访问G的邻接点，即"E和H"中一个(B已经被访问过，就不算在内)。而由于E在H之前，先访问E。
第5步：访问C(E的邻接点)。 和E相连只有"C"(G已经访问过了)。
第6步：访问D(C的邻接点)。
第7步：访问H。因为D没有未被访问的邻接点；因此，一直回溯到访问G的另一个邻接点H。
第8步：访问(H的邻接点)F。
因此访问顺序是：A -> B -> G -> E -> C -> D -> H -> F
　　1.2　有向图的深度优先遍历
有向图的深度优先遍历图解：

对上有向图进行深度优先遍历，从A开始：
第1步：访问A。
第2步：访问(A的出度对应的字母)B。 在第1步访问A之后，接下来应该访问的是A的出度对应字母，即"B,C,F"中的一个。但在本文的实现中，顶点ABCDEFGH是按照顺序存储，B在"C和F"的前面，因此，先访问B。
第3步：访问(B的出度对应的字母)F。 B的出度对应字母只有F。
第4步：访问H(F的出度对应的字母)。 F的出度对应字母只有H。
第5步：访问(H的出度对应的字母)G。
第6步：访问(G的出度对应字母)E。 在第5步访问G之后，接下来应该访问的是G的出度对应字母，即"B,C,E"中的一个。但在本文的实现中，顶点B已经访问了，由于C在E前面，所以先访问C。
第7步：访问(C的出度对应的字母)D。
第8步：访问(C的出度对应字母)D。 在第7步访问C之后，接下来应该访问的是C的出度对应字母，即"B,D"中的一个。但在本文的实现中，顶点B已经访问了，所以访问D。
第9步：访问E。D无出度，所以一直回溯到G对应的另一个出度E。
因此访问顺序是：A -> B -> F -> H -> G -> C -> D -> E

2.广度优先遍历
　广度优先遍历(Depth First Search)的主要思想是：类似于树的层序遍历。
　　2.1　无向图的广度优先遍历图解：

从A开始，有4个邻接点，“B，C，D，F”，这是第二层；
在分别从B，C，D，F开始找他们的邻接点，为第三层。以此类推。
先找B的邻接点

因此访问顺序是：A -> B -> C -> D -> F -> G -> E -> H

2.2　有向图的广度优先遍历图解：

与无向图类似 。可以参考。

因此访问顺序是：A -> B -> C -> F -> D -> H -> E -> G

前序、中序、后序遍历：
一棵二叉树由根结点、左子树和右子树三部分组成，若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树，则二叉树的遍历方式有 6 种：DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以，只讨论三种方式：
DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

补充两个例子：

前序124536 （根左右）
中序425136（左根右）
后序452631（左右根）

前序12469735810（根左右）
中序26947135108（左根右）
后序96742108531（左右根）

常见排序：

快速排序：

①先从队尾开始向前扫描且当low < high时,如果a[high] > tmp,则high–,但如果a[high] < tmp,则将high的值赋值给low,即arr[low] = a[high],同时要转换数组扫描的方式,即需要从队首开始向队尾进行扫描了
  ②同理,当从队首开始向队尾进行扫描时,如果a[low] < tmp,则low++,但如果a[low] > tmp了,则就需要将low位置的值赋值给high位置,即arr[low] = arr[high],同时将数组扫描方式换为由队尾向队首进行扫描.
  ③不断重复①和②,知道low>=high时(其实是low=high),low或high的位置就是该基准数据在数组中的正确索引位置.

直接插入排序：

直接插入排序（Straight Insertion Sorting）的基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
代码实现：

public void insertSort(int [] a){
        int len=a.length;//单独把数组长度拿出来，提高效率
        int insertNum;//要插入的数
        for(int i=1;i<len;i++){//因为第一次不用，所以从1开始
            insertNum=a[i];
            int j=i-1;//序列元素个数
            while(j>=0&&a[j]>insertNum){//从后往前循环，将大于insertNum的数向后移动
                a[j+1]=a[j];//元素向后移动
                j--;
            }
            a[j+1]=insertNum;//找到位置，插入当前元素
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。
设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。
从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。
将当前数放置到空着的位置，即j+1。

简单选择排序：

其实就是每次都取最小的数放在前面
常用于取序列中最大最小的几个数时。
(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)
遍历整个序列，将最小的数放在最前面。
遍历剩下的序列，将最小的数放在最前面。
重复第二步，直到只剩下一个数。

代码实现：

public void selectSort(int[]a){
        int len=a.length;
        for(int i=0;i<len;i++){//循环次数
            int value=a[i];
            int position=i;
            for(int j=i+1;j<len;j++){//找到最小的值和位置
                if(a[j]<value){
                    value=a[j];
                    position=j;
                }
            }
            a[position]=a[i];//进行交换
            a[i]=value;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

首先确定循环次数，并且记住当前数字和当前位置。
将当前位置后面所有的数与当前数字进行对比，小数赋值给key，并记住小数的位置。
比对完成后，将最小的值与第一个数的值交换。
重复2、3步。

冒泡排序：

每次都是相邻的两个数相比较，然后每次都把剩下的最大的数排到右边
很简单，用到的很少，据了解，面试的时候问的比较多！
将序列中所有元素两两比较，将最大的放在最后面。
将剩余序列中所有元素两两比较，将最大的放在最后面。
重复第二步，直到只剩下一个数。

代码实现：

public void bubbleSort(int []a){
           int len=a.length;
           for(int i=0;i<len;i++){// 第i次排序
               for(int j=0;j<len-i-1;j++){// 注意第二重循环的条件 从索引为j的数开始
                   if(a[j]>a[j+1]){//  相邻元素两两对比
                       int temp=a[j];// 元素交换
                       a[j]=a[j+1];
                       a[j+1]=temp;
                   }
               }
           }
       }
1
2
3
4
5
6
7
8
9
10
11
12

设置循环次数。
设置开始比较的位数，和结束的位数。
两两比较，将最小的放到前面去。
重复2、3步，直到循环次数完毕。

排序比较

一、稳定性:**

稳定：冒泡排序、插入排序、归并排序、选择排序和基数排序
稳定”排序算法使具有相同排序键的项保持顺序。假设我们有一个由5个字母组成的单词列表：peach straw apple spork如果我们只按每个单词的第一个字母对列表进行排序，那么稳定的排序就会产生：apple peach straw spork在不稳定排序算法，straw或spork可能是互换的，但在稳定的情况下，它们保持在相同的相对位置上(也就是说，因为straw出现在前面spork在输入中，它也出现在前面。spork在输出中)。
稳不稳定其实就是看在排序过程中，相等的两项或者多项会不会有交换位置的可能，如果有，那就是不稳定

不稳定：快速排序、希尔排序、堆排序

二、平均时间复杂度**

O(n^2):直接插入排序，简单选择排序，冒泡排序。
　　在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。
　　O(nlogn):快速排序，归并排序，希尔排序，堆排序。
　　其中，快排是最好的， 其次是归并和希尔，堆排序在数据量很大时效果明显。
三、排序算法的选择
　　1.数据规模较小
　　（1）待排序列基本序的情况下，可以选择直接插入排序；
　　（2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡
　　2.数据规模不是很大
　　（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
　　（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序
　　3.数据规模很大
　　（1）对稳定性有求，则可考虑归并排序。
　　（2）对稳定性没要求，宜用堆排序
　　4.序列初始基本有序（正序），宜用直接插入，冒泡
各算法复杂度如下：

树和二叉树：

结点的度：结点子树的个数
树的度：树中结点度的最大值

二叉树：每个结点最多只有两个子树的有序树
满二叉树：一个二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。

完全二叉树：是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。
一棵非空二叉树的第i层上最多有2^(i-1)个结点
一棵深度为k的二叉树中，最多具有2^k-1个结点
对于一棵费控的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有：n0=n2+1

哈夫曼树:又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+ WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。

构建哈夫曼树的过程
对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

图 2 哈夫曼树的构建过程

图 2 中，（A）给定了四个结点a，b，c，d，权值分别为7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是哈夫曼树。

二叉树的创建与遍历：

package test;

import java.util.LinkedList;  
import java.util.List;  
  
/** 
 * 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历 
 *  
 * 参考资料0:数据结构(C语言版)严蔚敏 
 *  
 * 参考资料1：http://zhidao.baidu.com/question/81938912.html 
 *  
 * 参考资料2：http://cslibrary.stanford.edu/110/BinaryTrees.html#java 
 *  
 * @author ocaicai@yeah.net @date: 2011-5-17 
 *  
 */  
public class BinTreeTraverse2 {  
  
    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
    private static List<Node> nodeList = null;  
  
    /** 
     * 内部类：节点 
     *  
     * @author ocaicai@yeah.net @date: 2011-5-17 
     *  
     */  
    private static class Node {  
        Node leftChild;  
        Node rightChild;  
        int data;  
  
        Node(int newData) {  
            leftChild = null;  
            rightChild = null;  
            data = newData;  
        }  
    }  
  
    public void createBinTree() {  
        nodeList = new LinkedList<Node>();  
        // 将一个数组的值依次转换为Node节点  
        for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {  
            nodeList.add(new Node(array[nodeIndex]));  
        }  
        // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树  
        for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {  
            // 左孩子  
            nodeList.get(parentIndex).leftChild = nodeList  
                    .get(parentIndex * 2 + 1);  
            // 右孩子  
            nodeList.get(parentIndex).rightChild = nodeList  
                    .get(parentIndex * 2 + 2);  
        }  
        // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理  
        int lastParentIndex = array.length / 2 - 1;  
        // 左孩子  
        nodeList.get(lastParentIndex).leftChild = nodeList  
                .get(lastParentIndex * 2 + 1);  
        // 右孩子,如果数组的长度为奇数才建立右孩子  
        if (array.length % 2 == 1) {  
            nodeList.get(lastParentIndex).rightChild = nodeList  
                    .get(lastParentIndex * 2 + 2);  
        }  
    }  
  
    /** 
     * 先序遍历 
     *  
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void preOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        System.out.print(node.data + " ");  
        preOrderTraverse(node.leftChild);  
        preOrderTraverse(node.rightChild);  
    }  
  
    /** 
     * 中序遍历 
     *  
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void inOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        inOrderTraverse(node.leftChild);  
        System.out.print(node.data + " ");  
        inOrderTraverse(node.rightChild);  
    }  
  
    /** 
     * 后序遍历 
     *  
     * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void postOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        postOrderTraverse(node.leftChild);  
        postOrderTraverse(node.rightChild);  
        System.out.print(node.data + " ");  
    }  
  
    public static void main(String[] args) {  
        BinTreeTraverse2 binTree = new BinTreeTraverse2();  
        binTree.createBinTree();  
        // nodeList中第0个索引处的值即为根节点  
        Node root = nodeList.get(0);  
  
        System.out.println("先序遍历：");  
        preOrderTraverse(root);  
        System.out.println();  
  
        System.out.println("中序遍历：");  
        inOrderTraverse(root);  
        System.out.println();  
  
        System.out.println("后序遍历：");  
        postOrderTraverse(root);  
    }  
  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

Hashtable和ConcurrentHashmap如何控制key value 不为空？

为了确保key和value不为空，Hashtable和ConcurrentHashmap在底层代码都对value和key在进行hash值计算的时候进行校验，如果为null则抛出空指针异常

而hashmap在计算key的hash值时，会判断是否为null，如果是，则返回0，即key为null的键值对的hash为0。因此一个hashmap对象只会存储一个key为null的键值对，因为它们的hash值都相同。
将键值对放入table中时，不会校验value是否为null。因此一个hashmap对象可以存储多个value为null的键值对

B树：

B树也称B-树,它是一颗多路平衡查找树。二叉树我想大家都不陌生，其实，B树和后面讲到的B+树也是从最简单的二叉树变换而来的，并没有什么神秘的地方，下面我们来看看B树的定义。
m是阶数

• 每个节点最多有m-1个关键字（可以存有的键值对）。
• 根节点最少可以只有1个关键字。
• 非根节点至少有m/2个关键字。
• 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
• 每个节点都存有索引和数据，也就是对应的key和value。

所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。
另外，我们需要注意一个概念，描述一颗B树时需要指定它的阶数，阶数表示了一个节点最多有多少个孩子节点，一般用字母m表示阶数。
我们再举个例子来说明一下上面的概念，比如这里有一个5阶的B树，根节点数量范围：1 <= k <= 4，非根节点数量范围：2 <= k <= 4。
下面，我们通过一个插入的例子，讲解一下B树的插入过程，接着，再讲解一下删除关键字的过程。
1.2 B树插入
插入的时候，我们需要记住一个规则：判断当前结点key的个数是否小于等于m-1，如果满足，直接插入即可，如果不满足，将节点的中间的key将这个节点分为左右两部分，中间的节点放到父节点中即可。
例子：在5阶B树中，结点最多有4个key,最少有2个key（注意：下面的节点统一用一个节点表示key和value）。
插入18，70，50,40

插入22

插入22时，发现这个节点的关键字已经大于4了，所以需要进行分裂，分裂的规则在上面已经讲了，分裂之后，如下。

接着插入23，25，39

分裂，得到下面的。

更过的插入的过程就不多介绍了，相信有这个例子你已经知道怎么进行插入操作了。
B树的删除操作相对于插入操作是相对复杂一些的，但是，你知道记住几种情况，一样可以很轻松的掌握的。
现在有一个初始状态是下面这样的B树，然后进行删除操作。

删除15，这种情况是删除叶子节点的元素，如果删除之后，节点数还是大于m/2，这种情况只要直接删除即可。

接着，我们把22删除，这种情况的规则：22是非叶子节点，对于非叶子节点的删除，我们需要用后继key（元素）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。对于删除22，需要将后继元素24移到被删除的22所在的节点。

此时发现26所在的节点只有一个元素，小于2个（m/2），这个节点不符合要求，这时候的规则（向兄弟节点借元素）：如果删除叶子节点，如果删除元素后元素个数少于（m/2），并且它的兄弟节点的元素大于（m/2），也就是说兄弟节点的元素比最少值m/2还多，将先将父节点的元素移到该节点，然后将兄弟节点的元素再移动到父节点。这样就满足要求了。
我们看看操作过程就更加明白了。

接着删除28，删除叶子节点，删除后不满足要求，所以，我们需要考虑向兄弟节点借元素，但是，兄弟节点也没有多的节点（2个），借不了，怎么办呢？如果遇到这种情况，首先，还是将先将父节点的元素移到该节点，然后，将当前节点及它的兄弟节点中的key合并，形成一个新的节点。

移动之后，跟兄弟节点合并。

删除就只有上面的几种情况，根据不同的情况进行删除即可。
上面的这些介绍，相信对于B树已经有一定的了解了，接下来的一部分，我们接着讲解B+树，我相信加上B+树的对比，就更加清晰明了了。

B+树：
B+树其实和B树是非常相似的，我们首先看看相同点。

• 根节点至少一个元素
• 非根节点元素范围：m/2 <= k <= m-1

不同点。

• B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。
• 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
• 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
• 父节点存有右孩子的第一个元素的索引。

下面我们看一个B+树的例子，感受感受它吧！

插入操作
对于插入操作很简单，只需要记住一个技巧即可：当节点元素数量大于m-1的时候，按中间元素分裂成左右两部分，中间元素分裂到父节点当做索引存储，但是，本身中间元素还是分裂右边这一部分的。
下面以一颗5阶B+树的插入过程为例，5阶B+树的节点最少2个元素，最多4个元素。
插入5，10，15，20

插入25，此时元素数量大于4个了，分裂

接着插入26，30，继续分裂

有了这几个例子，相信插入操作没什么问题了，下面接着看看删除操作。
2.3 删除操作
对于删除操作是比B树简单一些的，因为叶子节点有指针的存在，向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节移动即可（前提是兄弟节点的元素大于m/2），然后更新父节点的索引；如果兄弟节点的元素不大于m/2（兄弟节点也没有多余的元素），则将当前节点和兄弟节点合并，并且删除父节点中的key，下面我们看看具体的实例。
初始状态

删除10，删除后，不满足要求，发现左边兄弟节点有多余的元素，所以去借元素，最后，修改父节点索引

删除元素5，发现不满足要求，并且发现左右兄弟节点都没有多余的元素，所以，可以选择和兄弟节点合并，最后修改父节点索引

发现父节点索引也不满足条件，所以，需要做跟上面一步一样的操作

这样，B+树的删除操作也就完成了，是不是看完之后，觉得非常简单！
B树和B+树总结
B+树相对于B树有一些自己的优势，可以归结为下面几点。
单一节点存储的元素更多，使得查询的IO次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构了。
所有的查询都要查找到叶子节点，查询性能是稳定的，而B树，每个节点都可以查找到数据，所以不稳定。
所有的叶子节点形成了一个有序链表，更加便于查找。

B-树的阶数越大，越不容易发生分裂，阶数越小，越容易发生分裂

索引为什么用 B+ 树，不用 B 树

主要是B树不支持范围查找
B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。这就决定了B+树更适合用来存储外部数据，也就是所谓的磁盘数据。
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）
B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。
IO 次数
B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数

Hash表：

有没有一种函数H，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就预先知道key所在的位置，直接找到数据，提升效率。
即
地址index=H（key）

说白了，hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表
hashcode就是通过hash函数得来的，通俗的说，就是通过某一种算法得到的，hashcode就是在hash表中有对应的位置。
两个不同的关键字，由于哈希函数值相同，因而被映射到哈希表的同一位置上。称这种现象为冲突或碰撞。发生冲突的两个关键字称为该哈希函数的同义词。

什么情况会发生哈希冲突，如何解决哈希冲突？

哈希冲突：无限的数据被哈希算法计算出的结果是有限的，即多个数据对应同一个计算结果（多对一）。举个例子，哈希表就相当于查字典的汉语拼音音节索引。但是可能会出现一种情况，比如an和ang对应的汉字在同一页。这就是哈希冲突。
解决哈希冲突的方法：
1.开放寻址法。
①线性探查法；②二次探查法；
2.链地址法。
3.再散列法。
4.建立一个公共溢出区。

Hash冲突或者碰撞的解决方法：

拉链法

把所有的同义词用单链表链接起来的方法。在这种方法中，哈希表每个单元中存放的不再是记录本身，而是相应同义词单链表的头指针。由于单链表中可插入任意多个结点，所以此时装填因子α根据同义词的多少既可以设定为大于1，也可以设定为小于或者等于1，通常取α=1。

开放定址法

也叫闭散列，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
我们来看一个例子：假设现在有一个关键码集合{1,4,5,6,7,9}，哈希结构的容量为10，哈希函数为 Hash(key)=key%10。将所有关键码插入到该哈希结构中，如图。

假如现在有一关键码24要插入该结构中，使用哈希函数求得哈希地址为4，但是该地址处已经存放了元素，此时发生哈希冲突。

线性探测：从发生哈希冲突位置开始，依次向后探测，直到找到下一个空位置为止。例如上面的例子，插入关键码24时，进行线性探测，插入后如下图。

α=填入表中的元素个数/散列表的长度
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下

Hashmap的结构是什么

数组+单链表+红黑树
当链表长度超过8,并且数组长度到64时单链表会变成红黑树结构

HashSet是怎么确保元素不重复

HashSet是哈希表结构，当一个元素要存入HashSet集合时，首先通过自身的hashCode方法算出一个值，然后通过这个值查找元素在集合中的位置，如果该位置没有元素，那么就存入。如果该位置上有元素，那么继续调用该元素的equals方法进行比较，如果equals方法返回为真，证明这两个元素是相同元素，则不存。否则则在该位置上存储2个元素（一般不可能重复）所以当一个自定义的对象想正确存入HashSet集合，那么应该重写Object的hashCode和equals。HashSet是通过hashCode()和equals()方法确保元素无序不重复的

Hash表处理冲突的方式
开放地址法
线性探测法：若当前想放的位置有值了，就往后寻找最近一个空位置，将值放入。
可能会造成某一块区域数据很密集（如 上面代码中，18岁的学生有很多个，从“18”该放的位置起数据很密集），不推荐。
二次探测法：若当前想放的位置有值了，就往后查找 i^2 个位置是否为空，否则就继续指导找到空的位置（如：当前想放在位置 1，位置不为空，往后移动 1 ^ 2 位置查看是否为空；结果位置 2 有值，再往后移动 2 ^ 2 个位置，结果2 + 2 ^ 2 = 6 即位置6 为空，放下数值。否则继续前面操作）。
可能会造成很多位置的浪费，即数组长度过长中间却很多空位置。
再哈希法：需要两个（或三个及以上）散列函数。假设用函数一发现当前位置不为空，不继续调用函数一寻找空位置，而是转调用函数二寻找空位置

链地址法
在哈希表每一个单元中设置链表，某个数据项对的关键字还是像通常一样映射到哈希表的单元中，而数据项本身插入到单元的链表中。简单理解如下：

来一个相同的数据，就将它插入到单元对应的链表中，再来一个相同的，继续给链表中插入。

Srping Bean怎么解决线程安全

使用ThreadLocal，ThreadLocal会为每一个线程提供一个独立的变量副本
使用线程同步，关键字synchronized当线程较多时，当一个线程调用该方法时

LinkHashMap 如何实现有序？

LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。

TreeMap 如何实现有序？

TreeMap是按照Key的自然顺序或者Comprarator的顺序进行排序，内部是通过红黑树来实现。所以要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。

链表转红黑树为什么长度阈值是8

红黑树转链表阈值是6
经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，概率说话。。因为8够用了，至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的互相转化，为了预防这种情况的发生。

为什么当链表长度达到阈值转用红黑树，而不是二叉查找树？

选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性 结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。

红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树 就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为 了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当 长度大于 8 的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入 反而会慢。

HashSet的底层实现？

基于HashMap来实现的，new 一个 HashSet对象底层实际就是new了一个HashMap，并且使用默认的初始容量16和默认的加载因子0.75；当我们往HashSet里面添加一个元素其实就是往HashMap里面put了一个元素，并且是以key存在的，即插入HashSet中的值，为HashMap中的key，HashMap的value值都是一样的，是一个静态常量PRESENT，源码为：private static final Object PRESENT = new Object();

BlockingQueue（阻塞队列）如何实现生产者消费者模型？

阻塞队列常用于生产者和消费者的场景，生产者是向队列里添加元素的线程，消费者是从队列里取元素的线程。简而言之，阻塞队列是生产者用来存放元素、消费者获取元素的容器

阻塞队列的实现:
阻塞队列依旧是一个先进先出的队列
入队列时如果发现队列满了,就会阻塞,直到其他线程调用出队列操让队列有空位之后 ,才能继续入队列
出队列的时候如果发现队列为空,也会阻塞, 直到其他线程调用入队列操作rag队列有元素,才能继续出队列