1、Java中操作字符串都有哪些类？它们之间有什么区别？

参考答案：

操作字符串的类有：String、StringBuffer、StringBuilder 。

String和StringBuffer、StringBuilder的区别在于String声明的是不可变的对象，每次操作都会生成新的String对象，然后将指针指向新的String对象。而StringBuffer、StringBuilder可以在原有对象的基础上进行操作，所以在经常改变字符串内容的情况下最好不要使用String。

StringBuffer和StringBuilder最大的区别在于 ， StringBuffer是线程安全的 ，而 StringBuilder是非线程安全的 ，但 StringBuilder 的性能却高于StringBuffer，所以在单线程环境下推荐使用StringBuilder，多线程环境下推荐使用StringBuffer。

2、 String、StringBuffer和StringBuilder区别（类似上一题）

参考答案：

1、数据可变和不可变

String底层使用一个不可变的字符数组private final char value[]; 所以它内容不可变。

StringBuffer和StringBuilder 都继承了AbstractStringBuilder底层使用的是可变字符数组：char[] value。

2、线程安全

StringBuilder是线程不安全的，效率较高；而StringBuffer是线程安全的，效率较低。通过他们的append() 方法来看，StringBuffer是有同步锁，而StringBuilder没有：
1
2
3
4
5
6
7
8
9
10
11
12
<a href="/profile/992988"data-card-uid="992988"class=""target="_blank"from-niu="default"data-card-index="3">@Override
public synchronized StringBuffer append(Object obj) { 
    toStringCache = null;   
    super.append(String.valueOf(obj));
    return this;
}
 
</a><a href="/profile/992988"data-card-uid="992988"class=""target="_blank"from-niu="default"data-card-index="4">@Override
public StringBuilder append(String str) { 
    super.append(str);
    return this;
}</a>
3、相同点

StringBuilder与StringBuffer有公共父类AbstractStringBuilder 。

最后，操作可变字符串速度：StringBuilder > StringBuffer > String ，这个答案就显得不足为奇了。

3、String str="i"与 String str=new String("i")一样吗？

参考答案：

不一样，因为内存的分配方式不一样。String str="i"的方式，Java虚拟机会将其分配到常量池中；而 String str=new String("i") 则会被分到堆内存中。

代码示例：
1
2
3
4
5
String x = "叶痕秋"; 
String y = "叶痕秋";
String z = new String(" 叶 痕 秋 "); 
System.out.println(x == y); // true 
System.out.println(x == z); // false
String x = "叶痕秋"的方式，Java虚拟机会将其分配到常量池中，而常量池中没有重复的元素，比如当执行“叶痕秋”时，java虚拟机会先在常量池中检索是否已经有“叶痕秋”，如果有那么就将“叶痕秋”的地址赋给变量，如果没有就创建一个，然后在赋给变量。
而String z = new String(“叶痕秋”) 则会被分到堆内存中，即使内容一样还是会创建新的对象。

4、String 类的常用方法都有那些？

参考答案：

indexOf()：返回指定字符的索引。

charAt()：返回指定索引处的字符。

replace()：字符串替换。

trim()：去除字符串两端空白。

split()：分割字符串，返回一个分割后的字符串数组。

getBytes()：返回字符串的byte类型数组。

length()：返回字符串长度。

toLowerCase()：将字符串转成小写字母。

toUpperCase()：将字符串转成大写字符。

substring()：截取字符串。

equals()：字符串比较。

5、String s = new String("xyz");创建了几个StringObject？是否可以继承String类？

参考答案：

两个或一个都有可能，”xyz”对应一个对象，这个对象放在字符串常量缓冲区，常量”xyz”不管出现多少遍，都是缓冲区中的那一个。new String每写一遍，就创建一个新的对象，它使用常量”xyz”对象的内容来创建出一个新String对象。如果以前就用过’xyz’，那么这里就不会创建”xyz”了，直接从缓冲区拿，这时创建了一个String Object；但如果以前没有用过"xyz"，那么此时就会创建一个对象并放入缓冲区，这种情况它创建两个对象。

String类不能被继承，因为String默认final修饰，是不可继承的。

6、下面这条语句一共创建了多少个对象：String s="a"+"b"+"c"+"d"

参考答案：

先看下下面的代码：
1
2
3
4
5
6
String s1 = "a";
String s2 = s1 + "b";
String s3 = "a" + "b";
 
