1、Java异常以及常用工具类体系。异常处理机制主要回答了三个问题?

  答:1)、第一个是异常类型回答了什么被抛出。

    2)、第二个是异常堆栈跟踪回答了在哪里抛出。

    3)、第三个是异常信息回答了为什么被抛出。Throwable是所有异常体系的顶级父类,包含了Error类和Exception类。从概念角度分析Java的异常处理机制。

2、Java的异常体系,Error和Exception的区别?

  答:1)、Error,程序无法处理的系统错误,编译器不做检查。表示系统致命的错误,程序无法处理这些错误,Error类一般是指与JVM相关的问题,如果系统奔溃、虚拟机错误、内存空间不足、方法调用栈溢出等等错误。
    2)、Exception,程序可以处理的异常,捕获后可能恢复。遇到此类异常,尽可能去处理,使程序恢复运行,而不应该随意中止异常。
    3)、总结,Error是程序无法处理的错误,Exception是可以处理的异常。

3、Exception主要包含两类,一类是RuntimeException、另一类是非RuntimeException。

  答:1)、RuntimeException(运行时异常)异常表示不可预知的,程序应当自行避免,例如数组下标越界,访问空指针异常等等。
    2)、非RuntimeException(非运行时异常)异常是可以预知的,从编译器校验的异常。从编译器角度来说是必须处理的异常,如果不处理此类异常,编译不能够通过的。

4、Java的异常体系,从责任角度来看。

  答:Error属于JVM需要负担的责任。RuntimeException是程序应该负担的责任。Checked Exception可检查异常是Java编译器应该负担的责任。

5、常见Error以及Exception。RuntimeException运行时异常。

  答:1)、第一种,NullPointerException空指针引用异常。
    2)、第二种,ClassCastException类型强转转换异常。
    3)、第三种,IllegalArgumentException传递非法参数异常。
    4)、第四种,IndexOutOfBoundsException下标越界异常。
    5)、第五种,NumberFormatException数字格式异常。

6、非RuntimeException非运行时异常。

  答:1)、第一种,ClassNotFoundException,找不到指定的class的异常。
    2)、第二种,IOException,IO操作异常。

7、Error错误异常。

  答:1)、第一种,NoClassDefFoundError,找不到class定义的异常。造成的原因包含,类依赖的class或者jar包不存在。类文件存在,但是存在不同的域中。大小写问题,javac编译的时候无视大小写的,很有可能编译出来的class文件就与想要的不一样。
    2)、第二种,StackOverflowError,深递归导致栈被耗尽而抛出的异常。
    3)、第三种,OutOfMemoryError,内存溢出异常。

8、Java的异常处理机制,Exception的处理机制。

  答:1)、第一步、抛出异常,创建异常对象,交由运行时系统处理。当一个方法出现错误引发异常的时候,方法创建异常对象,并交付给运行时系统,系统对象中包含了异常类型,异常出现时的程序状态等异常信息,运行时系统负责寻找处置异常的代码并执行。  

    2)、第二步、捕获异常,寻找合适的异常处理器处理异常,否则终止运行。方法抛出异常以后,运行时系统将转为寻找合适的异常处理器,即ExceptionHandle。潜在的异常处理是异常发生时依次存留在调用栈方法的集合,当异常处理器所能处理的异常类型与抛出的异常类型相符的时候,即为合适的异常处理器,运行时系统从发生异常的方法开始依次回查调用栈中的方法直至找到含有异常处理器的方法并执行。当运行时系统遍历了调用栈都没有找到合适的异常处理器,则运行时系统终止,java程序终止。

9、Java异常的处理规则。

  答:具体明确,抛出的异常应能通过异常类名和message准确说明异常的类型和产生异常的原因。
    提早抛出,应尽可能早的发现并抛出异常,便于精准定位问题。
    延迟捕获,异常的捕获和处理应该尽可能延迟,让掌握更多信息的作用域来处理异常。

10、try-catch的性能问题。Java异常处理消耗性能的地方。

  答:第一点、try-catch块影响JVM的优化。
    第二点、异常对象实例需要保存栈快照等等信息,开销较大,这是一个相对较重的操作。所以一定要捕获可能出现异常的代码,不要使用一个大大的try-ccatch包起来整段代码,不要使用异常控制代码的流程,因为此效率远远没有if-else判断的效率高。

11、集合之List和Set的区别,如下所示。

11.1、备注:线程安全和线程不安全的集合:

Vector、HashTable、Properties是线程安全的。
ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等都是线程不安全的集合类型。

1)、注意:为了保证集合线程是安全的,效率就比较低;线程不安全的集合效率相对会高一些。

2)、如果需要保证集合既是安全的而且效率高,可以使用Collections为我们提出了解决方案,把这些集合包装成线程安全的集合。

3)、Collections的工具类,将自己创建的集合类实例传入进去,便可以包装成一个线程安全的集合类实例。因为SynchronizedMap有一个Object mutex互斥对象成员,对里面的公共方法使用synchronized对mutex进行加锁操作。相比SynchronizedMap使用的synchronized对mutex进行加锁操作,hashtable线程安全的原因,是在公有的方法都加入了synchronized修饰符,此时获取的是方法调用者的锁。SynchronizedMap和hashtable的原理几乎相同,唯一的区别就是锁定的对象不同,因此这两者在多线程环境下,由于都是串行执行的,效率比较低下,此时可以学习ConcurrentHashMap。

4)、无论是Hashtable还是Collections的工具类SynchronizedMap,当多线程并发的情况下,都要竞争同一把锁,导致效率极其低下,而在jdk1.5之后,为了改进hashTable的痛点,ConcurrentHashMap应运而生,

11.2、Tree的核心在于排序,保证元素排序。

答:1)、自然排序,让对象所属的类去实现comparable接口,无参构造,基于元素对象自身实现的comparable接口的自然排序。
  2)、比较器接口comparator,带参构造,更为灵活,不与单元绑定的comparator接口客户化排序。

自然排序代码实现,如下所示:

  1 package com.thread; 
  2  
  3 import java.util.Set; 
  4 import java.util.TreeSet; 
  5  
  6 /** 
  7  * 自然排序,实现了Comparable自然排序的接口,实现了该接口就要实现equals和hashcode方法和compareTo方法。 
  8  * <p> 
  9  * <p> 
 10  * <p> 
 11  * 为了使Customer类在添加了treeSet之后可以正确排序,要求Customer类里面的equals方法和compareTo方法按照相同的规则 
 12  * 来比较两个对象是否相等。 
 13  */ 
 14 public class Customer implements Comparable { 
 15  
 16     private String name; 
 17     private int age; 
 18  
 19     public Customer(String name, int age) { 
 20         this.name = name; 
 21         this.age = age; 
 22     } 
 23  
 24     public String getName() { 
 25         return name; 
 26     } 
 27  
 28     public void setName(String name) { 
 29         this.name = name; 
 30     } 
 31  
 32     public int getAge() { 
 33         return age; 
 34     } 
 35  
 36     public void setAge(int age) { 
 37         this.age = age; 
 38     } 
 39  
 40     @Override 
 41     public boolean equals(Object obj) { 
 42         // 两个对象相等返回true 
 43         if (this == obj) { 
 44             return true; 
 45         } 
 46         if (!(obj instanceof Customer)) { 
 47             return false; 
 48         } 
 49         final Customer other = (Customer) obj; 
 50  
 51         if (this.name.equals(other.name) && this.age == other.getAge()) { 
 52             return true; 
 53         } else { 
 54             return false; 
 55         } 
 56     } 
 57  
 58     @Override 
 59     public int hashCode() { 
 60         // 重新了equals方法,就要重新hashcode方法 
 61         int result; 
 62         result = (name == null) ? 0 : name.hashCode(); 
 63         result = 29 * result + age; 
 64         // 如果两个对象是相等的,那么hashcode返回值必须是相等的 
 65         return result; 
 66     } 
 67  
 68     @Override 
 69     public int compareTo(Object o) { 
 70         // compareTo返回值大于0,说明Customer1大于Customer2,反之Customer1小于Customer2 
 71         // 如果等于0,Customer1等于Customer2 
 72         Customer other = (Customer) o; 
 73         // 先按照name属性排序 
 74         if (this.name.compareTo(other.getName()) > 0) { 
 75             return 1; 
 76         } 
 77         if (this.name.compareTo(other.getName()) < 0) { 
 78             return -1; 
 79         } 
 80  
 81         // 再按照age属性排序 
 82         if (this.age > other.getAge()) { 
 83             return 1; 
 84         } 
 85         if (this.age < other.getAge()) { 
 86             return -1; 
 87         } 
 88         return 0; 
 89     } 
 90  
 91     public static void main(String[] args) { 
 92         Set<Customer> set = new TreeSet<>(); 
 93         Customer customer1 = new Customer("tom", 16); 
 94         Customer customer2 = new Customer("tom", 19); 
 95         Customer customer3 = new Customer("tom", 20); 
 96         set.add(customer1); 
 97         set.add(customer2); 
 98         set.add(customer3); 
 99  
100         // 循环遍历 
101         for (Customer c : set) { 
102             System.out.println(c.getName() + " , " + c.getAge()); 
103         } 
104     } 
105 }

