1、Java异常以及常用工具类体系。异常处理机制主要回答了三个问题? 答:1)、第一个是异常类型回答了什么被抛出。 2)、第二个是异常堆栈跟踪回答了在哪里抛出。 3)、第三个是异常信息回答了为什么被抛出。Throwable是所有异常体系的顶级父类,包含了Error类和Exception类。从概念角度分析Java的异常处理机制。 2、Java的异常体系,Error和Exception的区别? 答:1)、Error,程序无法处理的系统错误,编译器不做检查。表示系统致命的错误,程序无法处理这些错误,Error类一般是指与JVM相关的问题,如果系统奔溃、虚拟机错误、内存空间不足、方法调用栈溢出等等错误。 3、Exception主要包含两类,一类是RuntimeException、另一类是非RuntimeException。 答:1)、RuntimeException(运行时异常)异常表示不可预知的,程序应当自行避免,例如数组下标越界,访问空指针异常等等。 4、Java的异常体系,从责任角度来看。 答:Error属于JVM需要负担的责任。RuntimeException是程序应该负担的责任。Checked Exception可检查异常是Java编译器应该负担的责任。 5、常见Error以及Exception。RuntimeException运行时异常。 答:1)、第一种,NullPointerException空指针引用异常。 6、非RuntimeException非运行时异常。 答:1)、第一种,ClassNotFoundException,找不到指定的class的异常。 7、Error错误异常。 答:1)、第一种,NoClassDefFoundError,找不到class定义的异常。造成的原因包含,类依赖的class或者jar包不存在。类文件存在,但是存在不同的域中。大小写问题,javac编译的时候无视大小写的,很有可能编译出来的class文件就与想要的不一样。 8、Java的异常处理机制,Exception的处理机制。 答:1)、第一步、抛出异常,创建异常对象,交由运行时系统处理。当一个方法出现错误引发异常的时候,方法创建异常对象,并交付给运行时系统,系统对象中包含了异常类型,异常出现时的程序状态等异常信息,运行时系统负责寻找处置异常的代码并执行。 2)、第二步、捕获异常,寻找合适的异常处理器处理异常,否则终止运行。方法抛出异常以后,运行时系统将转为寻找合适的异常处理器,即ExceptionHandle。潜在的异常处理是异常发生时依次存留在调用栈方法的集合,当异常处理器所能处理的异常类型与抛出的异常类型相符的时候,即为合适的异常处理器,运行时系统从发生异常的方法开始依次回查调用栈中的方法直至找到含有异常处理器的方法并执行。当运行时系统遍历了调用栈都没有找到合适的异常处理器,则运行时系统终止,java程序终止。 9、Java异常的处理规则。 答:具体明确,抛出的异常应能通过异常类名和message准确说明异常的类型和产生异常的原因。 10、try-catch的性能问题。Java异常处理消耗性能的地方。 答:第一点、try-catch块影响JVM的优化。 11、集合之List和Set的区别,如下所示。 11.1、备注:线程安全和线程不安全的集合: Vector、HashTable、Properties是线程安全的。 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接口的自然排序。 自然排序代码实现,如下所示: 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。 4)、如何优化Hashtable呢?如何设计ConcurrentHashMap呢? a)、通过锁细粒度化,将整锁拆解成多个锁进行优化。对象锁之间是不相互制约的,因此,我们可以将原本一个锁的行为拆分多个锁,早期的ConcurrentHashMap也是这样做的,ConcurrentHashMap早期使用的是分段锁技术(由数组和链表组成),通过分段锁Segment来实现,将锁一段一段的进行存储,然后给每一段数据配一把锁即Segment,当一个线程占用一把锁即Segment的时候,然后访问其中一段数据的时候呢,位于其他Segment的数据也能被其他线程同时访问,默认是分配16个Segment,理论上比Hashtable效率提升了16倍,相比于早期的HashMap,就是将hashMap的table数组逻辑上拆分成多个子数组,每个子数组配置一把锁,线程在获取到某把分段锁的时候,比如,获取到编号为8的Segment之后呢,才能操作这个子数组,而其他线程想要操作该子数组的时候,只能被阻塞,但是如果其他线程操作的是其他未被占用的Segment所管辖的子数组,那么是不会被阻塞的。此时呢,可以将分段锁拆分的更细,或者不使用分段锁,而是table里面的每个bucket都用一把不同的锁进行管理,ConcurrentHashMap的效率就得到了更好的提高。 5)、Hashtable、HashMap、ConcurrentHashMap的区别,面试回答: a)、HashMap线程不安全的,底层是通过数组 + 链表 + 红黑树。键值对key-value均可以为null,但是hashtable,ConcurrentHashMap两个类都不支持。 d)、HashMap的key、value均可以为null,而其它的两个类Hashtable、ConcurrentHashMap不支持的。 14、HashMap中的put方法的逻辑,如下所示: 1)、如果HashMap未被初始化过,则进行初始化操作。 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值。 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,所以直接拿这个散列值使用不现实的。 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插入头节点,失败则循环重试,如果插入失败,则说明有别的线程插入头节点了,需要再次循环进行操作。 20、ConcurrentHashMap的put方法的逻辑。 1)、判断Node[]数组是否初始化,没有则进行初始化操作。 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包的基础。 22、java.util.concurrent简称为JUC,JUC包的分类。 答:1)、线程执行器executor,就是任务的执行和调度的框架,此外,在tools包可以看到和executor相关的Executors类,用来创建ExecutorService、ScheduledExecutorService、ThreadFactory、Callable对象等等。 23、java.util.concurrent简称为JUC,JUC包的并发工具类。 答:四个同步器,同步器的作用主要是用于协助线程的同步。 1)、闭锁CountDownLatch。让主线程等待一组事件发生后继续执行,这里面的事件指的是CountDownLatch里的countDown()方法。 值的注意的是其它线程调用完countDown()方法之后还是会继续执行的,也就是说,countDown()方法调用之后并不代表该子线程已经执行完毕,而是告诉主线程说你可以继续执行,至少我这边不托你后腿了,具体还需要看其它线程给不给力了,如图,引入了CountDownLatch之后了,主线程就进入了等待状态,此时CountDownLatch里面有一个cnt变量开始的时候初始化为一个整数,这里就是事件的个数,我们的变量初始化为3,m每当其中一个子线程调用countDown()方法之后,这个计数器便会减一,直到所有的子线程都调用了countDown()方法,cnt变为零之后,主线程才得以重新恢复到执行的状态。 2)、栅栏CyclicBarrier,阻塞当前线程,等待其它线程。 a)、等待其它线程,且会阻塞自己当前线程,所有线程必须同时到达栅栏位置后,才能继续执行。 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,一个由数据结构组成的有界阻塞队列,有边界的意思容量是有限的,我们必须在其初始化的时候指定它的容量大小,容量大小一旦指定就不可改变了,以先进先出的方式来存储数据的,最新插入的对象是在尾部,最先移除的对象是在头部。 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
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中提供的方法。 30、NIO-Buffers的类型,这些Buffer覆盖了我们能通过IO发送的基本数据类型。 1)、ByteBuffer。 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)、支持一个进程所能打开的最大连接数。 33、AIO,Asynchronous IO,基于事件和回调机制,异步非阻塞的方式,可以理解为应用操作直接返回,而不会阻塞在哪里,当后台处理完成,操作系统就会通知相应线程进行后续工作。 AIO属于异步模型,用户线程可以同时处理别的事情,AIO如何进一步加功处理结果。Java提供了两种方法。 1)、基于回调,实现CompletionHandler接口,调用的时候触发回调函数,在调用的时候,把回调函数传递给对应的API即可。 34、BIO、NIO、AIO对比。
|
|