System.out.println(s2 == "ab");   //false
System.out.println(s3 == "ab");   //true
第一条语句打印的结果为false，第二条语句打印的结果为true，这说明javac编译可以对字符串常量直接相加的表达式进行优化，不必要等到运行期再去进行加法运算处理，而是在编译时去掉其中的加号，直接将其编译成一个这些常量相连的结果。

题目中的第一行代码被编译器在编译时优化后，相当于直接定义了一个”abcd”的字符串，所以，上面的代码应该只创建了一个String对象。

看下面的两行代码：
1
2
String s ="a" + "b" +"c" + "d";  
System.out.println(s== "abcd");
最终打印的结果为true。

7、简述Java中的集合

Collection下：List系(有序、元素允许重复)和Set系(无序、元素不重复)

  • set根据equals和hashcode判断，一个对象要存储在Set中，必须重写equals和hashCode方法

Map下：HashMap线程不同步；TreeMap线程同步

Collection系列和Map系列：Map是对Collection的补充，两个没什么关系

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

List与Set具有相似性，它们都是单列元素的集合，所以，它们有一个共同的父接口，叫Collection。

1、Set里面不允许有重复的元素

即不能有两个相等（注意，不是仅仅是相同）的对象，即假设Set集合中有了一个A对象，现在我要向Set集合再存入一个B对象，但B对象与A对象equals相等，则B对象存储不进去，所以，Set集合的add方法有一个boolean的返回值，当集合中没有某个元素，此时add方法可成功加入该元素时，则返回true，当集合含有与某个元素equals相等的元素时，此时add方法无法加入该元素，返回结果为false。Set取元素时，不能细说要取第几个，只能以Iterator接口取得所有的元素，再逐一遍历各个元素。

2、List表示有先后顺序的集合

注意，不是那种按年龄、按大小、按价格之类的排序。当我们多次调用add(Obje)方法时，每次加入的对 象就像火车站买票有排队顺序一样，按先来后到的顺序排序。有时候，也可以插队，即调用add(intindex,Obj e)方法，就可以指定当前对象在集合中的存放位置。一个对象可以被反复存储进List 中，每调用一次add方法，这个对象就被插入进集合中一次，其实，并不是把这个对象本身存储进了集 合中，而是在集合中用一个索引变量指向这个对象，当这个对象被add多次时，即相当于集合中有多个 索引指向了这个对象。List除了可以用Iterator接口取得所有的元素，再逐一遍历各个元素之外，还可以 调用get(index i)来明确说明取第几个。

3、Map与List和Set不同

它是双列的集合，其中有put方法，定义如下：put(obj key,obj value)，每次存储时，要存储一对key/value，不能存储重复的key，这个重复的规则也是按equals比较相等。取则可以根据key获得相应 的value，即get(Object key)返回值为key所对应的value。另外，也可以获得所有的key的结合，还可以获得所有的value的结合，还可以获得key和value组合成的Map.Entry对象的集合。

总结

List以特定次序来持有元素，可有重复元素。Set无法拥有重复元素，内部排序。Map保存key-value值，value可多值。

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

Set里的元素是不能重复的，元素重复与否是使用equals()方法进行判断的。

==操作符专门用来比较两个变量的值是否相等，也就是用于比较变量所对应的内存中所存储的数值是否相同，要比较两个基本类型的数据或两个引用变量是否相等，只能用==操作符。

equals方法是用于比较两个独立对象的内容是否相同，就好比去比较两个人的长相是否相同，它比较的 两个对象是独立的。

比如：两条new语句创建了两个对象，然后用a/b这两个变量分别指向了其中一个对象，这是两个不同的对象，它们的首地址是不同的，即a和b中存储的数值是不相同的，所以，表达式a==b将返回false，而这两个对象中的内容是相同的，所以，表达式a.equals(b)将返回true。

10、ArrayList和LinkedList区别？

数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。

随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。

增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

11、ArrayList 和Vector的区别是什么？

线程安全方面：Vector使用了Synchronized来实现线程同步，是线程安全的，而ArrayList是非线程安全的。

性能方面：ArrayList在性能方面要优于 Vector。

扩容方面：ArrayList和Vector都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加1倍，而ArrayList只会增加50%。

12、ArrayList，Vector，LinkedList的存储性能和特性

ArrayList和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。

Vector由于使用了synchronized 方法（线程安全），通常性能上较ArrayList差。

