Java面试题-容器

目录

容器概念

使用集合的技巧

集合有哪些方法？

什么是Collections

集合和数组的区别?

Collection和Collections的区别？

集合-数据结构

ArrayList 与 LinkedList、Vector

遍历map集合中所有元素？

Map集合和Collection的区别

Set接口中的方法和Collection中方法一致的。Set接口取出方式只有一种，迭代器。

高级for循环和传统for循环的区别

集合遍历方式

HashMap、HashMap如何保证线程安全?

HashMap及数据结构

HashMap 的工作原理？

HashMap 的扩容机制、扩容过程？

HashMap实现原理，ConcurrentHashMap 实现原理？

HashMap和Hashtable的区别？

什么是二叉树、红黑树，哪里有出现，有点有哪些？

红黑树，为什么允许局部不平衡？

ConcurrentHashMap

ConcurrentHashMap默认初始容量是多少？

ConCurrentHashmap 的key，value是否可以为null?

ConCurrentHashmap 每次扩容是原来容量的几倍?

ConCurrentHashmap的数据结构是怎么样的？

存储在ConCurrentHashmap中每个节点是什么样的，有哪些变量?

ConCurrentHashmap的put过程是怎样的？

java1.8中，ConCurrentHashmap什么情况下链表才会转换成红黑树进行存储？

java1.8中，ConCurrentHashmap的get过程是怎样的？

java1.8中，ConCurrentHashmap是如何计算它的size大小的？

ConcurrentHashMap有哪些构造函数？

ConcurrentHashMap使用什么技术来保证线程安全？

ConcurrentHashMap的get方法是否要加锁，为什么？

ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？

ConcurrentHashMap1.7和1.8的区别

---

容器概念

 

使用集合的技巧

    看到Array就是数组结构，有角标，查询速度很快。

    看到link就是链表结构：增删速度快，而且有特有方法。addFirst； addLast； removeFirst()； removeLast()； getFirst()；getLast()；

    看到hash就是哈希表，就要想要哈希值，就要想到唯一性，就要想到存入到该结构的中的元素必须覆盖hashCode，equals方法。

    看到tree就是二叉树，就要想到排序，就想要用到比较。

    比较的两种方式：

    一个是Comparable：覆盖compareTo方法；

    一个是Comparator：覆盖compare方法。

    LinkedHashSet，LinkedHashMap:这两个集合可以保证哈希表有存入顺序和取出顺序一致，保证哈希表有序。 

集合什么时候用？

    当存储的是一个元素时，就用Collection。当存储对象之间存在着映射关系时，就使用Map集合。 

    保证唯一，就用Set。不保证唯一，就用List。

集合有哪些方法？

add(object)：添加一个元素

addAll(Collection) ：添加一个集合中的所有元素。

clear()：将集合中的元素全删除，清空集合。

remove(obj) ：删除集合中指定的对象。注意：删除成功，集合的长度会改变。

removeAll(collection) ：删除部分元素。部分元素和传入Collection一致。

boolean contains(obj) ：集合中是否包含指定元素 。

boolean containsAll(Collection) ：集合中是否包含指定的多个元素。

boolean isEmpty()：集合中是否有元素。

int size()：集合中有几个元素。

boolean  retainAll(Collection) ：对当前集合中保留和指定集合中的相同的元素。如果两个集合元素相同，返回flase；如果retainAll修改了当前集合，返回true。

Iterator  iterator()：迭代器

将集合变成数组：toArray();

什么是Collections

它的出现给集合操作提供了更多的功能。这个类不需要创建对象，内部提供的都是静态方法。

1. Collections.sort(list);//list集合进行元素的自然顺序排序。
2. Map m = Collections.synchronizeMap(hashMap);//HashMap同步

集合和数组的区别?

1. 数组长度固定，集合长度可变。
2. 数组可以存储基本数据类型、引用数据类型；集合只能存储引用数据类型。
3. 数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

Collection和Collections的区别？

    Collection是个java.util下的接口，它是各种集合类的父接口，继承于它的接口主要有Set和List,

    (提供了关于集合的一些操作,如插入、删除、判断一个元素是否其成员、遍历等)。

    Collections是个java.util下的类，是针对集合类的一个工具类,提供一系列静态方法,实现对集合的排序、搜索、替换、线程安全化（将非同步的集合转换成同步的）等操作

集合-数据结构

ArrayList 与 LinkedList、Vector

List本身是Collection接口的子接口，具备了Collection的所有方法。

List的特有方法都有索引，这是该集合最大的特点

List：元素有序可重复，元素都有索引。//有序(元素存入集合的顺序和取出的顺序一致)。

|--ArrayList：底层数据结构是数组，有角标，查询快，线程不安全。

|--LinkedList：底层数据结构是（双向）链表，增删快查询慢，线程不安全。

|--Vector：底层数据结构是数组，线程安全，Vector无论查询和增删都很慢（因为使用了 synchronized 方法（多线程安全））。

jdk7：创建 ArrayList 对象时，默认长度为 10，类似饿汉模式