客户化排序,实现Comparator,然后实现compare方法:

 1 package com.thread; 
 2  
 3 import java.util.*; 
 4  
 5 /** 
 6  * 客户化排序,实现Comparator,然后实现compare方法 
 7  */ 
 8 public class CustomerComparator implements Comparator<Customer> { 
 9  
10     @Override 
11     public int compare(Customer c1, Customer c2) { 
12         // 对姓名进行排序 
13         if (c1.getName().compareTo(c2.getName()) > 0) { 
14             return -1; 
15         } 
16         if (c1.getName().compareTo(c2.getName()) < 0) { 
17             return 1; 
18         } 
19  
20         // 对年龄进行排序 
21         if (c1.getAge() - c2.getAge() > 0) { 
22             return -1; 
23         } 
24         if (c1.getAge() - c2.getAge() < 0) { 
25             return 1; 
26         } 
27         return 0; 
28     } 
29  
30     public static void main(String[] args) { 
31         // 此时既使用了自然排序,也使用了客户化排序, 
32         // 在客户化排序和自然排序共存的情况下,最终结果以客户化排序优先。 
33         // 可以查看TreeMap源码的get(Object key) -> getEntry(key)方法。 
34         // 可以看到先使用客户化排序得到的结果。 
35         Set<Customer> set = new TreeSet<>(new CustomerComparator()); 
36         Customer customer1 = new Customer("张三三", 16); 
37         Customer customer2 = new Customer("李四四", 19); 
38         Customer customer3 = new Customer("王五五", 20); 
39         set.add(customer1); 
40         set.add(customer2); 
41         set.add(customer3); 
42         Iterator<Customer> iterator = set.iterator(); 
43         while (iterator.hasNext()) { 
44             Customer next = iterator.next(); 
45             System.out.println(next.getName() + " " + next.getAge()); 
46         } 
47     } 
48  
49 }

12、Map集合。

答:Map集合用于保存具有映射关系的数据,Map保存的数据都是key-value对的形式的,也就是key-value组成的键值对形式的,Map里面的key是不可以重复的,key是用于标示集合里面的每项数据的,Map里面的value则是可以重复的。

13、Hashtable、HashMap、ConcurrentHashMap的区别,如下所示:

答:1)、HashMap,存储特点是键值对映射,在Java8以前,是数组+链表的组成,HashMap结合了数组和链表的优势进行编写的。数组的特点是查询快,增删慢,而链表的特点是查询慢,增删快。HashMap是非Synchronized,所以是线程不安全的,但是效率高。HashMap是由数组和链表组成的,HashMap的数组长度在未赋初始值的时候,默认长度是16的,一个长度为16的数组中,每个元素存储的就是链表的头节点,通过类似于hash(key.hashCode) % len,哈希函数取模的操作获得要添加的元素所要存放的数组的位置,实际上,HashMap的哈希算法是通过位运算来进行的,相对于取模运算呢,效率更高。这里面有一个极端的情况,如果添加到哈希表里面的不同的值的键位来通过哈希散列运算,总是得出相同的值即分配到同一个桶中,这样会是某个桶中链表的长度变得很长,由于链表查询需要从头部开始遍历,因此,在最坏的情况下呢,HashMap性能恶化,从O(1)变成了O(n)。

    HashMap,存储特点是键值对映射,在Java8以后,HashMap采用了数组 + 链表 + 红黑树的组成。Java8以后使用常量TREEIFY_THRESHOLD来控制是否将链表转换为红黑树,来存储数据,这意味着,即使在最坏的情况下,HashMap的性能从O(n)提高到O(logn)。

    HashMap的成员变量,Node<K,V>[] table可以看作是Node<K,V>这个数组和链表组成的复合结构,数组被分为一个个的bucket桶,通过hash值决定了键值对在这个数组的寻址,hash值相同的键值对则以链表的形式来存储,而链表的大小超过TREEIFY_THRESHOLD =8这个值的时候,就会被改造成红黑树,而当某个桶上面的元素总数因为删除变得低于阈值UNTREEIFY_THRESHOLD =6之后,红黑树又被转换为链表,以保证更高的性能。

  2)、Hashtable是线程安全的,是因为在方法都加了synchronized关键字,和Collections.synchronizedMap(map)效果一样,都是串行执行的,效率比较低,唯一的区别就是锁定的对象不同而已。为了提升多线程下的执行性能,引入了ConcurrentHashMap。
  3)、ConcurrentHashMap,无论是Hashtable还是使用synchronizedMap包装了的hashMap,当多线程并发的情况下,都要竞争同一把锁,导致效率极其低下,而在jdk1.5以后,为了改进HashTable的缺点,引入了ConcurrentHashMap。

  4)、如何优化Hashtable呢?如何设计ConcurrentHashMap呢?

    a)、通过锁细粒度化,将整锁拆解成多个锁进行优化。对象锁之间是不相互制约的,因此,我们可以将原本一个锁的行为拆分多个锁,早期的ConcurrentHashMap也是这样做的,ConcurrentHashMap早期使用的是分段锁技术(由数组和链表组成),通过分段锁Segment来实现,将锁一段一段的进行存储,然后给每一段数据配一把锁即Segment,当一个线程占用一把锁即Segment的时候,然后访问其中一段数据的时候呢,位于其他Segment的数据也能被其他线程同时访问,默认是分配16个Segment,理论上比Hashtable效率提升了16倍,相比于早期的HashMap,就是将hashMap的table数组逻辑上拆分成多个子数组,每个子数组配置一把锁,线程在获取到某把分段锁的时候,比如,获取到编号为8的Segment之后呢,才能操作这个子数组,而其他线程想要操作该子数组的时候,只能被阻塞,但是如果其他线程操作的是其他未被占用的Segment所管辖的子数组,那么是不会被阻塞的。此时呢,可以将分段锁拆分的更细,或者不使用分段锁,而是table里面的每个bucket都用一把不同的锁进行管理,ConcurrentHashMap的效率就得到了更好的提高。
    b)、jdk1.8以后,当前的ConcurrentHashMap,使用的CAS + synchronized使锁更加细化,保证并发安全。同时,也做了进一步的优化,使用了数组 + 链表 + 红黑树的组合。synchronized只锁定当前链表或者红黑树的首节点,这样,只要哈希不冲突,就不会产生并发,效率得到了进一步的提高,ConcurrentHashMap的结构参考了jdk1.8以后的hashMap来设计的。

  5)、Hashtable、HashMap、ConcurrentHashMap的区别,面试回答:

    a)、HashMap线程不安全的,底层是通过数组 + 链表 + 红黑树。键值对key-value均可以为null,但是hashtable,ConcurrentHashMap两个类都不支持。
    b)、Hashtable是线程安全的,锁住整个对象,底层是数组 + 链表。实现线程安全的方式,是在修改数组的时候锁住整个hashtable,效率很低下的。
    c)、ConcurrentHashMap是线程安全的,CAS + 同步锁,底层是数组 + 链表 + 红黑树。则是对hashtable进行了优化,通过将锁细粒度化到table的每个元素来提升并发性能。

    d)、HashMap的key、value均可以为null,而其它的两个类Hashtable、ConcurrentHashMap不支持的。