而LinkedList使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，索引就变慢了，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。LinkedList也是线程不安全的， LinkedList提供了一些方法，使得LinkedList可以被当作堆栈和队列来使用。

13、HashMap和HashTable的区别

1、两者父类不同

HashMap是继承自AbstractMap类，而Hashtable是继承自Dictionary类。不过它们都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

2、对外提供的接口不同

Hashtable比HashMap多提供了elments() 和contains() 两个方法。 elments() 方法继承自Hashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue() 就只是调用了一下contains() 方法。

3、对null的支持不同

Hashtable：key和value都不能为null。

HashMap：key可以为null，但是这样的key只能有一个，因为必须保证key的唯一性；可以有多个key值对应的value为null。

4、安全性不同

HashMap是线程不安全的，在多线程并发的环境下，可能会产生死锁等问题，因此需要开发人员自 己处理多线程的安全问题。

Hashtable是线程安全的，它的每个方法上都有synchronized 关键字，因此可直接用于多线程中。

虽然HashMap是线程不安全的，但是它的效率远远高于Hashtable，这样设计是合理的，因为大部分的使用场景都是单线程。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。

ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。

5、初始容量大小和每次扩充容量大小不同

6、计算hash值的方法不同

14、Java中的同步集合与并发集合有什么区别？

同步集合与并发集合都为多线程和并发提供了合适的线程安全的集合，不过并发集合的可扩展性更高。

在Java1.5之前程序员们只有同步集合来用且在多线程并发的时候会导致争用，阻碍了系统的扩展性。Java5介绍了并发集合ConcurrentHashMap，不仅提供线程安全还用锁分离和内部分区等现代技术提高了可扩展性。不管是同步集合还是并发集合他们都支持线程安全，他们之间主要的区别体现在性能和可扩展性，还有他们如何实现的线程安全上。

同步HashMap，Hashtable ，HashSet，Vector，ArrayList相比他们并发的实现（ConcurrentHashMap，CopyOnWriteArrayList，CopyOnWriteHashSet）会慢得多。造成如此慢的主要原因是锁，同步集合会把整个Map或List锁起来，而并发集合不会。并发集合实现线程安全是通过使用先进的和成熟的技术像锁剥离。

比如ConcurrentHashMap会把整个Map划分成几个片段，只对相关的几个片段上锁，同时允许多线程访问其他未上锁的片段。

同样的，CopyOnWriteArrayList 允许多个线程以非同步的方式读，当有线程写的时候它会将整个List 复制一个副本给它。

如果在读多写少这种对并发集合有利的条件下使用并发集合，这会比使用同步集合更具有可伸缩性。

15、Java中的集合及其继承关系

关于集合的体系是每个人都应该烂熟于心的，尤其是对我们经常使用的List，Map的原理更该如此。这里我们看这张图即可：

16、poll()方法和remove()方法区别?

poll()和remove()都是从队列中取出一个元素，但是poll()在获取元素失败的时候会返回空，但是remove()失败的时候会抛出异常。

17、ArrayList和Array有什么区别?

Array可以容纳基本类型和对象，而ArrayList只能容纳对象。

ArrayList 是Java集合框架类的一员，可以称它为一个动态数组。array是静态的，所以一个数据一旦创建就无法更改他的大小。

18、Comparator和Comparable的区别?

相同点

都是用于比较两个对象“顺序”的接口

都可以使用Collections.sort()方法来对对象集合进行排序

不同点

Comparable位于java.lang包下，而Comparator则位于java.util包下

Comparable 是在集合内部定义的方法实现的排序，Comparator 是在集合外部实现的排序

总结

使用Comparable接口来实现对象之间的比较时，可以使这个类型（设为A）实现Comparable接口，并可以使用Collections.sort()方法来对A类型的List进行排序，之后可以通过a1.comparaTo(a2)来比较两个对象；当使用Comparator接口来实现对象之间的比较时，只需要创建一个实现Comparator接口的比较器（设为AComparator），并将其传给Collections.sort()方法即可对A类型的List进行排序，之后也可以通过调用比较AComparator.compare(a1, a2)来比较两个对象。可以说一个是自己完成比较，一个是外部程序实现比较的差别而已。

用Comparator是策略模式（strategy design pattern），就是不改变对象自身，而用一个策略对象（strategy object）来改变它的行为。