jdk8：创建 ArrayList 对象时，默认长度为 0，在你第一次插入数据时，创建一个 长度为10的数组，类似懒汉模式

遍历map集合中所有元素？

Map<Integer, String> map = new HashMap<Integer, String>(); map.put(1, "a"); map.put(2, "b"); map.put(3, "ab"); map.put(4, "ab"); map.put(4, "ab");// 和上面相同 ， 会自己筛选 System.out.println(map.size());

// 第一种： System.out.println("第一种：通过Map.keySet遍历key和value："); for (Integer in : map.keySet()) { //map.keySet()返回的是所有key的值 String str = map.get(in);//得到每个key多对用value的值 System.out.println(in + " " + str); }

    Set keySet = map.keySet();     Iterator it = keySet.iterator();     while(it.hasNext()) {     Object key = it.next();     Object value = map.get(key);     System.out.println(key+":"+value);     }

// 第二种： System.out.println("第二种：通过Map.entrySet使用iterator遍历key和value："); Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();

while (it.hasNext()) { Map.Entry<Integer, String> entry = it.next(); System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());

// 第三种：推荐，尤其是容量大时 System.out.println("第三种：通过Map.entrySet遍历key和value"); for (Map.Entry<Integer, String> entry : map.entrySet()) { //Map.entry<Integer,String> 映射项（键-值对） 有几个方法：用上面的名字entry //entry.getKey() ;entry.getValue(); entry.setValue(); //map.entrySet() 返回此映射中包含的映射关系的 Set视图。 System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); }

// 第四种： System.out.println("第四种：通过Map.values()遍历所有的value，但不能遍历key"); for (String v : map.values()) { System.out.println("value= " + v); }

遍历HashMap:

List<Map<String,Object>> list = readExcel.readExcelcc22(path); try { for (Map<String, Object> map : list) { Set<String> keySet = map.keySet(); for (String string : keySet) { String str = (String) map.get(string); if(str!=null){ if(str=="序号"){} System.out.println(string+":"+dealNum.sumDeal(str)); } } } } catch (Exception e) { }

Map集合和Collection的区别

1.     Collection一次存一个元素；Map一次存一对元素。
2.     Collection是单列集合；Map是双列集合。
3.     Map中的存储的一对元素：一个是键，一个是值，键与值之间有对应(映射)关系。

    特点：要保证map集合中键的唯一性。

Set接口中的方法和Collection中方法一致的。Set接口取出方式只有一种，迭代器。

    |--HashSet：底层数据结构是哈希表，线程是不同步的。无序，高效；

    HashSet集合保证元素唯一性：通过元素的hashCode方法，和equals方法完成的。

    当元素的hashCode值相同时，才继续判断元素的equals是否为true。

    如果为true，那么视为相同元素，不存。如果为false，那么存储。

    如果hashCode值不同，那么不判断equals，从而提高对象比较的速度。

高级for循环和传统for循环的区别

    高级for循环在使用时，必须要明确被遍历的目标。这个目标，可以是Collection集合或者数组，如果遍历Collection集合，在遍历过程中还需要对元素进行操作，比如删除，需要使用迭代器。

    如果遍历数组，还需要对数组元素进行操作，建议用传统for循环因为可以定义角标通过角标操作元素。如果只为遍历获取，可以简化成高级for循环，它的出现为了简化书写。

高级for循环可以遍历map集合吗？不可以。但是可以将map转成set后再使用foreach语句。

集合遍历方式

第一种：迭代器

Collection coll = new ArrayList();

coll.add("abc0");

coll.add("abc1");

coll.add("abc2");

Iterator it = coll.iterator();

while(it.hasNext()){

System.out.println(it.next());

}

//增强for

for(Object obj : list) {

            String s = (String) obj;

            System.out.println(s);

        }

//  普通for

for (int i = 0; i <al.size(); i++) {

System.out.println(al.get(i));

}

HashMap、HashMap如何保证线程安全?

HashMap及数据结构

HashMap 的工作原理？

HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，返回的hashCode用于找到bucket位置来储存Entry对象。如果该位置已经有元素了,调用equals方法判断是否相等,相等的话就进行替换值,不相等的话,放在链表里面.

当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

HashMap 的扩容机制、扩容过程？

当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值，即当前数组的长度乘以加载因子0.75的值的时候，就要自动扩容啦。

初始值不写默认容量16，当添加第13条数据时会触发HashMap扩容机制，扩容( resize )后容量为32，Java 里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。当指定hashMap容量的时候，会使用刚好比指定容量大的最近的2次幂的值为大小。

例一：25，32，24<25，会触发扩容机制。

例二：1000，1024，会。

例三：10000，16192，不会。

为什么二次幂？

hash碰撞

HashMap实现原理，ConcurrentHashMap 实现原理？

HashMap和Hashtable的区别？

Map集合(接口)：

|--HashMap：底层是哈希表数据结构，线程不安全，效率略高，允许空（null）键或值（key）。替代了Hashtable，是Hashtable的轻量级实现

