[数据结构与算法]每天一道面试题04：Java集合类相关面试题

常见Java的集合类

• List列表
  • ArrayList，基于数组
  • LinkList，基于链表
  • Vector，基于数组，线程安全
  • Stack栈，后进先出
  • ArrayQueue，数组队列，先进后出
• set
  • HashSet，基于哈希表
  • LinkHashSet，基于链表
  • TreeSet，基于树
• map
  • HashMap，基于哈希表
  • LinkHashMap，基于数组
  • TreeMap，基于哈希表
• Queue
  • ArrayDeque，数组实现的双端队列

ArrayList

• 底层是一个Object[]
• 在jdk1.8中默认创建容量为0的数组
• 在容量用完时会自动扩容
• 优化：可以使用ArrayList(int capacity)设置初始化的容量，可以避免一开始就不断扩充容量，影响效率
• 查询效率高，增删效率差

LinkedList

• 底层是一个双向链表
• 增删效率高，查询效率差
• 查询指定下标的元素时，需要从头节点开始遍历
• LinkedList.add方法只能将元素添加道链表末尾，如果要添加到中间，需要使用迭代器方法：ListIterator.add

Vector

• 底层是一个数组
• 当容量用完时，默认扩充为原容量的两倍
• 线程安全的，内置方法都带有synchronized关键字
• 如何将ArrayList变成线程安全的，调用Collections工具类中的synchronizedList(List list)方法

Set

• 是一种泛型
• 在jdk1.5引入，之前都是使用Object[]
• Object[]的缺点
  • 需要强制转换类型
  • 使用方法前需要用instanceof判断对象类型
• 使用Set优点
  • 减少强制转换类型的次数
  • 类型安全
  • 运行阶段在JVM看不到泛型类型
  • 支持lambda表达式

HashSet

• 基于哈希表
• 无序，不可重复

TreeSet

• 底层是树
• 无序，不可重复，但是可以排序
• HashMap的key部分底层是HashSet，TreeMap的key部分底层是TreeSet

Map

• Map和Collections没有继承关系
• Map以键值对形式存储数据，key和value都是存储对象的内存地址（引用）
• Map的迭代方法：
  • 第一类：效率低下，得到Map的key集合keySet，再取出对应的value
    1. 通过foreach遍历map.keySet,取出对应的value
    2. 使用迭代器迭代keySet，取出Value
  • 第二类：效率高，直接从结点中取出key和value
    1. 调用map.entrySet，然后foreach遍历keySet
    2. 调用map.entrySet，然后通过迭代器遍历keySet

HashMap

• 基于数组和单链表
• 数组中每一个元素都是单链表
• 单链表中每一个结点Node的hash值不一定相同，但是下标一定是相同的，因为下标都是通过hash值哈希算法计算的
• 数组查询效率高，单链表增删效率高，HashMap结合了两者的优点
• 无序：因为不知道值挂到哪一个单链表上去了
• 不可重复：使用equals实现不可重复
• 默认初始容量为16（必须为2的次方），加载因子为0.75，即容量使用了3/4就开始扩容
• 在jdk1.7及其以前，使用数组+单链表实现；在jdk1.8时，使用数组+单链表+红黑树实现
  • 单链表元素超过8个，将单链表转换成红黑树
  • 当红黑树结点小于6个，将红黑树转换成单链表
  • 这样做是为了提高检索效率，二叉树的检索会缩小检索范围，提高效率

put()方法原理

1. 将key，value封装到Node中
2. 调用key的hashCode()获得hash值
3. 使用hash值进行哈希函数计算得到下标
   • 如果该下标没有元素，将该结点放入
   • 如果有元素，将Node的key与该链表上的每个结点的key进行equals对比
     • 如果都返回false，将该节点放入到该链表末尾
     • 如果有一个返回了true，那么链表中对应这个结点的value会被Node的value覆盖（保证了不可重复）

注：

• HashMap的key，value可以为null，但是只能有一个（不可重复）
• HashTable的key，value都不能为null

get()方法原理

1. 先调用key的hashCode()函数计算hash值
2. 通过哈希算法，将hash值转化为数组的下标
3. 通过下标定位数组的某个位置：
   • 如果这个位置什么都没有，返回null
   • 如果这个位置有一个链表，将链表所有结点的key与当前key进行equals比对
     • 如果都返回false，那么get方法返回null
     • 如果有一个equals返回了true，那么返回这个结点的value

注：放在HashMap中的key的元素需要同时重写hashCode和equals方法

Hash冲突及其解决

hash冲突：键（key）通过hash函数得到的结果作为地址去存放键值对（key-value）（这就是hashmap的存值方式），当时计算发现这个地址已经存放了键值对，就会产生冲突，这就是hash冲突。

解决方法：

**1、开放定址法：**当冲突发生时，通过某种探测技术在散列表上形成一个探测序列，沿着此序列逐个查找，直到找出一个开放的地址。常见的探测技术有：线性探测、再平方探测、伪随机探测

**2、再哈希法：**对冲突的哈希值再次进行哈希处理，直到没有哈希冲突。

**3、链地址法：**将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针放在哈希表的第i个单元中。链地址法适用于经常进行插入和删除的情况。

**4、建立公共溢出区：**将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，都放入溢出表。

ArrayList和LinkLsit的区别

ArrayList基于数组，对随机index的访问比较快，空间浪费体现在列表结尾的预留空间

LinkList基于链表，增加和删除元素比较快，空间浪费体现在每个元素都需要消耗一定的空间

ArrayList和Vector的区别

Vector是线程安全的类，而ArrayList是非线程安全的。

HashMap在jdk1.7和jdk1.8的区别

• 底层结构：1.7采用数组+链表，1.8采用数组+链表+红黑树
• 初始化方式：哈希表为空时，1.7采用inflateTable()初始化一个数组；1.8采用resize()扩容
• put()实现方式：1.7采用头插法；1.8采用尾插法
• hash()实现方式：1.7直接计算key的hashCode值；1.8采用key的hashCode异或key的hashCode进行无符号右移16位的结果
• 扩容策略：在1.7中，只要元素个数不小于阈值（容量的3/4）就直接扩容2倍。在1.8中，容量未达到64时，以2倍扩容，超过64时，若单链表元素个数超过8个，将单链表转换成红黑树，若红黑树节点小于6个，将红黑树转换成单链表，这样做是为了提高检索效率，二叉树的检索会缩小检索范围，提高效率

String和StringBuffer和StringBuilder的区别

1. String变量不可修改，StringBuffer和StringBuilder可以修改
2. StringBuffer是线程安全的，StringBuilder不是线程安全的。
3. StringBuffer使用了缓存区，StringBuilder没有使用缓存区，所以没有修改数据的情况下，多次调用StringBuffer的toString方法获取的字符串是共享底层的字符数组的。而StringBuilder不是共享底层数组的，每次都生成了新的字符数组。
4. 因为方法被上锁，所以StringBuffer的性能一般会比StringBuilder差，单线程中建议使用StringBuilder。
5. String对象的相加底层调用的是StringBuilder对象，分别调用了append方法和toString方法，所以在大量字符串相加时，使用String对象相加效率低于使用StringBuffer和StringBuilder，因为还有有StringBuilder对象的创建过程和toString方法中字符数组的拷贝过程。

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系