14、HashMap中的put方法的逻辑,如下所示:

  1)、如果HashMap未被初始化过,则进行初始化操作。
  2)、对Key求Hash值,然后再计算table数组的下标。
  3)、如果没有碰撞,table数组里面对应的位置还没有键值对,则将键值对直接放入对应的table数组位置(桶)中。
  4)、如果碰撞了,table数组这个位置有元素了,以链表的方式链接到后面。
  5)、如果链表长度超过阈值,就把链表转成红黑树。
  6)、如果链表长度低于6,就把红黑树转回链表。
  7)、如果节点已经存在就键位对应的旧值进行替换。所谓的节点存在也就是,即key值已经存在在了HashMap中了,我们找到这个key值就key对应的新值替换掉它对应的旧值。
  8)、如果桶满了(容量16*加载因子0.75),需要扩容了,就需要resize(扩容2倍后重排)。

  1 /** 
  2  * The default initial capacity - MUST be a power of two. 
  3  */ 
  4 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
  5  
  6 /** 
  7  * The maximum capacity, used if a higher value is implicitly specified 
  8  * by either of the constructors with arguments. 
  9  * MUST be a power of two <= 1<<30. 
 10  */ 
 11 //  
 12 static final int MAXIMUM_CAPACITY = 1 << 30; 
 13  
 14 /** 
 15  * The load factor used when none specified in constructor. 
 16  */ 
 17 // 默认的扩容因子DEFAULT_LOAD_FACTOR = 0.75f 
 18 static final float DEFAULT_LOAD_FACTOR = 0.75f; 
 19  
 20 /** 
 21  * The bin count threshold for using a tree rather than list for a 
 22  * bin.  Bins are converted to trees when adding an element to a 
 23  * bin with at least this many nodes. The value must be greater 
 24  * than 2 and should be at least 8 to mesh with assumptions in 
 25  * tree removal about conversion back to plain bins upon 
 26  * shrinkage. 
 27  */ 
 28 // 如果链表的长度超过TREEIFY_THRESHOLD = 8的时候呢,就会被改造成红黑树。 
 29 static final int TREEIFY_THRESHOLD = 8; 
 30  
 31 /** 
 32  * The bin count threshold for untreeifying a (split) bin during a 
 33  * resize operation. Should be less than TREEIFY_THRESHOLD, and at 
 34  * most 6 to mesh with shrinkage detection under removal. 
 35  */ 
 36 // 如果某个桶上面元素的总数,因为删除而低于阈值之后呢,即低于UNTREEIFY_THRESHOLD = 6的时候,红黑树又被转换成了链表以保证更高的性能。 
 37 static final int UNTREEIFY_THRESHOLD = 6; 
 38  
 39 /** 
 40  * The smallest table capacity for which bins may be treeified. 
 41  * (Otherwise the table is resized if too many nodes in a bin.) 
 42  * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts 
 43  * between resizing and treeification thresholds. 
 44  */ 
 45 //  
 46 static final int MIN_TREEIFY_CAPACITY = 64; 
 47  
 48  
 49  
 50 /** 
 51  * Constructs an empty <tt>HashMap</tt> with the default initial capacity 
 52  * (16) and the default load factor (0.75). 
 53  */ 
 54 // 无参构造函数,table的数组并没有在构造函数中进行初始化,而是仅仅给了一些成员变量赋初始值。HashMap是按照LazyLoad的原则,在首次使用的时候才会被初始化的。 
 55 public HashMap() { 
 56     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 
 57 } 
 58  
 59  
 60  
 61  
 62 ...... 
 63  
 64  
 65  
 66  
 67  
 68 /** 
 69 * Basic hash bin node, used for most entries.  (See below for 
 70 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) 
 71 */ 
 72 static class Node<K,V> implements Map.Entry<K,V> { 
 73     final int hash; // hash值 
 74     final K key; //键值key 
 75     V value; //键值value 
 76     Node<K,V> next; //指向下一个节点的next 
 77  
 78     Node(int hash, K key, V value, Node<K,V> next) { 
 79         this.hash = hash; 
 80         this.key = key; 
 81         this.value = value; 
 82         this.next = next; 
 83     } 
 84  
 85     public final K getKey()        { return key; } 
 86     public final V getValue()      { return value; } 
 87     public final String toString() { return key + "=" + value; } 
 88  
 89     public final int hashCode() { 
 90         return Objects.hashCode(key) ^ Objects.hashCode(value); 
 91     } 
 92  
 93     public final V setValue(V newValue) { 
 94         V oldValue = value; 
 95         value = newValue; 
 96         return oldValue; 
 97     } 
 98  
 99     public final boolean equals(Object o) { 
100         if (o == this) 
101             return true; 
102         if (o instanceof Map.Entry) { 
103             Map.Entry<?,?> e = (Map.Entry<?,?>)o; 
104             if (Objects.equals(key, e.getKey()) && 
105                 Objects.equals(value, e.getValue())) 
106                 return true; 
107         } 
108         return false; 
109     } 
110 } 
111  
112  
113  
114  
115  
116  
117 /** 
118  * The table, initialized on first use, and resized as 
119  * necessary. When allocated, length is always a power of two. 
120  * (We also tolerate length zero in some operations to allow 
121  * bootstrapping mechanics that are currently not needed.) 
122  */ 
123 // HashMap的内部结构,HashMap可以看作是通过数组Node<K,V>[] table,和链表组合而成的复合结构,数组被分为一个个的bucket,通过hash值决定了键值对在这个数组的寻址,hash值相同的键值对则以链表的形式来存储。 
124 transient Node<K,V>[] table; 
125  
126  
127  
128  
129 ...... 
130  
131  
132  
133  
134  
135 /** 
136  * Associates the specified value with the specified key in this map. 
137  * If the map previously contained a mapping for the key, the old 
138  * value is replaced. 
139  * 
140  * @param key key with which the specified value is to be associated 
141  * @param value value to be associated with the specified key 
142  * @return the previous value associated with <tt>key</tt>, or 
143  *         <tt>null</tt> if there was no mapping for <tt>key</tt>. 
144  *         (A <tt>null</tt> return can also indicate that the map 
145  *         previously associated <tt>null</tt> with <tt>key</tt>.) 
146  */ 
147 public V put(K key, V value) { 
148     return putVal(hash(key), key, value, false, true); 
149 } 
150  
151  
152 /** 
153  * Implements Map.put and related methods 
154  * 
155  * @param hash hash for key 
156  * @param key the key 
157  * @param value the value to put 
158  * @param onlyIfAbsent if true, don't change existing value 
159  * @param evict if false, the table is in creation mode. 
160  * @return previous value, or null if none 
161  */ 
162 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
163                boolean evict) { 
164     Node<K,V>[] tab; Node<K,V> p; int n, i; 
165     // 如果table为null的时候,或者table的长度为0的时候 
166     if ((tab = table) == null || (n = tab.length) == 0) 
167         // 调用resize()方法初始化table,resize()方法的作用是进行初始化和扩容的功能。 
168         n = (tab = resize()).length; 
169     // 做hash运算,算出键值对在table里面的具体位置。hash哈希值并不是key本身的hashCode的,而是来自于hash与或产生的结果的。 
170     if ((p = tab[i = (n - 1) & hash]) == null) 
171         // 如果通过hash运算得到的位置还没有元素存储到里面的时候,则会直接new该键值对的Node,放到该数组的位置当中tab[i]。 
172         tab[i] = newNode(hash, key, value, null); 
173     // 否则就继续向下走。 
174     else { 
175         Node<K,V> e; K k; 
176         // 如果发现同样的位置,已经存在键值对的时候,且键和传进来的键是一致的, 
177         if (p.hash == hash && 
178             ((k = p.key) == key || (key != null && key.equals(k)))) 
179             // 则直接替换数组里面的元素值 
180             e = p; 
181             // 否则,如果当前数组位置存储的是否已经是树化后的节点 
182         else if (p instanceof TreeNode) 
183             // 如果是树化了,就按照树的方式尝试存储键值对 
184             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
185         else { 
186             // 如果未树化,则按照链表的插入方式往链表后面添加元素 
187             for (int binCount = 0; ; ++binCount) { 
188                 if ((e = p.next) == null) { 
189                     p.next = newNode(hash, key, value, null); 
190                     // 判断链表元素的总数,一旦超过了TREEIFY_THRESHOLD,则将链表进行树化操作。 
191                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
192                         // 树化操作哦 
193                         treeifyBin(tab, hash); 
194                     break; 
195                 } 
196                 //  
197                 if (e.hash == hash && 
198                     ((k = e.key) == key || (key != null && key.equals(k)))) 
199                     break; 
200                 p = e; 
201             } 
202         } 
203         // 如果插入的键位存在于hashMap中的时候,则对对应的键位进行值的更新操作。 
204         if (e != null) { // existing mapping for key 
205             V oldValue = e.value; 
206             if (!onlyIfAbsent || oldValue == null) 
207                 e.value = value; 
208             afterNodeAccess(e); 
209             return oldValue; 
210         } 
211     } 
212     ++modCount; 
213     // 当hashMap里面的szie大于阈值的时候呢,就对HashMap进行扩容 
214     if (++size > threshold) 
215         resize(); 
216     afterNodeInsertion(evict); 
217     return null; 
218 }