比如：你想对整数采用绝对值大小来排序，Integer是不符合要求的，你不需要去修改Integer 类（实际上你也不能这么做）去改变它的排序行为，这时候只要（也只有）使用一个实现了Comparator接口的对象来实现控制它的排序就行了。

两种方式，各有各的特点：使用Comparable方式比较时，我们将比较的规则写入了比较的类型中，其特点是高内聚。但如果哪天这个规则需要修改，那么我们必须修改这个类型的源代码。如果使用Comparator方式比较，那么我们不需要修改比较的类，其特点是易维护，但需要自定义一个比较器， 后续比较规则的修改，仅仅是改这个比较器中的代码即可。

19、HashMap的实现原理

HashMap的原理：HashMap基于Hash算法，我们通过put(key,value)存储，get(key)来获取。当传入key时，HashMap会根据key.hashCode()计算出hash值，根据hash值将value保存在bucket里。当计算出的hash值相同时怎么办呢，我们称之为Hash冲突，HashMap的做法是用链表和红黑树存储相同hash值的value。当Hash冲突的个数比较少时，使用链表，否则使用红黑树。

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

下面介绍下HashMap的结构：

Java7的HashMap结构：

大方向上， HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色的实体是嵌套类Entry的实例，Entry包含四个属性：key, value, hash值和用于单向链表的next。

  • capacity：当前数组容量，始终保持2^n，可以扩容，扩容后数组大小为当前的2倍。

  • oadFactor：负载因子，默认为0.75。

  • threshold：扩容的阈值，等于capacity * loadFactor

Java8对HashMap进行了一些修改，最大的不同就是利用了红黑树，所以其由数组+链表+红黑树组成。

根据Java7 HashMap的介绍，我们知道，查找的时候，根据hash值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在Java8中，当链表中的元素超过了8个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为O(logN)。

Java8的HashMap结构：

小结：

JDK7与JDK8（及JDK8以后）的HashMap有什么区别：

  • 链表新节点插入链表的顺序不同（JDK7是插入头结点，JDK8因为要把链表变为红黑树所以采用插入尾节点）

  • resize的逻辑修改（JDK7会出现死循环，JDK8不会）

扩展讲一下

1、HashMap的几个重要知识点

HashMap是无序且不安全的数据结构。

HashMap是以key–value对的形式存储的，key值是唯一的（可以为null），一个key只能对应着一个value，但是value是可以重复的。

HashMap如果再次添加相同的key值，它会覆盖key值所对应的内容，这也是与HashSet不同的一点，Set通过add添加相同的对象，不会再添加到Set中去。

HashMap 提供了get方法，通过key值取对应的value值，但是HashSet只能通过迭代器Iterator来遍历数据，找对象。

2、HashMap的默认负载因子
1
2
3
4
5
6
7
8
9
 /**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
*默认的负载因子是0.75f,也就是75% 负载因子的作用就是计算扩容阈值用，比如说使用
*无参构造方法创建的HashMap 对象，他初始长度默认是16  阈值 = 当前长度 * 0.75  就
*能算出阈值，当当前长度大于等于阈值的时候HashMap就会进行自动扩容
*/
经常会问的一个问题： 为什么HashMap的默认负载因子是0.75，而不是0.5或者是整数1呢？

阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 根据HashMap的扩容机制，他会保证容量(capacity)的值永远都是2的幂 为了保证负载因子x容量的结果是一个整数，这个值是0.75(3/4)比较合理，因为这个数和任何2的次幂乘积结果都是整数。

理论上来讲，负载因子越大，导致哈希冲突的概率也就越大，负载因子越小，费的空间也就越大,这是一个无法避免的利弊关系，所以通过一个简单的数学推理，可以测算出这个数值在0.75左右是比较合理的

另一种说法：当负载因子为1.0时，意味着只有当hashMap装满之后才会进行扩容，虽然空间利用率有大的提升，但是这就会导致大量的hash冲突，使得查询效率变低。当负载因子为0.5或者更低的时候，hash冲突降低，查询效率提高，但是由于负载因子太低，导致原来只需要1M的空间存储信息，现在用了2M的空间。最终结果就是空间利用率太低。（负载因子是0.75的时候，这是时间和空间的权衡，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度也比较低，提升了空间效率 ）

3、HashMap的扩容机制

写数据之后会可能触发扩容，HashMap结构内，我记得有一个记录当前数据量的字段，这个数据量字段到达扩容阈值的话，它就会触发扩容的操作。

阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 。