|--Hashtable：底层是哈希表数据结构，线程安全，效率略低。不允许空（null）键或值（key）。

|--HashtSet：基于set实现的，以对象作为元素，且拒绝重复对象。内部使用HashMap实现，其实就是HashMap的一个视图。

|--TreeMap：底层是二叉树结构，可以对map集合中的键进行指定顺序的排序。 |--LinkedHashSet：有序，hashset的子类。

|--TreeSet：对Set集合中的元素的进行指定顺序的排序。不同步。TreeSet底层的数据结构就是二叉树。

什么是二叉树、红黑树，哪里有出现，有点有哪些？

红黑树，为什么允许局部不平衡？

ConcurrentHashMap

ConcurrentHashMap默认初始容量是多少？

从下面ConcurrentHashMap类的静态变量可以看出它的初始容量为16

ConCurrentHashmap 的key，value是否可以为null?

不行 如果key或者value为null会抛出空指针异常

ConCurrentHashmap 每次扩容是原来容量的几倍?

2倍 在transfer方法里面会创建一个原数组的俩倍的node数组来存放原数据。

ConCurrentHashmap的数据结构是怎么样的？

在java1.8中，它是一个数组+链表+红黑树的数据结构。

存储在ConCurrentHashmap中每个节点是什么样的，有哪些变量?

它是实现Map.Entry<K,V>接口。里面存放了hash，key，value，以及next节点。它的value和next节点是用volatile进行修饰，可以保证多线程之间的可见性。

ConCurrentHashmap的put过程是怎样的？

整体流程跟HashMap比较类似，大致是以下几步：

（1）如果桶数组未初始化，则初始化；

（2）如果待插入的元素所在的桶为空，则尝试把此元素直接插入到桶的第一个位置；

（3）如果正在扩容，则当前线程一起加入到扩容的过程中；

（4）如果待插入的元素所在的桶不为空且不在迁移元素，则锁住这个桶（分段锁）；

（5）如果当前桶中元素以链表方式存储，则在链表中寻找该元素或者插入元素；

（6）如果当前桶中元素以红黑树方式存储，则在红黑树中寻找该元素或者插入元素；

（7）如果元素存在，则返回旧值；

（8）如果元素不存在，整个Map的元素个数加1，并检查是否需要扩容；

添加元素操作中使用的锁主要有（自旋锁 + CAS + synchronized + 分段锁）。

java1.8中ConCurrentHashmap节点是尾插还是头插？

尾插法,见上述put方法。

java1.8中，ConCurrentHashmap什么情况下链表才会转换成红黑树进行存储？

链表长度大于8。数组长度大于64。从put源码和以下源码可以看出：并非一开始就创建红黑树结构，如果当前Node数组长度小于阈值MIN_TREEIFY_CAPACITY，默认为64，先通过扩大数组容量为原来的两倍以缓解单个链表元素过大的性能问题。

java1.8中，ConCurrentHashmap的get过程是怎样的？

1、计算 hash 值
2、根据 hash 值找到数组对应位置: (n - 1) & h
3、根据该位置处结点性质进行相应查找

如果该位置为 null，那么直接返回 null 就可以了
如果该位置处的节点刚好就是我们需要的，返回该节点的值即可

如果该位置节点的 hash 值小于 0，说明正在扩容，或者是红黑树，后面我们再介绍 find 方法如果以上 3 条都不满足，那就是链表，进行遍历比对即可

java1.8中，ConCurrentHashmap是如何计算它的size大小的？

对于size的计算，在扩容和addCount()方法就已经有处理了，可以注意一下Put函数，里面就有addCount()函数。

ConcurrentHashMap有哪些构造函数？

一共有五个，作用及代码如下：

//无参构造函数
    public ConcurrentHashMap() {
    }
    //可传初始容器大小的构造函数
    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }
    //可传入map的构造函数
    public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }
    //可设置阈值和初始容量
    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }

    //可设置初始容量和阈值和并发级别
    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }

ConcurrentHashMap使用什么技术来保证线程安全？

jdk1.7：Segment+HashEntry来进行实现的；

jdk1.8：放弃了Segment臃肿的设计，采用Node+CAS+Synchronized来保证线程安全；

ConcurrentHashMap的get方法是否要加锁，为什么？

不需要，get方法采用了unsafe方法，来保证线程安全。

ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？

弱一致性，HashMap强一直性。

ConcurrentHashMap可以支持在迭代过程中，向map添加新元素，而HashMap则抛出了ConcurrentModificationException，因为HashMap包含一个修改计数器，当你调用他的next()方法来获取下一个元素时，迭代器将会用到这个计数器。

ConcurrentHashMap1.7和1.8的区别

jdk1.8的实现降低锁的粒度，jdk1.7锁的粒度是基于Segment的，包含多个HashEntry，而jdk1.8锁的粒度就是Node

数据结构：jdk1.7 Segment+HashEntry；jdk1.8 数组+链表+红黑树+CAS+synchronized