15、HashMap中的get方法的逻辑,如下所示: 

 1 /** 
 2  * Returns the value to which the specified key is mapped, 
 3  * or {@code null} if this map contains no mapping for the key. 
 4  * 
 5  * <p>More formally, if this map contains a mapping from a key 
 6  * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 
 7  * key.equals(k))}, then this method returns {@code v}; otherwise 
 8  * it returns {@code null}.  (There can be at most one such mapping.) 
 9  * 
10  * <p>A return value of {@code null} does not <i>necessarily</i> 
11  * indicate that the map contains no mapping for the key; it's also 
12  * possible that the map explicitly maps the key to {@code null}. 
13  * The {@link #containsKey containsKey} operation may be used to 
14  * distinguish these two cases. 
15  * 
16  * @see #put(Object, Object) 
17  */ 
18 public V get(Object key) { 
19     Node<K,V> e; 
20     // 通过传入的key值进行调用getNode()方法 
21     return (e = getNode(hash(key), key)) == null ? null : e.value; 
22 } 
23  
24  
25  
26  
27 ...... 
28  
29  
30  
31  
32  
33 /** 
34  * Implements Map.get and related methods 
35  * 
36  * @param hash hash for key 
37  * @param key the key 
38  * @return the node, or null if none 
39  */ 
40 final Node<K,V> getNode(int hash, Object key) { 
41     Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 
42     // 键对象的hashcode,通过哈希算法,找到bucket的位置 
43     if ((tab = table) != null && (n = tab.length) > 0 && 
44         (first = tab[(n - 1) & hash]) != null) { 
45         // 找到Bucket的位置以后,调用key.equals(k))方法找到链表中正确的节点,最终找到要找的值 
46         if (first.hash == hash && // always check first node 
47             ((k = first.key) == key || (key != null && key.equals(k)))) 
48             return first; 
49         if ((e = first.next) != null) { 
50             if (first instanceof TreeNode) 
51                 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 
52             do { 
53                 if (e.hash == hash && 
54                     ((k = e.key) == key || (key != null && key.equals(k)))) 
55                     return e; 
56             } while ((e = e.next) != null); 
57         } 
58     } 
59     return null; 
60 }

16、HashMap,如何有效减少碰撞?

  答:树化这种被动的方式可以提升性能,哈希运算也是可以提升性能的关键。

    1)、扰动函数,促使元素位置分布均匀,减少碰撞的机率。原理就是如果两个不相等的对象返回不同的hashcode的话,或者说元素位置尽量的分布均匀些,那么碰撞的机率就会小些,意味着有些元素就可以通过数组来直接去获取了,这样可以提升hashMap的性能的。哈希算法的内部实现,是让不同对象返回不同的hashcode值。
    2)、其次,如果使用final对象,并采用合适的equals()和hashCode()方法,将会减少碰撞的发生。不可变性使得能够缓存不同键的hashcode,这将提供获取对象的速度,而使用String,Integer,这种是非常好的选择,因为他们是final,并且重写了hashcode方法和equals方法的。不可变性final是必要的,因为为了要计算hashcode,就要防止键值改变,如果键值在放入的时候和获取的时候返回不同的hashcode的话呢,就不能从hashMap中找到想要的对象了。

 1 /** 
 2  * Computes key.hashCode() and spreads (XORs) higher bits of hash 
 3  * to lower.  Because the table uses power-of-two masking, sets of 
 4  * hashes that vary only in bits above the current mask will 
 5  * always collide. (Among known examples are sets of Float keys 
 6  * holding consecutive whole numbers in small tables.)  So we 
 7  * apply a transform that spreads the impact of higher bits 
 8  * downward. There is a tradeoff between speed, utility, and 
 9  * quality of bit-spreading. Because many common sets of hashes 
10  * are already reasonably distributed (so don't benefit from 
11  * spreading), and because we use trees to handle large sets of 
12  * collisions in bins, we just XOR some shifted bits in the 
13  * cheapest possible way to reduce systematic lossage, as well as 
14  * to incorporate impact of the highest bits that would otherwise 
15  * never be used in index calculations because of table bounds. 
16  */ 
17 static final int hash(Object key) { 
18     int h; 
19     // 即先获取key.hashCode(),hashCode方法返回值是int类型的,是32位的,然后再将高位数移位到低位,移动16位,最后进行异或运算。 
20     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
21 }

16.1、HashMap,从获取hash到散列的过程。

  1)、不使用hashcode()方法获取的值,是因为key.hashCode();方法返回的是int类型的散列值,如果直接使用这个散列值作为下标去访问hashMap数组的话呢,考虑到二进制的32位带符号的int值的范围呢-2147483648——2147483647,前后区间大概有40亿的映射空间,只要哈希函数映射的均匀松散,一般应用是很难出现碰撞的,但是40亿长度的数组在内存中是放不下的,况且,HashMap在扩容之前数组默认大小才是16,所以直接拿这个散列值使用不现实的。
  2)、h >>> 16,右移16位,再和自己做异或操作。这样做,就是为了混合原始哈希码的高位与低位,依次来加大低位的随机性,而且混合后的低位参杂了高位部分的特征,这样高位的信息也变相的保存了下来,这样做主要从速度,质量,功效进行考虑的,可以在数组table的length在比较小的时候,也能保证考虑到高低bit都参与到哈希的运算中,同时也不会有太大的开销。

