tian ci

外观

集合

约 1163 字大约 4 分钟

java

2025-02-14

概览

  1. List, Set, Queue, Map 四者的区别？
    1. Hashset 无序唯一
    2. Treeset 有序唯一（红黑树，自平衡排序二叉树）
    3. Treemap（红黑树，自平衡排序二叉树）
    4. Hashtable 数组+链表组成的，数组是Hashtable的主体，链表是主要为了解决哈希冲突而存在的
  2. 如何选用集合？
    1. 键值对时就用map，需要排序treemap，不需要排序hashmap，线程安全ConcurrentHashMap
    2. 只需要存放元素用collection，需要元素唯一用treeset或hashset，不需要元素唯一用arraylist或linkedlist

Collection

  1. ArrayList 和 Vector 和 LinkedList 的区别？
    1. Vector线程安全；ArrayList适合频繁查找工作，线程不安全；LinkedList线程不安全
    2. ArrayList使用Object数组；LinkedList使用双向链表
    3. ArrayList在末尾插入执行add(E e)时，时间复杂度是O(1)；在指定位置 i 插入时，时间复杂度是O(n-i)；LinkedList头尾插入删除时，时间复杂度是O(1)；在指定位置插入时，时间复杂度时O(n)
    4. ArrayList的空间浪费体现在数组结尾会预留一定的容量空间；LinkedList的空间浪费体现在每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）
  2. Comparable和Comparator的区别？
    1. Comparable出自于java.lang，有一个compareTo(Object obj)的方法；Comparator出自于java.util，有一个compare(Object obj1, Object obj2)的方法
    2. 如果需要排序可以重写Comparable的compareTo方法，或者使用自制的Comparator中compare方法
  3. 无序性和不可重复性具体含义是什么？
    1. 无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
    2. 不可重复性是指添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。
  4. HashSet、LinkedHashSet 和 TreeSet 三者的异同？
    1. 相同点：都能保证唯一，都是线程不安全的
    2. HashSet底层是哈希表，基于HashMap实现；LinkedHashSet底层是哈希表和链表，元素的插入和取出顺序满足FIFO先进先出；TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
    3. HashSet用于不需要保证插入和取出顺序；LinkedHashSet用于保证插入和取出顺序满足FIFO；TreeSet用于支持元素自定义排序
  5. Queue、Deque、ArrayDeque与LinkedList、PriorityQueue
    1. Queue 是单端队列，Deque 是双端队列
    2. Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈
    3. ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能
    4. ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现
    5. ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持
    6. 选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈
    7. PriorityQueue 与 Queue 的区别在于元素出队顺序是与优先级相关
    8. PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
    9. PriorityQueue 在 O(logn) 的时间复杂度内插入元素和删除堆顶元素
    10. PriorityQueue 非线程安全的，且不支持存储 NULL 和 non-comparable 的对象
    11. PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后

Map

  1. HashMap和Hashtable的区别
    1. HashMap非线程安全, Hashtable线程安全(synchronized修饰), ConcurrentHashMap线程安全
    2. HashMap支持null key和null value, Hashtable不支持
    3. Hashtable默认容量是11, 每次扩充是2n+1; HashMap默认容量是16, 每次扩充是2的幂次方大小
    4. HashMap在jdk1.8后底层数据结构发生变化
    5. Hashtable基本被淘汰
  2. HashMap和TreeMap的区别
    1. TreeMap实现NavigableMap有了对集合内搜索的能力
    2. TreeMap实现SortedMap有了对集合中元素根据key排序的能力
  3. HashSet如何检查重复?
    1. 先计算对象的hashcode判断加入的位置，没有相同的hashcode则会认为对象没有重复出现，如果有相同的hashcode，调用equals方法判断对象是否真的相同，如果相同，HashSet不会让其成功插入
  4. HashMap的长度为什么是2的幂次方？
  5. HashMap有哪几种常见的遍历方式？