精华内容
下载资源
问答
  • java集合常见面试题附带答案解析
  • java集合常见面试题

    2021-04-19 10:40:32
    List:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector Set:一个无序(存入和取出顺序有可能不一致)...

    1. List,Set,Map三者的区别?

    • List:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector
    • Set:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet
    • Map是一个键值对集合,存储键、值和之间的映射。 Key无序,唯一;value 不要求有序,允许重复。Map 的常用实现类:HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

    2. 集合框架底层的数据结构

    • List集合
      • Arraylist和Vector使用的是 Object 数组, LinkedList使用双向循环链表
    • Set集合
      • HashSet(无序,唯一):基于 HashMap 实现的,HashSet的值作为key,value是Object类型的常量
      • LinkedHashSet继承HashSet,并且通过 LinkedHashMap 来实现的
      • TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树。)
    • Map集合
      • HashMap由数组+链表+红黑树组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,当链表长度大于阈值(默认为8)并且数组长度大于64时,将链表转化为红黑树
      • LinkedHashMap(有序) 继承自 HashMap,底层仍然是数组+链表+红黑树组成。另外,LinkedHashMap 在此基础上,节点之间增加了一条双向链表,使得可以保持键值对的插入顺序
      • HashTable无序,数组+链表组成的,数组是 HashTable的主体,链表则是主要为了解决哈希冲突而存在的
      • TreeMap有序,红黑树

    3. 集合框架的扩容

    • ArrayList和Vector默认初始容量为10,当元素个数超过容量长度时都进行进行扩容,ArrayList扩容为原来的1.5倍,而Vector扩容为原来的2倍
    • HashSet和HashMap默认初始容量为16,加载因子为0.75:即当元素个数超过容量长度的0.75倍时,进行扩容,扩容为原来的2倍。HashSet基于 HashMap 实现的,因此两者相同
    • HashTable:默认初始容量为11,加载因子为0.75,扩容策略是2倍+1,如 初始的容量为11,一次扩容后是容量为23

    4. HashMap 的实现原理以及JDK1.7和JDK1.8的区别?

    实现原理

    数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。我们综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构哈希表。并且使用最常用的一种方法—— 拉链法来实现哈希表。

    在这里插入图片描述
    数组存储的元素是一个Entry类,这个类有三个数据域,key、value(键值对),next(指向下一个Entry)。当两个key经过计算得到的index(索引)相同时,即产生哈希冲突时,用链地址法来解决哈希冲突,即通过next属性将索引值相同的链接在一起。随着map的容量或者链表长度越来越大,在进行进一步的优化,比如使用红黑树。

    存储过程
    • HashMap个put()方法:
      第一步首先将k,v封装成Node节点。第二步调用hashCode()方法得出hash值并将hash值转换成数组的下标,下标位置上如果没有任何元素(没有碰撞),就把Node节点添加到这个位置上。如果说下标对应的位置上有值(hash碰撞)。碰撞的元素与要插入的元素key值相等,直接进行value的更新;如果key值不相同,于是增长链表或者树节点的增加。插入之后判断是否进行扩容。
    • HashMap个get()方法:
      先调用k的hashCode()方法得出哈希值,并转换成数组的下标。第二步:通过数组下标快速定位到某个位置上。如果该位置上什么都没有,则返回null。如果这个位置上有数据,那么它就会拿着参数k和单向链表上(红黑树)的每一个节点的k进行equals,如果所有equals方法都返回false,则get方法返回null。如果其中一个节点的k和参数k进行equals返回true,那么返回该节点的value。
    区别
    • JDK1.7是数组+链表,无冲突时,存放数组;冲突时,存放链表;采用头插法。
    • JDK1.8是数组 + 链表 + 红黑树,无冲突时,存放数组;有冲突存放链表或者红黑树,当链表长度大于阈值(默认为8)并且数组长度大于64时,将链表转化为红黑树;树元素小于等于6时,树结构还原成链表形式。

    5. HashMap是怎么解决哈希冲突的?

    1. 使用链地址法(链表)来链接拥有相同hash值的数据;
    2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;
    3. 引入红黑树进一步降低遍历的时间复杂度,使得遍历更快;
    • 扰动函数的解释:
      如果只使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode的高位(与自己右移16位进行异或)也参与运算,来获取hash值,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动。
      在这里插入图片描述

    6. 为什么默认长度和扩容后的长度都必须是 2 的幂

    获取数组索引的计算方式为 key 的 hash 值与数组长度减一按位与,当长度为 2 的幂时减一的值的二进制位数一定全为 1,这样数组下标 index 的值完全取决于 key 的 hash 值的后几位,只要key 的 hash 值分布均匀,HashMap 中Node也就尽可能是均匀的,所以当长度为 2 的幂时不同的 hash 值发生碰撞的概率比较小。

    7. HashMap的数据的迁移机制

    由于数组的容量是以2的幂次方扩容的,新的位置要么在原位置,要么在原长度+原位置的位置。因为数组长度变为原来的2倍,表现为key 的 hash 值在二进制上就是多了一个高位参与数组下标确定。此时,一个元素通过hash转换坐标的方法计算后,恰好出现一个现象:最高位是0则坐标不变,最高位是1则坐标变为“原长度+原坐标”。 因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好。
    例如:HashMap扩容之前为16,那么length-1的二进制为01111,同理扩容后的数组长度为32,length-1二进制表示为011111。我们可以看出扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,那么就是在原先位置;差异位为1,就在原长度+原位置

    8. HashMap的排序操作

    具体可参考:
    https://blog.csdn.net/qq_39033181/article/details/115891134

    9. ConcurrentHashMap 底层具体实现

    • 在 JDK1.7 中,ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。Segment 继承了 ReentrantLock,是一种可重入锁。HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组,一个 Segment 里包含一个 HashEntry 数组 ,每个 HashEntry 是一个链表结构的元素,因此 JDK1.7 的 ConcurrentHashMap 是一种数组+链表结构。当对 HashEntry 数组的数据进行修改时,必须首先获得与它对应的 Segment 锁,这样只要保证每个 Segment 是线程安全的,也就实现了全局的线程安全

    在这里插入图片描述

    • 在 JDK1.8 中采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点。如果相应位置的Node还没有初始化,则调用CAS插入相应的数据;如果相应位置的Node不为空,如果该节点的first.hash!=-1,则对该节点加synchronized锁,更新节点或插入新节点; 如果该节点的first.hash=-1,则扩容。读操作无锁,Node节点的val和next使用volatile修饰,数组也用volatile修饰。
      在这里插入图片描述

    10. 其他

    java基础常见面试题
    并发编程常见面试题目
    JVM常见面试题汇总
    MySQL数据库常见面试题目
    Spring常见面试题总结

    感觉写的不错的话,麻烦来一波关注三连,后期还会有更新~感谢!!

    展开全文
  • Java集合常见面试题

    2020-03-10 19:49:28
    1)说说常见集合有哪些吧? 答:Map接口和Collection接口是所有集合框架的父接口: Collection接口的子接口包括:Set接口和List接口 Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及...

    1)说说常见的集合有哪些吧?

    答:Map接口和Collection接口是所有集合框架的父接口:

    • Collection接口的子接口包括:Set接口和List接口
    • Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
    • Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等
    • List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等

    2)HashMap与HashTable的区别?

    答:

    • HashMap没有考虑同步,是线程不安全的;Hashtable使用了synchronized关键字,是线程安全的;
    • HashMap允许K/V都为null;后者K/V都不允许为null;
    • HashMap继承自AbstractMap类;而Hashtable继承自Dictionary类

    3)HashMap的put方法的具体流程?

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
        // 1.如果table为空或者长度为0,即没有元素,那么使用resize()方法扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 2.计算插入存储的数组索引i,此处计算方法同 1.7 中的indexFor()方法
        // 如果数组为空,即不存在Hash冲突,则直接插入数组
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 3.插入时,如果发生Hash冲突,则依次往下判断
        else {
            HashMap.Node<K,V> e; K k;
            // a.判断table[i]的元素的key是否与需要插入的key一样,若相同则直接用新的value覆盖掉旧的value
            // 判断原则equals() - 所以需要当key的对象重写该方法
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // b.继续判断:需要插入的数据结构是红黑树还是链表
            // 如果是红黑树,则直接在树中插入 or 更新键值对
            else if (p instanceof HashMap.TreeNode)
                e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 如果是链表,则在链表中插入 or 更新键值对
            else {
                // i .遍历table[i],判断key是否已存在:采用equals对比当前遍历结点的key与需要插入数据的key
                //    如果存在相同的,则直接覆盖
                // ii.遍历完毕后任务发现上述情况,则直接在链表尾部插入数据
                //    插入完成后判断链表长度是否 > 8:若是,则把链表转换成红黑树
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 对于i 情况的后续操作:发现key已存在,直接用新value覆盖旧value&返回旧value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 插入成功后,判断实际存在的键值对数量size > 最大容量
        // 如果大于则进行扩容
        if (++size > threshold)
            resize();
        // 插入成功时会调用的方法(默认实现为空)
        afterNodeInsertion(evict);
        return null;
    }
    

    在这里插入图片描述

    4)HashMap的扩容操作是怎么实现的?

    /**
     * 该函数有2中使用情况:1.初始化哈希表;2.当前数组容量过小,需要扩容
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;// 扩容前的数组(当前数组)
        int oldCap = (oldTab == null) ? 0 : oldTab.length;// 扩容前的数组容量(数组长度)
        int oldThr = threshold;// 扩容前数组的阈值
        int newCap, newThr = 0;
    
        if (oldCap > 0) {
            // 针对情况2:若扩容前的数组容量超过最大值,则不再扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 针对情况2:若没有超过最大值,就扩容为原来的2倍(左移1位)
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
    
        // 针对情况1:初始化哈希表(采用指定或者使用默认值的方式)
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    
        // 计算新的resize上限
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // 把每一个bucket都移动到新的bucket中去
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    

    5)HashMap是怎么解决哈希冲突的?

    答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行;

    什么是哈希?

    • Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

    • 所有散列函数都有如下一个基本特性:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同。

    什么是哈希冲突?

    • 当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。

    HashMap的数据结构

    • 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突:
      在这里插入图片描述
      这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化

    hash()函数

    • 上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下:
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或)
    }
    

    在这里插入图片描述

    • 通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn);

    总结

    • 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的:
    1. 使用链地址法(使用散列表)来链接拥有相同hash值的数据;
    2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;
    3. 引入红黑树进一步降低遍历的时间复杂度,使得遍历更快;

    6)HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标?

    • hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置;

    面试官:那怎么解决呢?

    • HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均;

    • 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题;

    面试官:为什么数组长度要保证为2的幂次方呢?

    • 只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,即实现了key的定位,2的幂次方也可以减少冲突次数,提高HashMap的查询效率;
    • 如果 length 为 2 的次幂 则 length-1 转化为二进制必定是 11111……的形式,在于 h 的二进制与操作效率会非常的快,而且空间不浪费;如果 length 不是 2 的次幂,比如 length 为 15,则 length - 1 为 14,对应的二进制为 1110,在于 h 与操作,最后一位都为 0 ,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。

    面试官:那为什么是两次扰动呢?

    • 这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的;

    7)HashMap在JDK1.7和JDK1.8中有哪些不同?

    在这里插入图片描述

    8)为什么HashMap中String、Integer这样的包装类适合作为K?

    • 答:String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率

    • 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况

    • 答:重写hashCode()和equals()方法

    • 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞;

    • 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性;

    9)ConcurrentHashMap和Hashtable的区别?

    • 答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。

    10)Java集合的快速失败机制 “fail-fast”?

    • 是java集合的一种错误检测机制,当多个线程对集合进行结构上的改变的操作时,有可能会产生 fail-fast 机制。
    • 例如:假设存在两个线程(线程1、线程2),线程1通过Iterator在遍历集合A中的元素,在某个时候线程2修改了集合A的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生fail-fast机制。
    • 原因:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。
    • 解决办法:
      • 在遍历过程中,所有涉及到改变modCount值得地方全部加上synchronized。
      • 使用CopyOnWriteArrayList来替换ArrayList

    11)ArrayList 和 Vector 的区别?

    • 这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合,即存储在这两个集合中的元素位置都是有顺序的,相当于一种动态的数组,我们以后可以按位置索引来取出某个元素,并且其中的数据是允许重复的,这是与 HashSet 之类的集合的最大不同处,HashSet 之类的集合不可以按索引号去检索其中的元素,也不允许有重复的元素。

    • ArrayList 与 Vector 的区别主要包括两个方面:

      • 同步性:

      • Vector 是线程安全的,也就是说它的方法之间是线程同步(加了synchronized 关键字)的,而 ArrayList 是线程不安全的,它的方法之间是线程不同步的。如果只有一个线程会访问到集合,那最好是使用 ArrayList,因为它不考虑线程安全的问题,所以效率会高一些;如果有多个线程会访问到集合,那最好是使用 Vector,因为不需要我们自己再去考虑和编写线程安全的代码。

      • 数据增长:

      • ArrayList 与 Vector 都有一个初始的容量大小,当存储进它们里面的元素的个人超过了容量时,就需要增加 ArrayList 和 Vector 的存储空间,每次要增加存储空间时,不是只增加一个存储单元,而是增加多个存储单元,每次增加的存储单元的个数在内存空间利用与程序效率之间要去的一定的平衡。Vector 在数据满时(加载因子1)增长为原来的两倍(扩容增量:原容量的 2 倍),而 ArrayList 在数据量达到容量的一半时(加载因子 0.5)增长为原容量的 (0.5 倍 + 1) 个空间。

    12)ArrayList和LinkedList的区别?

    • LinkedList 实现了 List 和 Deque 接口,一般称为双向链表;ArrayList 实现了 List 接口,动态数组;
    • LinkedList 在插入和删除数据时效率更高,ArrayList 在查找某个 index 的数据时效率更高;
    • LinkedList 比 ArrayList 需要更多的内存;

    面试官:Array 和 ArrayList 有什么区别?什么时候该应 Array 而不是 ArrayList 呢?

    • Array 可以包含基本类型和对象类型,ArrayList 只能包含对象类型。
    • Array 大小是固定的,ArrayList 的大小是动态变化的。
    • ArrayList 提供了更多的方法和特性,比如:addAll(),removeAll(),iterator() 等等。
    • 对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。

    13)HashSet是如何保证数据不可重复的?

    答:HashSet的底层其实就是HashMap,只不过我们HashSet是实现了Set接口并且把数据作为K值,而V值一直使用一个相同的虚值来保存,我们可以看到源码:

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
    }
    
    • 由于HashMap的K值本身就不允许重复,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V,那么在HashSet中执行这一句话始终会返回一个false,导致插入失败,这样就保证了数据的不可重复性;
    展开全文
  • java 集合常见面试题

    2020-03-17 15:52:44
    3、List 的 4、ArrayList 大小 5、ArrayList 扩容过程 6、HashMap 和 TreeMap 区别 相同点: HashMap 非线程安全,TreeMap 非线程安全,都继承了 AbstractMap。 不同点: 1、HashMap:基于哈希表实现。使用 ...

    1、HashMap 和 HashTable 区别

    (1) 线程安全性不同
    HashMap 是线程不安全的,HashTable 是线程安全的,其中的方法是 Synchronize 的,在多线程并发的情况下,可以直接使用 HashTable,但是使用 HashMap 时必须自己增加同步处理。

    (2) 是否提供 contains 方法
    HashMap 只有 containsValue 和 containsKey 方法。HashTable 有 contains、containsKey 和 containsValue 三个方法,其中 contains 和 containsValue方法功能相同。

    (3) key 和 value 是否允许 null 值
    Hashtable 中,key 和 value 都不允许出现 null 值。HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。

    (4) 数组初始化和扩容机制
    HashTable 在不指定容量的情况下的默认容量为 11,而 HashMap 为 16,Hashtable 不要求底层数组的容量一定要为 2 的整数次幂,而 HashMap 则要求一定为 2 的整数次幂。Hashtable 扩容时,将容量变为原来的 2 倍加 1,而 HashMap 扩容时,将容量变为原来的 2 倍。

    2、TreeSet 和 HashSet 区别

    HashSet 是采用 hash 表来实现的。其中的元素没有按顺序排列,add()、remove() 以及 contains() 等方法都是复杂度为 O(1) 的方法。

    TreeSet 是采用树结构实现(红黑树)。元素是按顺序进行排列,add()、remove()以及 contains()等方法都是复杂度为 O(log(n)) 的方法。它还提供了一些方法来处理排序的 set,first(),last() 等。

    3、List 的题

    在这里插入图片描述

    4、ArrayList 大小

    在这里插入图片描述

    5、ArrayList 扩容过程

    在这里插入图片描述

    6、HashMap 和 TreeMap 区别

    相同点:
    HashMap 非线程安全,TreeMap 非线程安全,都继承了 AbstractMap。

    不同点:
    1、HashMap:基于哈希表实现。使用 HashMap 要求添加的键类明确定义了 hashCode() 和 equals()(可以重写 hashCode() 和 equals()),为了优化 HashMap 空间的使用,您可以调优初始容量和负载因子。
    TreeMap:基于红黑树实现。TreeMap没有调优选项,因为该树总处于平衡状态。

    2、HashMap:适用于在 Map 中插入、删除和定位元素。
    TreeMap:适用于按自然顺序或自定义顺序遍历键(key)。
    HashMap 通常比 TreeMap 快一点(树和哈希表的数据结构使然),建议多使用 HashMap,在需要排序的 Map 时候才用 TreeMap。
    HashMap 的结果是没有排序的。TreeMap 实现 SortMap 接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用 Iterator 遍历 TreeMap 时,得到的记录是排过序的。HashMap 里面存入的键值对在取出的时候是随机的,它根据键的 HashCode 值存储数据,根据键可以直接获取它的值,具有很快的访问速度。在 Map 中插入、删除和定位元素,HashMap 是最好的选择。TreeMap 取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。

    总结:
    1、实现
    TreeMap:SortedMap 接口,基于红黑树
    HashMap:基于哈希散列表实现
    2、存储
    TreeMap:默认按键的升序排序
    HashMap:随机存储
    3、遍历
    TreeMap:Iterator 遍历是排序的
    HashMap:Iterator 遍历是随机的
    4、性能损耗
    TreeMap:插入、删除
    HashMap:基本无
    5、键值对
    TreeMap:键、值都不能为 null
    HashMap:只允许键、值均为 null
    6、安全
    TreeMap:非并发安全 Map
    HashMap:非并发安全 Map
    7、效率
    TreeMap:低
    HashMap:高
    一般情况下我们选用 HashMap,因为 HashMap 的键值对在取出时是随机的,其依据键的 hashCode 和键的 equals 方法存取数据,具有很快的访问速度,所以在 Map 中插入、删除及索引元素时其是效率最高的实现。而 TreeMap 的键值对在取出时是排过序的,所以效率会低点。

    展开全文
  • Java 集合常见面试题

    2019-05-19 16:47:21
    ArrayList是容量可以改变的非线程安全集合。内部实现使用数组进行存储,集合扩容时会创建更大的数组空间,把原有数据复制到新数组中。ArrayList支持对元素的快速随机访问,但是插入与删除时速度通常很慢,因为这个...

    1、ArrayList和LinkedList区别?

    ArrayList是容量可以改变的非线程安全集合。内部实现使用数组进行存储,集合扩容时会创建更大的数组空间,把原有数据复制到新数组中。ArrayList支持对元素的快速随机访问,但是插入与删除时速度通常很慢,因为这个过程很有可能需要移动其他元素。

    LinkedList的本质是双向链表。与ArrayList相比,LinkedList的插入和删除速度更快,但是随机访问速度则很慢。测试表明,对于10万条的数据,与ArrayList相比,随机提取元素时存在数百倍的差距。除继承AbstractList抽象类外,LinkedList还实现了另一个接口Deque,即double-ended queue。这个接口同时具有队列和栈的性质。LinkedList包含3个重要的成员:size、first、last。size是双向链表中节点的个数。first和last分别指向第一个和最后一个节点的引用。LinkedList的优点在于可以将零散的内存单元通过附加引用的方式关联起来,形成按链路顺序查找的线性结构,内存利用率较高。【1】

    ......

     

     

     

     

     

     

     

    【1】《码出高效:Java 开发手册》

    展开全文
  • 一、常见java集合以及面试常见问题 集合的继承体系 Set、Map、List三者对比 Set(底层基于Map实现) (1)不允许重复对象 (2)无序容器(就是无法保证每个元素的存储顺序,TreeSet通过Comparator或者...
  • Java的集合类主要由两个接口派生而出:Collection和Map,Collection和Map是Java集合框架的根接口,这两个接口又包含了一些子接口或实现类。 2. Collection 接口是一组允许重复的对象。 3. Set 接口继承 Collection,...
  • Java集合常见面试题集锦

    千次阅读 多人点赞 2019-11-06 17:32:41
    集合Java中的一个非常重要的一个知识点,主要分为List、Set、Map、Queue三大数据结构。它们在Java中的结构关系如下: Collection接口是List、Set、Queue的父级接口。 Set接口有两个常用的实现类:HashSet和...
  • Java集合常见面试题

    2020-12-18 20:06:00
    java8的ConcurrentHashMap为何放弃分段锁,为什么要使用CAS+Synchronized取代Segment+ReentrantLock JDK 1.8 以后,ConcrrentHashMap 采用的是在HashMap 的基础上对每个桶加锁的形式实现的,取代了原来 segment + ...
  • Java集合常见面试题--1

    2020-02-14 19:50:54
    这个乍一看没有什么思路(因为Map是个集合,当然也有可能是我记错了),所以我们可以先介绍一下Map然后转到HashMap中 Map是一种使用键值对存储的集合。Map会维护与Key有关联的值。两个Key可以引用相同的对象,但...
  • Java集合常见面试题(一)

    万次阅读 2018-08-11 20:25:08
    集合和数组的区别: 1:数组是固定长度的;集合可变长度的。 2:数组可以存储基本数据类型,也可以存储引用数据类型;集合只能存储引用数据类型。 3:数组存储的元素必须是同一个数据类型;集合存储的对象可以是...
  • Set是无序集合,并且不允许重复的元素 List是有序的集合,并且允许重复的元素 而Map是键值对 它被视为是键的set和值的set的组合 Map被设计为键值对的集合,所以不需要继承Collection 接口 2.HashMap和Hashtable...
  • Java集合框架常见面试题.pdf
  • Java集合框架常见面试题夜间阅读版.pdf
  • java集合常见面试题

    2019-03-19 14:04:40
    java集合常见面试题集合是什么?介绍Collection框架的结构Collection 和Collections 的区别?为何Collection不从Cloneable和Serializable接口继承?为何Map接口不继承Collection接口?什么是迭代器(Iterator)?...
  • 剖析面试常见问题之 Java 集合框架1.1. 集合概述1.1.1. Java 集合概览1.1.2. 说说 List,Set,Map 三者的区别?1.1.3. 集合框架底层数据结构总结1.1.3.1. List1.1.3.2. Set1.1.3.3. Map1.1.4. 如何选用集合?1.1.5. ...
  • Java集合常见面试题

    2019-03-08 12:14:33
    其次你们也可以看我自己写的关于Java集合面试问题和解决方案。 1,collection是Java.util包下的接口类,它继承了Iterable接口,实现Iterable接口的类可以增强for循环,Iterable接口必须提供一个名为Iterator()的...
  • (这几道Java集合框架面试题在面试中几乎必问)...(Java集合框架常见面试题)https://www.cnblogs.com/iwenwen/p/11052689.html (关于Java集合框架面试题(含答案)上)https://www.jb51.net/article/76411....
  • 本文转载自:Java集合框架常见面试题总结 一. List,Set,Map三者的区别及总结 List:对付顺序的好帮手 List接口存储一组不唯一(可以有多个元素引用相同的对象),有序的对象 Set:注重独一无二的性质 不允许重复的...
  • java常见集合面试题

    2019-03-13 09:26:22
    对于Java来说集合是普遍存在的,也是面试经常问到的,所以对于这些问题,我整理了一些常用的Java集合问题。 一、Iterator为什么接口没有具体的实现? Iterator接口定义了遍历集合的方法,但它的实现则是集合实现类的...
  • 剖析面试常见问题之 Java 集合框架1.1. 集合概述1.1.1. Java 集合概览1.1.2. 说说 List,Set,Map 三者的区别?1.1.3. 集合框架底层数据结构总结1.1.3.1. List1.1.3.2. Set1.1.3.3. Map1.1.4. 如何选用集合?1.1.5. ...
  • java集合常见面试题总结1、java集合体系(List、Set、Collection、Map的区别和联系)2、Vector和ArrayList的区别和联系3、ArrayList和LinkedList的区别和联系4、HashMap和Hashtable的区别和联系5、HashSet的使用和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,261
精华内容 504
关键字:

java集合常见面试题

java 订阅