17、hashMap含参的构造器,可以传入初始化的hashMap的初始化大小的,根据传入的初始化值,换算成2的n次方,转换成最接近的2的倍数的值,这样做,就是为了通过哈希运算定位桶的时候呢,能实现用与操作来代替取模进而获得更好的效果。

 1 /** 
 2  * Constructs an empty <tt>HashMap</tt> with the specified initial 
 3  * capacity and the default load factor (0.75). 
 4  * 
 5  * @param  initialCapacity the initial capacity. 
 6  * @throws IllegalArgumentException if the initial capacity is negative. 
 7  */ 
 8 // hashMap含参的构造器,可以传入初始化的hashMap的初始化大小的 
 9 public HashMap(int initialCapacity) { 
10     this(initialCapacity, DEFAULT_LOAD_FACTOR); 
11 } 
12  
13  
14  
15 /** 
16  * Constructs an empty <tt>HashMap</tt> with the specified initial 
17  * capacity and load factor. 
18  * 
19  * @param  initialCapacity the initial capacity 
20  * @param  loadFactor      the load factor 
21  * @throws IllegalArgumentException if the initial capacity is negative 
22  *         or the load factor is nonpositive 
23  */ 
24 // hashMap含参的构造器,调用该构造器。 
25 public HashMap(int initialCapacity, float loadFactor) { 
26     if (initialCapacity < 0) 
27         throw new IllegalArgumentException("Illegal initial capacity: " + 
28                                            initialCapacity); 
29     if (initialCapacity > MAXIMUM_CAPACITY) 
30         initialCapacity = MAXIMUM_CAPACITY; 
31     if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
32         throw new IllegalArgumentException("Illegal load factor: " + 
33                                            loadFactor); 
34     this.loadFactor = loadFactor; 
35     // 根据传入的hashMap的初始化值,并不是传入的初始化值多大,就是多大的 
36     this.threshold = tableSizeFor(initialCapacity); 
37 } 
38  
39  
40  
41  
42 ....... 
43  
44  
45  
46  
47 /** 
48  * Returns a power of two size for the given target capacity. 
49  */ 
50 // 根据传入的初始化值,换算成2的n次方,转换成最接近的2的倍数的值,这样做,就是为了通过哈希运算定位桶的时候呢,能实现用与操作来代替取模进而获得更好的效果。 
51 static final int tableSizeFor(int cap) { 
52     int n = cap - 1; 
53     n |= n >>> 1; 
54     n |= n >>> 2; 
55     n |= n >>> 4; 
56     n |= n >>> 8; 
57     n |= n >>> 16; 
58     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
59 }

18 、hashMap的扩容resize?

  1)、hashMap的扩容,就是重新计算容量,向hashMap对象中不停的添加元素,而hashMap对象内部的数组无法装载更多的元素的时候,对象就需要扩大数组的长度了,才能装入更多的元素。java中的数组是无法进行自动扩容的,hashMap的扩容,是使用新的大的数组替换小的数组。

  2)、hashMap的默认负载因子是0.75f,当hashMap填满了75%的bucket的时候呢,就会创建原来hashMap大小2倍的bucket数组,来重新调整map的大小,并将原来的对象放入的新的bucket数组中。

  3)、HashMap扩容的问题,多线程环境下,调整大小会存在条件竞争,容易造成死锁。rehashing是一个比较耗时的过程,由于需要将原先的hashMap中的键值对重新移动的新的hashMap中去,是一个比较耗时的过程。

  1 /** 
  2  * The load factor used when none specified in constructor. 
  3  */ 
  4 // 默认的负载因子 
  5 static final float DEFAULT_LOAD_FACTOR = 0.75f; 
  6  
  7  
  8  
  9  
 10 ...... 
 11  
 12  
 13  
 14  
 15  
 16 /** 
 17  * Initializes or doubles table size.  If null, allocates in 
 18  * accord with initial capacity target held in field threshold. 
 19  * Otherwise, because we are using power-of-two expansion, the 
 20  * elements from each bin must either stay at same index, or move 
 21  * with a power of two offset in the new table. 
 22  * 
 23  * @return the table 
 24  */ 
 25 // hashMap的扩容resize,就是重新计算容量,向hashMap对象中不停的添加元素,而hashMap对象内部的数组无法装载更多的元素的时候,对象就需要扩大数组的长度了,才能装入更多的元素。java中的数组是无法进行自动扩容的,hashMap的扩容,是使用新的大的数组替换小的数组。 
 26  
 27 // hashMap的默认负载因子是0.75f,当hashMap填满了75%的bucket的时候呢,就会创建原来hashMap大小2倍的bucket数组,来重新调整map的大小,并将原来的对象放入的新的bucket数组中。 
 28 final Node<K,V>[] resize() { 
 29     Node<K,V>[] oldTab = table; 
 30     int oldCap = (oldTab == null) ? 0 : oldTab.length; 
 31     int oldThr = threshold; 
 32     int newCap, newThr = 0; 
 33     if (oldCap > 0) { 
 34         if (oldCap >= MAXIMUM_CAPACITY) { 
 35             threshold = Integer.MAX_VALUE; 
 36             return oldTab; 
 37         } 
 38         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
 39                  oldCap >= DEFAULT_INITIAL_CAPACITY) 
 40             newThr = oldThr << 1; // double threshold 
 41     } 
 42     else if (oldThr > 0) // initial capacity was placed in threshold 
 43         newCap = oldThr; 
 44     else {               // zero initial threshold signifies using defaults 
 45         newCap = DEFAULT_INITIAL_CAPACITY; 
 46         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 
 47     } 
 48     if (newThr == 0) { 
 49         float ft = (float)newCap * loadFactor; 
 50         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 
 51                   (int)ft : Integer.MAX_VALUE); 
 52     } 
 53     threshold = newThr; 
 54     @SuppressWarnings({"rawtypes","unchecked"}) 
 55         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 
 56     table = newTab; 
 57     if (oldTab != null) { 
 58         for (int j = 0; j < oldCap; ++j) { 
 59             Node<K,V> e; 
 60             if ((e = oldTab[j]) != null) { 
 61                 oldTab[j] = null; 
 62                 if (e.next == null) 
 63                     newTab[e.hash & (newCap - 1)] = e; 
 64                 else if (e instanceof TreeNode) 
 65                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
 66                 else { // preserve order 
 67                     Node<K,V> loHead = null, loTail = null; 
 68                     Node<K,V> hiHead = null, hiTail = null; 
 69                     Node<K,V> next; 
 70                     do { 
 71                         next = e.next; 
 72                         if ((e.hash & oldCap) == 0) { 
 73                             if (loTail == null) 
 74                                 loHead = e; 
 75                             else 
 76                                 loTail.next = e; 
 77                             loTail = e; 
 78                         } 
 79                         else { 
 80                             if (hiTail == null) 
 81                                 hiHead = e; 
 82                             else 
 83                                 hiTail.next = e; 
 84                             hiTail = e; 
 85                         } 
 86                     } while ((e = next) != null); 
 87                     if (loTail != null) { 
 88                         loTail.next = null; 
 89                         newTab[j] = loHead; 
 90                     } 
 91                     if (hiTail != null) { 
 92                         hiTail.next = null; 
 93                         newTab[j + oldCap] = hiHead; 
 94                     } 
 95                 } 
 96             } 
 97         } 
 98     } 
 99     return newTab; 
100 }

19、 ConcurrentHashMap是出自于JUC包的,ConcurrentHashMap有很多地方和hashMap类似的,包含属性参数之类的。ConcurrentHashMap使用的CAS + synchronized进行高效的同步更新数据的。

ConcurrentHashMap总结,jdk1.8的实现,也是锁分离的思想,比起Segment,锁拆的更细,只要哈希不冲突,就不会出现并发或者锁的情况。

  1)、首先使用无锁操作CAS插入头节点,失败则循环重试,如果插入失败,则说明有别的线程插入头节点了,需要再次循环进行操作。
  2)、若头节点已经存在,则通过synchronized尝试获取头节点的同步锁,再进行操作。性能比Segment分段锁又提高了很多。
 

