java基础面试题系列(71 - 80)

20200714 by 1z

1. 请你说明HashMap 和 HashTable的区别

1.是否同步 
	*HashMap是非同步的，HashTable是同步的

2.继承体系 
	*HashTable继承自Dictionary,HashMap继承自AbstractMap类，HashMap允许使用null值（key value都行）

3.内部是否容纳null值
	*HashTable不允许key or value为null，HashMap允许使用null值（key中只能有一个null值，value中可以有多个）

4.遍历方式
	*HashTable使用Enumeration进行遍历，HashMap使用iterator进行遍历

5.HashTable 和 HashMap的扩容方式有所不同
	* HashTable初始化容量为11，每次扩充之后变成原来的2 * n + 1
	* HashMap会动态调整容量为2的幂次方，初始容量为16，之后的每次扩容，容量变为原来的两倍
	
6.HashTable 和 HashMap的计算hash值方式不同
	* HashTable直接使用hash方法，计算的hash值，然后计算index的时候采用除留余数法
		int hash = key.hashCode();
		int index = (hash & 0X7FFFFFFF) % tab.length;
		
	* HashMap实现计算hash值的时候，首先根据元素的key计算hash值，然后通过位移异或操作得到最终结果
		int h;
		return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

1. 请说明快速失败(fail-fast) 和 安全失败（fail-safe）的区别？

一、快速失败（fail—fast）
在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出 Concurrent Modification Exception。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。

注意：这里异常的抛出条件是检测到 modCount != expectedmodCount 这个条件。如果集合发生变化时修改 modCount 值刚好又设置为了 expectedmodCount 值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。

场景：java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。
---------------------------------------------------------------------------------------
二、安全失败（fail—safe）
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。

>缺点：基于拷贝内容的优点是避免了 Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
场景：java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使用，并发修改。


参考链接 ： http://www.cnblogs.com/ygj0930/p/6543350.html

1. 请你说说Iterator 和 ListIterator的区别？

1.Iterator是一个接口，它是集合的迭代器。集合可以通过Iterator去遍历集合中的元素。
但ListIterator是一个功能更加强大的, 它继承于Iterator接口,只能用于各种List类型的访问。

2.ListIterator有add方法，可以向list中添加对象，Iterator不行

3.ListIterator可以实现双向遍历（next(),previous()），而Iterator只能进行单向遍历（next()）

4.ListIterator可以定位当前的索引位置，通过nextIndex 和 previousIndex实现，Iterator不行

5.ListIterator可以实现对当前list中对象的修改(set()),iterator只能单纯的遍历，不能修改

demo
package com.basic_knowledge;

import java.util.*;

public class TestListIterator {

    public static void main(String[] args) {
        ArrayList<String> a = new ArrayList<String>();
        a.add("aaa");
        a.add("bbb");
        a.add("ccc");
        System.out.println("Before iterate : " + a);
        ListIterator<String> it = a.listIterator();
        while (it.hasNext()) {
            System.out.println(it.next() + ", " + it.previousIndex() + ", " + it.nextIndex());
        }
        while (it.hasPrevious()) {
            System.out.print(it.previous() + " ");
        }
        System.out.println();
        it = a.listIterator(1);//调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator。
        while (it.hasNext()) {
            String t = it.next();
            System.out.println(t);
            //修改集合内元素
            if ("ccc".equals(t)) {
                it.set("nnn");
            } else {
                it.add("kkk");
            }
        }
        System.out.println("After iterate : " + a);
    }
}

1. 请简单说明一下什么是迭代器？

迭代器就是提供了一种访问一个集合对象各个元素的途径，同时不会暴露元素的内部细节。

具体在java中使用Iterator 和 Iterable两个接口用来实现集合类的可迭代性

通俗用法: 使用hasNext() 作为循环条件，再用next拿到集合内部元素进行操作

1. 请解释为什么集合类中没有实现Cloneable 和 Serializable接口

先谈一下Cloneable 和 Serializable的作用
*Cloneable的作用
	实现了Cloneable接口，可以调用clone 从而实现深浅拷贝
*Serializable的作用
	如果某个类有需要持久化的需求（存到磁盘中），或者进行远程的对象调用，可以使用序列化实现这些作用
	
上述可以看出，这两个接口的作用主要是针对对象的，而集合类只是为了管理对象而存在的，所以应该在集合类中的具体对象中实现接口，而不是在集合类中体现。

1. 请说明java集合类框架的基本接口有哪些？

一种有两大接口: Collection 和 Map，Collection内部又有Set 和 List子接口
* Collection：代表一组对象，每一个对象都是它的子元素。
* Set：不包含重复元素的Collection。 
* List：有顺序的collection，并且可以包含重复元素。 
* Map：可以把键(key)映射到值(value)的对象，键不能重复。

简单架构图:

java.util.Collection [I]

|—java.util.List [I]

    |—java.util.ArrayList [C]

    |—java.util.LinkedList [C]

    |—java.util.Vector [C]

        |—java.util.Stack [C]

|—java.util.Set [I]

    |—java.util.HashSet [C]

    |—java.util.SortedSet [I]

        |—java.util.TreeSet [C]
java.util.Map [I]

|—java.util.SortedMap [I]

    |—java.util.TreeMap [C]

|—java.util.Hashtable [C]

|—java.util.HashMap [C]

    |—java.util.LinkedHashMap [C]

|—java.util.WeakHashMap [C]

1. 请说明一下ConcurrentHashMap的原理

ConcurrentHashMap内部使用了分段锁的操作，内部存在着两个类HashEntry 和 Segment，HashEntry用来封装map的键值对，Segment用来充当锁的角色。每个Segment对象守护者整个散列表的若干个HashBacket，每个HashBacket是由若干个HashEntry组成的链表或者红黑树。

HashEntry结构
static final class HashEntry<K,V> {
       final K key;                       // 声明 key 为 final 型
       final int hash;                   // 声明 hash 值为 final 型
       volatile V value;                 // 声明 value 为 volatile 型
       final HashEntry<K,V> next;      // 声明 next 为 final 型
  
       HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
           this.key = key;
           this.hash = hash;
           this.next = next;
           this.value = value;
       }
}

ConcurrentHashMap和HashMap在处理数据的过程类似，使用链地址法解决哈希冲突
Segment 继承自 ReentrantLock 实现了并发控制 

static class Segment<K,V> extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        final float loadFactor;
        Segment(float lf) { this.loadFactor = lf; }
    }

详细分析: https://blog.csdn.net/dingjianmin/article/details/79776646?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase

1. 请解释一下TreeMap

TreeMap是一个有序的key-value集合，基于红黑树（Red-Black tree）的 NavigableMap实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator进行排序，具体取决于使用的构造方法。

TreeMap的特性：

1）根节点是黑色 

2）每个节点都只能是红色或者黑色

3）每个叶节点（NIL节点，空节点）是黑色的。 

4)如果一个节点是红色的，则它两个子节点都是黑色的，也就是说在一条路径上不能出现两个红色的节点。

5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

      TreeMap tMap = new TreeMap((o1,o2)->{
      		//指定排序规则
            return (int)o1 - (int)o2;
        });

1. 请说明一下ArrayList是否会越界？

ArrayList的底层是基于数组操作的，可能在并发情况下发生越界

1. 请你说明ConcurrentHashMap有什么优势，1.7和1.8有什么区别

参考链接: https://www.cnblogs.com/like-minded/p/6805301.html