转载

Java集合框架常见面试题

java基础知识 (๑• . •๑)

Java集合框架常见面试题

这是崔斯特的第一百零一篇原创文章

说说List,Set,Map三者的区别

  • List(对付顺序的好帮手): List接口存储一组不唯一(可以有多个元素引用相同的对象),有序的对象
  • Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。
  • Map(用Key来搜索的专家): 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象,但Key不能重复,典型的Key是String类型,但也可以是任何对象。

Arraylist 与 LinkedList 区别

  • 1. 是否保证线程安全: ArrayListLinkedList 都是不同步的,也就是不保证线程安全;
  • 2. 底层数据结构: Arraylist 底层使用的是 Object 数组LinkedList 底层使用的是 双向链表 数据结构(JDK1.6之前为循环链表,JDK1.7取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)
  • 3. 插入和删除是否受元素位置的影响:
    • ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行 add(E e) 方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话( add(int index, E element) )时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
    • LinkedList 采用链表存储,所以对于add(E e)方法的插入,删除元素时间复杂度不受元素位置的影响 ,近似 O(1),如果是要在指定位置i插入和删除元素的话((add(int index, E element)) 时间复杂度应为o(n))因为需要新创立一个新的链表,复制前i-1个元素并在第i位加入新的元素,最后附上n-i个元素。
  • 4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) 方法)。
  • 5. 内存空间占用: ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)。

补充内容:RandomAccess接口

public interface RandomAccess{
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以,在我看来 RandomAccess 接口不过是一个标识罢了。标识什么? 标识实现这个接口的类具有随机访问功能。

binarySearch( )方法中,它要判断传入的list 是否 RamdomAccess 的实例,如果是,调用 indexedBinarySearch() 方法,如果不是,那么调用 iteratorBinarySearch() 方法

public static <T>
int binarySearch(List<? extends Comparable<?super T>> list, T key){
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

ArrayList 实现了 RandomAccess 接口, 而 LinkedList 没有实现。为什么呢?我觉得还是和底层数据结构有关! ArrayList 底层是数组,而 LinkedList 底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。, ArrayList 实现了 RandomAccess 接口,就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识,并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的!

下面再总结一下 list 的遍历方式选择:

RandomAccess
RandomAccess

双向链表和双向循环链表

双向链表:包含两个指针,一个prev指向前一个节点,一个next指向后一个节点。

Java集合框架常见面试题

双向循环链表:最后一个节点的 next 指向head,而 head 的prev指向最后一个节点,构成一个环。

Java集合框架常见面试题

ArrayList 与 Vector 区别

Vector 类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

Arraylist 不是同步的,所以在不需要保证线程安全时建议使用Arraylist。

ArrayList 的扩容机制

详见笔主的这篇文章: 通过源码一步一步分析ArrayList 扩容机制

#HashMap 和 Hashtable 的区别

  1. 线程是否安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!);
  2. 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它;
  3. 对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛出 NullPointerException。
  4. 初始容量大小和每次扩充容量大小的不同 : ①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小(HashMap 中的 tableSizeFor() 方法保证,下面给出了源代码)。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
  5. 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。

HashMap 中带有初始容量的构造函数:

public HashMap(int initialCapacity, float loadFactor){
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
 public HashMap(int initialCapacity){
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

下面这个方法保证了 HashMap 总是使用2的幂作为哈希表的大小。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap){
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

HashMap 和 HashSet区别

如果你看过 HashSet 源码的话就应该知道:HashSet 底层就是基于 HashMap 实现的。(HashSet 的源码非常非常少,因为除了 clone()writeObject()readObject() 是 HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。

HashMap HashSet
实现了Map接口 实现Set接口
存储键值对 仅存储对象
调用 put() 向map中添加元素 调用 add() 方法向Set中添加元素
HashMap使用键(Key)计算Hashcode HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,

HashSet如何检查重复

当你把对象加入 HashSet 时,HashSet会先计算对象的 hashcode 值来判断对象加入的位置,同时也会与其他加入的对象的hashcode值作比较,如果没有相符的hashcode,HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象,这时会调用 equals() 方法来检查hashcode相等的对象是否真的相同。如果两者相同,HashSet就不会让加入操作成功。(摘自我的Java启蒙书《Head fist java》第二版)

hashCode()与equals()的相关规定:

  1. 如果两个对象相等,则hashcode一定也是相同的
  2. 两个对象相等,对两个equals方法返回true
  3. 两个对象有相同的hashcode值,它们也不一定是相等的
  4. 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖
  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。

==与equals的区别

  1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
  2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较
  3. ==指引用是否相同 equals()指的是值是否相同

HashMap的底层实现

JDK1.8之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列 。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化,但是原理不变。

  static final int hash(Object key){
    int h;
    // key.hashCode():返回散列值也就是hashcode
    // ^ :按位异或
    // >>>:无符号右移,忽略符号位,空位都以0补齐
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对比一下 JDK1.7的 HashMap 的 hash 方法源码.

static int hash(int h){
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 ,JDK 1.7 的 hash 方法的性能会稍差一点点,因为毕竟扰动了 4 次。

所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

Java集合框架常见面试题

JDK1.8之后

相比于之前的版本, JDK1.8之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。

Java集合框架常见面试题

TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。

推荐阅读:

  • 《Java 8系列之重新认识HashMap》 : https://zhuanlan.zhihu.com/p/21673805

HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上面也讲到了过了,Hash 值的范围值-2147483648到2147483647,前后加起来大概40亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash ”。(n代表数组长度)。这也就解释了 HashMap 的长度为什么是2的幂次方。

这个算法应该如何设计呢?

我们首先可能会想到采用%取余的操作来实现。但是,重点来了: “取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。

原文  https://zhangslob.github.io/2019/11/11/Java集合框架常见面试题/
正文到此结束
Loading...