20、ConcurrentHashMap的put方法的逻辑。

  1)、判断Node[]数组是否初始化,没有则进行初始化操作。
  2)、通过hash定位数组的索引坐标,是否有Node节点,如果没有则使用CAS进行添加(链表的头节点),添加失败则进入下次循环,继续尝试添加。
  3)、检查到内部正在扩容,如果正在扩容,就调用helpTransfer方法,就帮助它一块扩容。
  4)、如果f!=null,头节点不为空,则使用synchronized锁住f元素(链表/红黑二叉树的头元素)。如果是Node链表结构,则执行链表的添加操作。如果是TreeNode(树形结构)则执行树添加操作。
  5)、判断链表长度已经到达临界值8,当然这个8是默认值,大家可以去做调整,当节点数超过这个值就需要把链表转换成树结构了。

  1 private static final int MAXIMUM_CAPACITY = 1 << 30; 
  2  
  3 /** 
  4  * The default initial table capacity.  Must be a power of 2 
  5  * (i.e., at least 1) and at most MAXIMUM_CAPACITY. 
  6  */ 
  7 private static final int DEFAULT_CAPACITY = 16; 
  8  
  9 /** 
 10  * The largest possible (non-power of two) array size. 
 11  * Needed by toArray and related methods. 
 12  */ 
 13 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 
 14  
 15 /** 
 16  * The default concurrency level for this table. Unused but 
 17  * defined for compatibility with previous versions of this class. 
 18  */ 
 19 private static final int DEFAULT_CONCURRENCY_LEVEL = 16; 
 20  
 21 /** 
 22  * The load factor for this table. Overrides of this value in 
 23  * constructors affect only the initial table capacity.  The 
 24  * actual floating point value isn't normally used -- it is 
 25  * simpler to use expressions such as {@code n - (n >>> 2)} for 
 26  * the associated resizing threshold. 
 27  */ 
 28 private static final float LOAD_FACTOR = 0.75f; 
 29  
 30 /** 
 31  * The bin count threshold for using a tree rather than list for a 
 32  * bin.  Bins are converted to trees when adding an element to a 
 33  * bin with at least this many nodes. The value must be greater 
 34  * than 2, and should be at least 8 to mesh with assumptions in 
 35  * tree removal about conversion back to plain bins upon 
 36  * shrinkage. 
 37  */ 
 38 static final int TREEIFY_THRESHOLD = 8; 
 39  
 40 /** 
 41  * The bin count threshold for untreeifying a (split) bin during a 
 42  * resize operation. Should be less than TREEIFY_THRESHOLD, and at 
 43  * most 6 to mesh with shrinkage detection under removal. 
 44  */ 
 45 static final int UNTREEIFY_THRESHOLD = 6; 
 46  
 47 /** 
 48  * The smallest table capacity for which bins may be treeified. 
 49  * (Otherwise the table is resized if too many nodes in a bin.) 
 50  * The value should be at least 4 * TREEIFY_THRESHOLD to avoid 
 51  * conflicts between resizing and treeification thresholds. 
 52  */ 
 53 static final int MIN_TREEIFY_CAPACITY = 64; 
 54  
 55 /** 
 56  * Minimum number of rebinnings per transfer step. Ranges are 
 57  * subdivided to allow multiple resizer threads.  This value 
 58  * serves as a lower bound to avoid resizers encountering 
 59  * excessive memory contention.  The value should be at least 
 60  * DEFAULT_CAPACITY. 
 61  */ 
 62 private static final int MIN_TRANSFER_STRIDE = 16; 
 63  
 64 /** 
 65  * The number of bits used for generation stamp in sizeCtl. 
 66  * Must be at least 6 for 32bit arrays. 
 67  */ 
 68 private static int RESIZE_STAMP_BITS = 16; 
 69  
 70 /** 
 71  * The maximum number of threads that can help resize. 
 72  * Must fit in 32 - RESIZE_STAMP_BITS bits. 
 73  */ 
 74 private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; 
 75  
 76 /** 
 77  * The bit shift for recording size stamp in sizeCtl. 
 78  */ 
 79 private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; 
 80  
 81  
 82  
 83  
 84  
 85  
 86 ...... 
 87  
 88  
 89  
 90  
 91 /* 
 92  * Encodings for Node hash fields. See above for explanation. 
 93  */ 
 94 // 其它成员变量主要用来控制线程之间的并发操作,比如可以同时可以进行扩容的线程数等等。  
 95 static final int MOVED     = -1; // hash for forwarding nodes 
 96 static final int TREEBIN   = -2; // hash for roots of trees 
 97 static final int RESERVED  = -3; // hash for transient reservations 
 98 static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash 
 99  
100  
101  
102 ....... 
103  
104  
105  
106  
107  /** 
108  * Table initialization and resizing control.  When negative, the 
109  * table is being initialized or resized: -1 for initialization, 
110  * else -(1 + the number of active resizing threads).  Otherwise, 
111  * when table is null, holds the initial table size to use upon 
112  * creation, or 0 for default. After initialization, holds the 
113  * next element count value upon which to resize the table. 
114  */ 
115 // sizeCtl是size control,是做大小控制的标识符,是哈希表初始化和扩容时候的一个控制位标识量,负数代表正在进行初始化或者扩容操作,-1代表正在初始化,-n代表有n-1个线程正在扩容操作,正数或者0代表哈希表还没有被初始化操作。这个数值表示初始化或者下一次进行扩容的大小,因为有了volatile修饰符, sizeCtl是多线程之间可见的,对它的改动,其他线程可以立即看得到,确实可以起到控制的作用的。 
116 private transient volatile int sizeCtl; 
117  
118  
119  
120  
121  
122 ....... 
123  
124  
125  
126  
127  
128  
129 /** 
130  * Maps the specified key to the specified value in this table. 
131  * Neither the key nor the value can be null. 
132  * 
133  * <p>The value can be retrieved by calling the {@code get} method 
134  * with a key that is equal to the original key. 
135  * 
136  * @param key key with which the specified value is to be associated 
137  * @param value value to be associated with the specified key 
138  * @return the previous value associated with {@code key}, or 
139  *         {@code null} if there was no mapping for {@code key} 
140  * @throws NullPointerException if the specified key or value is null 
141  */ 
142 //  ConcurrentHashMap的put方法。 
143 public V put(K key, V value) { 
144     return putVal(key, value, false); 
145 } 
146  
147 /** Implementation for put and putIfAbsent */ 
148 final V putVal(K key, V value, boolean onlyIfAbsent) { 
149     // ConcurrentHashMap不允许插入null的键值对,即key不能为null或者value不能为null  
150     if (key == null || value == null) throw new NullPointerException(); 
151     // 计算key的哈希值 
152     int hash = spread(key.hashCode()); 
153     int binCount = 0; 
154     // for循环,因为我们对数组元素的更新是使用CAS的机制进行更新的,需要不断的做失败重试,直到成功为止,因此这里使用了for循环。 
155     for (Node<K,V>[] tab = table;;) { 
156         Node<K,V> f; int n, i, fh; 
157         // 先判断数组是否为空,如果为空或者length等于0 
158         if (tab == null || (n = tab.length) == 0) 
159             // 就进行初始化操作 
160             tab = initTable(); 
161         // 如果不为空,且不等于0,就使用哈希值来找到f,f表示的是链表或者红黑二叉树的头节点,即我们数组里面的元素,根据哈希值定位到的元素来检查元素是否存在 
162         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
163             // 如果不存在,尝试使用CAS进行添加,如果添加失败,则break掉,进入下一次循环 
164             if (casTabAt(tab, i, null, 
165                          new Node<K,V>(hash, key, value, null))) 
166                 break;                   // no lock when adding to empty bin 
167         } 
168         // 如果我们发现原先的元素已经存在了,此时,由于我们的ConcurrentHashMap是随时存在于多线程环境下的,有可能别的线程正在移动它,也就是说,ConcurrentHashMap的内部呢,正在移动元素,那么我们就协助其扩容。 
169         else if ((fh = f.hash) == MOVED) 
170             tab = helpTransfer(tab, f); 
171         else { 
172             // 这里表示发生了哈希碰撞 
173             V oldVal = null; 
174             // 此时,锁住链表或者红黑二叉树的头节点,即我们的数组元素 
175             synchronized (f) { 
176                 // 判断,f是否的链表的头节点 
177                 if (tabAt(tab, i) == f) { 
178                     // fh代表的是头节点的哈希值 
179                     if (fh >= 0) { 
180                         // 如果是链表的头节点,就初始化链表的计数器 
181                         binCount = 1; 
182                         // 遍历该链表,每遍历一次,就将计数器加一 
183                         for (Node<K,V> e = f;; ++binCount) { 
184                             K ek; 
185                             // 此时,发现,如果节点存在呢,就去更新对应的value值 
186                             if (e.hash == hash && 
187                                 ((ek = e.key) == key || 
188                                  (ek != null && key.equals(ek)))) { 
189                                 oldVal = e.val; 
190                                 if (!onlyIfAbsent) 
191                                     e.val = value; 
192                                 break; 
193                             } 
194                             Node<K,V> pred = e; 
195                             // 如果不存在,就在链表尾部,添加新的节点 
196                             if ((e = e.next) == null) { 
197                                 pred.next = new Node<K,V>(hash, key, 
198                                                           value, null); 
199                                 break; 
200                             } 
201                         } 
202                     } 
203                     // 如果头节点是红黑二叉树的节点 
204                     else if (f instanceof TreeBin) { 
205                         Node<K,V> p; 
206                         binCount = 2; 
207                         // 则尝试调用红黑二叉树的操作逻辑,去尝试往树里面添加节点 
208                         if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, 
209                                                        value)) != null) { 
210                             oldVal = p.val; 
211                             if (!onlyIfAbsent) 
212                                 p.val = value; 
213                         } 
214                     } 
215                 } 
216             } 
217             // 如果链表长度已经已经达到了临界值8 
218             if (binCount != 0) { 
219                 if (binCount >= TREEIFY_THRESHOLD) 
220                     // 那么,就将链表转化为树结构 
221                     treeifyBin(tab, i); 
222                 if (oldVal != null) 
223                     return oldVal; 
224                 break; 
225             } 
226         } 
227     } 
228     // 在添加完节点之后呢,就将当前的ConcurrentHashMap的size数量呢,加上1。 
229     addCount(1L, binCount); 
230     return null; 
231 }

