Java面试:List, Set, Map异同

List

List元素以线性方式存储,可以存放重复对象

  • ArrayList:长度可变的数组,可以对元素进行随机的访问,向ArrayList中插入与删除元素的速度慢。JDK8中ArrayList扩容的实现是通过grow()方法实现的,该方法使用语句newCapacity = oldCapacity + (oldCapacity >> 1)计算容量,然后调用Arrays.copyof()方法对原数组进行复制。
  • LinkedList:采用链表数据结构,插入和删除速度快,但是访问速度慢。

Set

Set中的对象不按特定的方式排序,并且没有重复对象

  • HashSet:按照哈希算法来存储集合中的对象,存取速度比较快,当HashSet中的元素个数超过数组大小*loadFactor时,就会进行近似两倍扩容(newCapacity = (oldCapacity << 1) + 1)。
  • TreeSet:实现了SortedSet接口,能够对集合中的对象进行排序。

Map

Map是一种把键对象和值对象映射的集合,它的每一个元素都包含一个键对象和值对象。

  • HashMap:基于散列表实现,其插入和查询<K, V>的开销是固定的,可以通过构造器设置容量和负载因子来调整容器的性能。
  • LinkedHashMap:类似于HashMap,但是迭代遍历它时,取得<K, V>的顺序是其插入次序,或者是最近最少使用的次序。
  • TreeMap:基于红黑树实现。查看<K, V>时,它们会被排序。TreeMap是唯一的带有subMap()方法的Map,该方法可以返回一个子树。

HashMap的实现,原理,机制

底层实现

HashMap底层整体结构是一个数组,数组中的每个元素又是一个链表。每次添加一个对象时会产生一个链表对象(Object类型),Map中的每个Entry就是数组中的一个元素(Map.Entry就是一个键值对),它具有由当前元素指向下一个元素的饮用,这就构成了链表。

存储原理

当向HashMap中添加元素的时候,先根据HashCode计算Key的Hash值,得到数组下标,如果数组该位置已经存在其他元素,那么这个位置的元素将会以链表的形式存放,新假如的放在链表的头部,如果数组该位置元素不存在,那么就直接将该元素放到此数组中的该位置。

去重原理

不同的Key计算到数组下标相同的几率很小,新建一个键值对放入到HashMap的时候,首先会计算Key的数组下标,如果数组该位置已经存在其他元素,则比较两个Key,若相同则覆盖写入,若不同则形成链表。

读取原理

从HashMap中读取元素时,首先计算Key的HashCode,找到数组下标,然后在对应位置的链表中找到需要的元素。

扩容机制

当HashMap中的元素个数超过数组大小*loadFactor时,就会进行2倍扩容。

比较

List

  • 可以允许重复的对象
  • 可以插入多个null元素
  • 是一个有序容器,保持了每个元素的插入顺序,输出的顺序就是插入的顺序
  • 常用的实现类有ArrayList、LinkedList和Vector。ArrayList最为流行,它提供了使用索引的随意访问,而LinkedList则对于经常需要从List中添加或删除元素的场合更为合适

Set

  • 不允许重复对象
  • 无序容器,无法保证每个元素的存储顺序,TreeSet通过Comparator或者Comparable维护了一个排序顺序
  • 只允许一个null元素
  • Set接口最流行的几个实现类是HashSet、LinkedHashSet以及TreeSet。最流行的是基于HashMap实现的HashSet。TreeSet还实现了SortedSet接口,因此TreeSet是一个根据其compare()和compareTo()的定义进行排序的有序容器

Map

  • Map不是Collection的子接口或者实现类,Map是一个接口
  • Map的每个Entry都持有两个对象,也就是一个键一个值,Map可能会持有相同的值对象,但键对象必须是唯一的
  • TreeMap也通过Comparator或者Comparable维护了一个排序顺序
  • Map里可以拥有随意个null值,但最多只能有一个null键
  • Map接口最流行的几个实现类是HashMap、LinkedHashMap、HashTable和TreeMap
    • HashMap:非线程同步,允许null,增长:2的指数倍
    • HashTable:线程安全,不允许null,增长:n*2+1
    • TreeMap:按键排序(默认升序)
    • ConcurrentHashMap:线程同步
    • LinkedHashMap:链表形式

使用场景

  • 使用索引来对容器中的元素进行访问,List是最好的选择。ArrayList提供更快速的访问,而如果需要经常添加删除元素的,选择LinkedList。
  • 若需要容器中的元素能够按照它们插入的次序有序存储,选择List
  • 需要保证插入元素的唯一性,可以选择Set的实现类。
  • 需要键值对的形式存储数据,Map是你正确的选择。

参考

  1. Java中 List、Set、Map 之间的区别
  2. List、Set、Map的区别

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.