当HashMap中table数组(也称为桶)长度 >= 阈值(threshold) 就会自动进行扩容。扩容的规则是这样的，因为table数组长度必须是2的次方数，扩容其实每次都是按照上一次tableSize位运算得到的就是做一次左移1位运算，假设当前tableSize是16的话 16转为二进制再向左移一位就得到了32 即 16 << 1 == 32 即扩容后的容量，也就是说扩容后的容量是当前容量的两倍，但记住HashMap的扩容是采用当前容量向左位移一位（newtableSize = tableSize << 1），得到的扩容后容量，而不是当前容量x2

为什么计算扩容后容量要采用位移运算呢，怎么不直接乘以2呢？

因为cpu毕竟它不支持乘法运算，所有的乘法运算它最终都是再指令层面转化为了加法实现的，这样效率很低，如果用位运算的话对cpu来说就非常的简洁高效。

4、HashMap中散列表数组初始长度
1
2
3
4
5
6
7
8
9
10
11
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  
/**
* HashMap中散列表数组初始长度为 16 (1 << 4)
* 创建HashMap的时候可以设置初始化容量和设置负载因子，
* 但HashMap会自动优化设置的初始化容量参数，确保初始化
* 容量始终为2的幂
*/
为啥HashMap中初始化大小为什么是16呢？

首先我们看hashMap的源码可知当新put一个数据时会进行计算位于table数组(也称为桶)中的下标：

int index =key.hashCode()&(length-1); hahmap每次扩容都是以 2的整数次幂进行扩容，因为是将二进制进行按位于，(16-1) 是 1111,末位是1，这样也能保证计算后的index既可以是奇数也可以是偶数，并且只要传进来的key足够分散，均匀那么按位于的时候获得的index就会减少重复，这样也就减少了hash的碰撞以及hashMap的查询效率。

那么既然16可以，是不是只要是2的整数次幂就可以呢？

答案是肯定的。那为什么不是8,4呢？ 因为是8或者4的话很容易导致map扩容影响性能，如果分配的太大的话又会浪费资源，所以就使用16作为初始大小。

5、HashMap存储原理与存储流程

1）HashMap存储原理

  • 获取到传过来的key，调用hash算法获取到hash值；

  • 获取到hash值之后调用indexFor方法，通过获取到的hash值以及数组的长度算出数组的下标 (把哈希值和数组容量转换为二进，再在数组容量范围内与哈希值进行一次与运算，同为1则1，不然则为0，得出数组的下标值，这样可以保证计算出的数组下标不会大于当前数组容量)；

  • 把传过来的key和value存到该数组下标当中；

  • 如该数组下标下以及有值了，则使用链表，jdk7是把新增元素添加到头部节点 jdk8则添加到尾部节点。

2）HashMap存储流程

前面寻址算法都是一样的，根据key的hashcode经过高低位异或之后的值，再按位与 &(table.lingth - 1),得到一个数组下标，然后根据这个数组下标内的状况，状况不同，然后情况也不同，大概分为了4种状态：

（1）第一种就是数组下标下内容为空：

这种情况没什么好说的，为空据直接占有这个slot槽位就好了，然后把当前.put方法传进来的key和value包装成一个node对象,放到这个slot中就好了。

（2）第二种情况就是数组下标下内容不为空，但它引用的node还没有链化：

这种情况下先要对比一下这个node对象的key与当前put对象的key是否完全.相等，如果完全相等的情况下，就行进行replace操作，把之前的槽位中node.下的value替换成新的value就可以了，否则的话这个put操作就是一个正儿.八经的hash冲突,这种情况在slot槽位后面追加一个node就可以了,用尾插法 ( 前面讲过，jdk7是把新增元素添加到头部节点，而jdk8则添加到尾部节点)。

（3）第三种就是该数组下标下内容已经被链化了：

这种情况和第二种情况处理很相似，首先也是迭代查找node，看看链表上中元素的key，与当前传过来的key是否完全一致，如果完全一致的话还是repleace操作，用put过来的新value替换掉之前node中的value，否则的话就是一致迭代到链表尾节点也没有匹配到完全一致的node，就和之前的一样，把put进来数据包装成node追加到链表的尾部，再检查一下当前链表的长度，有没有达到树化阈值，如果达到了阈值就调用一个树化方法，树化操作都是在这个方法里完成的。

（4）第四种情况就是冲突很严重的情况下，这个链表已经转化成红黑树了：