21、java.util.concurrent,提供了并发编程的解决方案,java.util.concurrent简称为JUC,JUC包里面有两大核心。

答:1)、CAS是java.util.concurrent.atomic包的基础。
  2)、AQS是java.util.concurrent.locks包以及一些常用类比如Semophore,ReentrantLock等类的基础。

22、java.util.concurrent简称为JUC,JUC包的分类。

答:1)、线程执行器executor,就是任务的执行和调度的框架,此外,在tools包可以看到和executor相关的Executors类,用来创建ExecutorService、ScheduledExecutorService、ThreadFactory、Callable对象等等。
  2)、锁locks。在jdk1.5之前协调共享对象的访问时,可以使用的机制只有synchronized和volatile,jdk1.5之后便出现了锁locks,locks里面引入了显式锁,方便线程间的共享资源做更细粒度的锁控制,Condition对象是由locks锁对象创建的,一个Lock对象可创建多个Condition对象,主要用于将线程的等待和唤醒,即将wait、notify、notifyAll方法对象化。不管是Condition对象、还是Lock对象都是基于AQS来实现的,而AQS得底层是通过调用LockSupport.unpark和LockSupport.park去实现线程的阻塞和唤醒的。ReentrantReadWriteLock是可重入读写锁,没有线程进行写操作的时候,多个线程可同时进行读操作,当有线程进行写操作的时候,其它读写操作只能等待,即读读共存,但是读写不能共存,写写也不能共存,在读多于写的情况下,可重入读写锁能够提供比排它锁ReentrantLock更好的并发性和吞吐量。
  3)、原子变量类atomic,中文是原子,指的是一个操作不可中断的,在多个线程一起执行的时候,一个操作一旦开始就不会被其它线程所干扰,所以原子类就是具有原子操作特征的类,atomic包方便程序员在多线程环境下无锁的进行原子操作。atomic包中一共有12个类,四种原子更新方式,分别是原子更新基本类型,原子更新数组,原子更新引用,原子更新字段。atomic使用的CAS的更新方式,当某个线程在执行atomic方法的时候不会被其它线程打断,而别的线程j就像自旋锁一样,一直等到该方法执行完成才有JVM从等待队列中选择一个线程来执行,在软件层面上是非阻塞的,是在底层硬件上借助处理器的原子指令来保证的。在面对多线程的累加操作可以适当运用atomic包里面的类来解决。
  4)、并发工具类tools。
  5)、并发集合collections。

23、java.util.concurrent简称为JUC,JUC包的并发工具类。

答:四个同步器,同步器的作用主要是用于协助线程的同步。

1)、闭锁CountDownLatch。让主线程等待一组事件发生后继续执行,这里面的事件指的是CountDownLatch里的countDown()方法。

  值的注意的是其它线程调用完countDown()方法之后还是会继续执行的,也就是说,countDown()方法调用之后并不代表该子线程已经执行完毕,而是告诉主线程说你可以继续执行,至少我这边不托你后腿了,具体还需要看其它线程给不给力了,如图,引入了CountDownLatch之后了,主线程就进入了等待状态,此时CountDownLatch里面有一个cnt变量开始的时候初始化为一个整数,这里就是事件的个数,我们的变量初始化为3,m每当其中一个子线程调用countDown()方法之后,这个计数器便会减一,直到所有的子线程都调用了countDown()方法,cnt变为零之后,主线程才得以重新恢复到执行的状态。

2)、栅栏CyclicBarrier,阻塞当前线程,等待其它线程。

a)、等待其它线程,且会阻塞自己当前线程,所有线程必须同时到达栅栏位置后,才能继续执行。
b)、所有线程到达栅栏处,可以触发执行另外一个预先设置的线程。

  CyclicBarrier和CountDownLatch一样,内部也有一个计数器,如图中的cnt,T1,T2,T3没调用一次await()方法,计数器就会减一,且在它们调用await方法的时候,如果计数器不为零,这些线程也会被阻塞,另外TA线程j即当前线程会在所有线程到达栅栏处即计数器为0的时候才会跟着T1,T2,T3一起去执行,同样都是阻塞当前线程来等待其它线程,计数的时候CountDownLatch的其它子线程是可以继续执行的,而CyclicBarrier的所有线程会被阻塞直到计数器变为零,这是两者作用上的区别。

3)、信号量Semaphore,控制某个资源可被同时访问的线程个数。

  通过acquire()方法获取一个许可,如果没有就去等待,而一旦利用资源执行完业务逻辑之后,线程就会调用release方法去释放出一个许可出来。

4)、交换器Exchanger,两个线程到达同步点后,相互交换数据。

  Exchanger提供一个同步点,在这个同步点,两个线程k可以交换彼此的数据,Exchanger会产生一个同步点,一个线程先执行到达同步点,就会被阻塞,直到另外一个线程也进入到同步点为止,当两个都到达了同步点之后就开始交换数据,线程中调用Exchanger.Exchange()的地方就是同步点了,Exchanger只能用于连个线程互相    交换数据。

24、BlockingQueue,阻塞队列,提供了可阻塞的入队和出队操作。

答:Collections里面除了ConcurrentHashMap之外,还有BlockingQueue。

  1)、如果队列满了,入队操作将阻塞,直到有空间可用,如果队列空了,出队操作将阻塞,直到有元素可用。根据出入队的规则和底层数据结构的实现,可以划分出多个BlockingQueue的实现子类。

  2)、主要用于生产者-消费者模式,在多线程场景的时候生产者线程在队列尾部添加元素,而消费者线程在队列头部消费元素,通过这种方式能够达到将任务的生产和消费进行隔离的目的。

25、BlockingQueue主要有以下的七个队列实现,它们都是线程安全的。

  1)、ArrayBlockingQueue,一个由数据结构组成的有界阻塞队列,有边界的意思容量是有限的,我们必须在其初始化的时候指定它的容量大小,容量大小一旦指定就不可改变了,以先进先出的方式来存储数据的,最新插入的对象是在尾部,最先移除的对象是在头部。
  2)、LinkedBlockingQueue,一个由链表结构组成的有界或者无界阻塞队列,阻塞队列大小配置是可选的,如果初始化的时候指定大小,那么它就是有边界的,如果不指定大小,它就是无边界的,说是无边界,其实是采用了默认大小的容量,内部实现是一个链表,和ArrayBlockingQueue一样是采用先进先出的方式存储数据。
  3)、PriorityBlockingQueue,一个支持优先级排序的无界阻塞队列,不是先进先出的队列,元素按照优先级顺序被移除的,该队列没有上限,但是如果队列为空,那么取元素的操作take就会被阻塞,所以它的检索操作task是受阻的,另外该队列的元素是要具备可比性的,这样才可以按照优先级来进行操作。
  4)、DealyQueue,一个使用优先级队列实现的无界阻塞队列,支持延迟获取元素的无边界阻塞队列,队列中的元素必须实现Delay接口,在创建元素的时候,可以指定多久才能从队列中获取当前元素,只有在延迟期满的时候,才能从队列中获取元素。
  5)、SynchronousQueue,一个不存储元素的阻塞队列,队列内部仅允许容纳一个元素,当一个线程插入一个元素后,会被阻塞,直到这个元素被另外一个线程给消费掉。
  6)、LinkedTransferQueue,一个由链表结构组成的无界阻塞队列,是SynchronousQueue和LinkedBlockingQueue合体,性能比LinkedBlockingQueue更高,因为它是无锁操作,比SynchronousQueue存储更多的元素。
  7)、LinkedBlockingDeque,一个由链表结构组成的双向阻塞队列,是一个双端队列。

26、Java中 BIO、NIO、AIO的主要区别。

答:1)、BIO是Block-IO,是传统的java.io以及部分java.net包下的接口或者类,java.net里面比如socket、server socket、http,UrlConnection,因为网络通信同样是IO行为,因此都可以说是输入BIO的范畴。

  a)、传统IO基于字节流和字符流j进行操作,提供了InputStream和OutputStream,Reader和Writer。4
  b)、BIO是基于流模型实现的,这意味着其交互方式是同步阻塞的方式,在读取输入流或写入输出流的时候,在读写操作完成之前,线程会一直阻塞在哪里,它们之间的调用是可靠的线性顺序,程序发送请求给内核,然后有内核去进行通信,在内核准备好数据之前,这个线程是被挂起的,所以在两个阶段程序都处于挂起状态,类比成Client/Server模式呢,则其实现模式为一个连接,一个线程即客户端要连接请求的时候服务端就需要启动一个线程进行处理,待操作系统返回结果,如果这个连接不做任何事情,会造成不必要的线程开销,当然可以通过线程池机制来改善。
  c)、BIO的特点就是在IO执行的两个阶段都被阻塞住了,好处就是代码比较简单,直观。缺点就是IO效率和扩展性存在瓶颈。

2)、NIO是NonBlock-IO即非阻塞IO,在jdk1.4以后引入了NIO框架,提供了channel、selector、buffer等新的抽象,构建多路复用的,同步非阻塞的IO操作,同时提供了更接近操作系统底层高性能数据操作方式。

  a)、NIO与BIO明显区别就是,在发起第一次请求之后,线程并没有被阻塞,它是反复去检查数据是否已经准备好,把原来大块不能用的阻塞的时间分成了许多小阻塞,检查的是会有一些些阻塞,线程不断有机会去被执行,检查这个数据有没有准备好,有点类似于轮询,类比成client/server模式呢,其实现模式为一个请求一个线程,即客户端发送的连接请求都会注册到多路复用器上,多路复用器轮循到有IO请求时,才启动一个线程进行处理。NIO的特点就是程序不断去主动询问内核是否已经准备好,第一个阶段是非阻塞的,第二个阶段是阻塞的。

27、NIO的核心部分组成,Channels、Buffers、Selectors。

  基本上所有的IO在NIO中都是从一个Channel开始,Channel有点像流,数据可以从Channel读到Buffer中,也可以从Buffer中写到Channel中。

29、NIO-Channels的类型,涵盖了TCP和UDP网络IO以及文件IO。

  1)、FileChannel,拥有transferTo方法和transferFron方法。transferTo方法把FileChannel中的数据拷贝到另外一个Channel。transferFron方法把另外一个Channel中的数据拷贝到FileChannel中。该接口常被用于高效的网络文件的数据传输和大文件拷贝,在操作系统支持的情况下,通过该方法传输数据,并不需要将源数据从内核态拷贝到用户态,再从用户态拷贝到目标通道的内核态。同时也避免了两次用户态和内核态间的上下文切换,即零拷贝,效率较高,其性能高于BIO中提供的方法。
  2)、DatagramChannel。
  3)、SocketChannel。
  4)、ServerSocketChannel。

30、NIO-Buffers的类型,这些Buffer覆盖了我们能通过IO发送的基本数据类型。

  1)、ByteBuffer。
  2)、CharBuffer。
  3)、DoubleBuffer。
  4)、FloatBuffer。
  5)、IntBuffer。
  6)、LongBuffer。
  7)、ShortBuffer。
  8)、MappedByteBuffer,主要用于表示内存映射文件。

31、NIO-Selector。

  Selector允许单线程处理多个Channel,如果你的应用打开了多个连接即通道,但每个连接的流量都比较低,使用Selector就会很方便了,例如开发一个聊天服务器就排上用场了。如图所示的是使用一个Selector处理三个Channel的时候,使用Selector得向Selector注册Channel,然后调用它的select方法,这个方法会一直阻塞,直到某个注册的通道有事件就绪,一旦这个方法返回呢,线程就可以处理这些事件了,事件可以是,比如说是有新的连接进来,或者说Buffer已经有内容可以读取到了等等。

32、NIO的底层使用了操作系统底层的IO多路复用,调用系统级别的select、poll、epoll等不同方式,优点在于单线程可以同时处理多个网络IO,IO多路复用调用系统级别的select、poll、epoll模型,由系统监控IO状态,select轮询可以监控许多的IO请求,当有一个socket的数据被准备好的时候就可以返回了。

  1)、支持一个进程所能打开的最大连接数。
    a)、select,单个进程所能打开的最大连接数由FD_SETSIZE宏定义,其大小是32个整数的大小(在32位的机器上,大小是32*32,64的机器上FD_SETSIZE为32*64),我们可以对其进行修改,然后重新编译内核,但是性能无法保证,需要做进一步测试。
    b)、poll,本质上与select没有区别,但是它没有最大连接数的限制,原因是它是基于链表来存储的。
    c)、epoll,虽然连接数有上限,但是很大,1G内存的机器上可以打开10万左右的连接。
  2)、FD剧增后带来的IO效率问题。
    a)、select,因为每次调用时候都会对连接进行线性遍历,所以随着FD的增加会造成遍历速度的线性下降的性能问题。
    b)、poll,同上。
    c)、epoll,由于epoll是根据每个fd上的callback函数来实现的,只有活跃的socket才会主动调用callback,所以在活跃socket较少的情况下,使用epoll不会有线性线性下降的性能问题,但是所有的socket都很活跃的情况下,可能会有性能问题。
  3)、消息传递方式。
    a)、select,内核需要将消息传递到用户空间,需要内核的拷贝动作。
    b)、poll,同上。
  c)、epoll,通过内核的用户空间共享一块内存来实现,性能较高。

33、AIO,Asynchronous IO,基于事件和回调机制,异步非阻塞的方式,可以理解为应用操作直接返回,而不会阻塞在哪里,当后台处理完成,操作系统就会通知相应线程进行后续工作。

AIO属于异步模型,用户线程可以同时处理别的事情,AIO如何进一步加功处理结果。Java提供了两种方法。

  1)、基于回调,实现CompletionHandler接口,调用的时候触发回调函数,在调用的时候,把回调函数传递给对应的API即可。
  2)、返回Future,通过isDone查看是否准备好,通过get方法等待返回数据。

34、BIO、NIO、AIO对比。

属性\模型 阻塞BIO 非阻塞NIO 异步AIO
blocking 阻塞并同步。 非阻塞但同步 非阻塞并异步
线程数(server:client) 1:1 1:N 0:N
复杂度 简单 较复杂 复杂
吞吐量

发布评论
IT序号网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Java底层知识JVM、GC知识解答
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。