红黑树就比较复杂 要将清楚这个红黑树还得从TreeNode说起 TreeNode继承了Node结构，在Node基础上加了几个字段，分别是指向父节点parent字段，指向左子节点left字段，指向右子节点right字段，还有一个表示颜色的red字段，这就是TreeNode的基本结构，然后红黑树的插入操作，首先找到一个合适的插入点，就是找到插入节点的父节点，然后红黑树它又满足二叉树的所有特性，所以找这个父节点的操作和二叉树排序是完全一致的，然后说一下这个二叉树排序，其实就是二分查找算法映射出来的结构，就是一个倒立的二叉树，然后每个节点都可以有自己的子节点，本且左节点小于但前节点，右节点大于当前节点，然后每次向下查找一层就能那个排除掉一半的数据，查找效率非常的高效，当查找的过程中也是分情况的。

  • 首先第一种情况就是一直向下探测，直到查询到左子树或者右子树位null，说明整个树中，并没有发现node链表中的key与当前put key一致的TreeNode,那此时探测节点就是插入父节点的所在了，然后就是判断插入节点的hash值和父节点的hash值大小决定插入到父节点的左子树还是右子树。当然插入会打破平衡，还需要一个红黑树的平衡算法保持平衡。

  • 其次第二种情况就是根节点在向下探测过程中发现TreeNode中key与当前put的key完全一致，然后就也是一次repleace操作，替换value。

6、JDK8中HashMap为什么要引入红黑树？

主要就是为了解决jdk1.8以前hash冲突所导致的链化严重的问题，因为链表结构的查询效率是非常低的，不像数组，能通过索引快速找到想要的值，链表只能挨个遍历，当hash冲突非常严重的时候，链表过长的情况下，就会严重影响查询性能，本身散列列表最理想的查询效率为O(1)，当时链化后链化特别严重，他就会导致查询退化为O(n)为了解决这个问题所以jdk8中的HashMap添加了红黑树来解决这个问题，当链表长度>=8的时候链表就会变成红黑树，红黑树其实就是一颗特殊的二叉排序树嘛，这个时间复杂…反正就是要比列表强很多。

20、HashMap自动扩容

如果在初始化HashMap中没有指定初始容量，那么默认容量为16，但是如果后来HashMap中存放的数量超过了16，那么便会有大量的hash冲突；在HashMap中有自动扩容机制，如果当前存放的数量大于某个界限，HashMap便会调用resize()方法，扩大HashMap的容量。

当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。

HashMap的capacity必须满足是2的N次方，如果在构造函数内指定的容量n不满足，HashMap会通过下面的算法将其转换为大于n的最小的2的N次方数。
1
2
3
4
5
6
7
8
9
10
// 减1→移位→按位或运算→加1返回
static final int tableSizeFor(int cap) { 
    int n = cap - 1;
    n |= n >>> 1; 
    n |= n >>> 2; 
    n |= n >>> 4; 
    n |= n >>> 8; 
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

21、HashMap线程安全吗？

HashMap是非线程安全的，如果在多线程环境下，可以使用HashTable，HashTable中所有CRUD操作 都是线程同步的，同样的，线程同步的代价就是效率变低了。

再Java 5以后，有了一个线程安全的HashMap——ConcurrentHashMap，ConcurrentHashMap相对于HashTable来说，ConcurrentHashMap将hash表分为16个桶（默认值），诸如get，put，remove等常用操作只锁当前需要用到的桶。试想，原来只能一个线程进入，现在却能同时16个写线程进入（写线程才需要锁定，而读线程几乎不受限制，并发性的提升是显而易见。

快速失败(fast-fail)

“快速失败”也就是fail-fast，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。例如：假设存在两个线程（线程1、 线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出ConcurrentModificationException 异常，从而产生fail-fast机制。

在HashMap的forEach方法中有以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<a href="/profile/992988"data-card-uid="992988"class=""target="_blank"from-niu="default"data-card-index="5">@Override
public void forEach(BiConsumer<? super K, ? super V> action) { 
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException(); 
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) 
                action.accept(e.key, e.value);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}</a>
 在上面提到，modCount是记录每次HashMap结构修改。 forEach方***在在进入for循环之前，将modCount赋值给mc，如果在for循环之后，HashMap的结构变化了，那么导致的结果就是modCount != mc，则抛出ConcurrentModificationException()异常。