Hurley's 校招面经

# 集合框架 Uncompleted

# 集合的特点

  • 集合可以用于存储对象。
  • 对象的个数确定的话可以使用数组，对象的个数不确定的话可以使用集合，因为集合是可变长度的。

# 集合和数组的区别

  • 数组是固定长度的；集合是可变长度的。
  • 数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。
  • 数据存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型的。

# 常用的集合类

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

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

ArrayList与LinkedList都是List接口的实现类，因此都实现了List的所有未实现的方法。List接口继承了Collection接口，Collection接口又继承了Iterable接口，因此可以看出List同时拥有了Collection与Iterable接口的特性。

# List | Set | Map 三者的区别

List接口存储一组不唯一（即可以有多个元素引用相同的对象），有序的对象

Set中不允许有重复的集合，不会有多个元素引用相同的对象。

Map是使用键值对来存储。Key是不能重复的，是唯一的，Value的值可以相同。

# ArrayList

  • ArrayList实现了List接口，即ArrayList实现了可变大小的数组。它允许所有元素，包括null。
  • 当更多的元素添加到ArrayList时，它的大小会动态增大。它的元素可以通过get/set的方式直接访问，因为ArrayList本质上是一个数组。
  • ArrayList没有同步方法，这意味着它不是线程安全的。如果多个线程同时访问一个List，则必须要自己实现访问同步：List list = Collections.synchronizedList(new LinkedList(...));

# ArrayList的原理 Uncompleted

# LinkedList

LinkedList的结构

  • LinkedList是通过双向链表实现的，添加、删除元素的性能比ArrayList好，但是查询元素的性能较差。
  • LinkedList没有同步方法，这意味着它不是线程安全的。如果多个线程同时访问一个List，则必须要自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：List list = Collections.synchronizedList(new LinkedList(...));

# LinkedList的原理 Uncompleted

# ArrayList与LinkedList的区别

  • ArrayList是动态数组的数据结构实现，而LinkedList是双向链表的数据结构实现。
  • 对于随机访问get和set，ArrayList要优于LinkedList，因为LinkedList需要移动指针。
  • 对于增删操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。
  • LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

# Vector

Vector和ArrayList几乎一样，区别是Vector是线程安全的。因为这个原因，所以它的性能较差，开销比ArrayList大。所以通常情况下推荐使用ArrayList。

Vector类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。这意味着，Vector是「基于数组实现的」。

# HashMap Uncompleted

HashMap是基于Map接口的实现，存储键值对时，它可以接收为null的键和值（其键和值都可以为空），是非同步的，非线程安全的。

Hash table based implementation of the Map interface. The implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

  1. HashMap的工作原理

  2. get()和put()的原理

  3. hash的实现是怎么样的，为什么要这样实现？

  4. 如果HashMap的大小超过了负载因子(load factor)定义的容量怎么办

# HashSet Uncompleted

# HashTable Uncompleted

# ConcurrentHashMap

ConcurrentHashMap同样也分为1.7、1.8的版本，两者在实现上是略有不同的。

# Base 1.7

ConcurrentHashMap数据结构为一个Segment数组，Segment的数据结构又为HashEntry的数组，HashEntry存的就是键值对，可以构成链表的结构。

HashEntry是用来封装散列映射表中的键值对的。在HashEntry类中，key、hash和next域都被声明为final类型，value域则被声明为volatile类型。

static final class HashEntry<K, V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K, V> next;
}

在JDK1.8之前，ConcurrentHashMap是使用了「分段锁」的方式，具体可以理解为把一个大的Map拆分成N个小的HashTable，根据key.hashCode()来决定把key放到哪个HashTable中，即把Map分成了N个Segment，put和get的时候，都是现根据key.hashCode()算出放到哪个Segment中。

原理上来说，ConcurrentHashMap的Segment继承于ReentrantLock，理论上ConcurrentHashMap支持CurrencyLevel（Segment分组数量）的线程并发。每当一个线程占用锁访问一个Segment时，不会影响到其它的Segment。

put的流程：

  1. 将当前的Segment中的table通过key的hashcode值定位到HashEntry
  2. 遍历该HashEntry，如果不为空则判断传入的key和当前遍历的key是否相等，相等则覆盖旧的value
  3. 不为空，则需要新建一个HashEntry并加入到Segment中，同时会先判断是否需要扩容
  4. 最后会解除第1步中获取的当前Segment的锁

get的流程：

只需要将Key通过Hash之后，定位到具体的Segment，再通过一次Hash定位到具体的元素上。由于HashEntry中的value属性是由volatile关键词修饰的，保证了内存可见性，所以每次获取到的都是最新值。整个过程都是不需要加锁的。

# Base 1.8

1.8版本之后，抛弃了Segment分段锁的方式，而是采用了CAS+synchronized来保证并发的安全性。

put的流程：

  • 根据key计算出hashcode
  • 判断是否需要进行初始化
  • 通过key定位出的Node，如果为空就表示当前位置可以写入数据，利用CAS尝试写入，失败则自旋保证成功；
  • 如果当前位置hashcode == MOVED == -1，说明需要扩容
  • 如果都不满足，则使用synchronized锁写入数据
  • 如果数量大于TREEIFY_THRESHOLD则通过treeifyBin转化为红黑树

get的流程：

  • 根据计算出的hashcode寻址，如果在桶上，则直接返回值
  • 如果是红黑树，则按照红黑树的方式获取值
  • 如果不满足，则按照链表的方式遍历获取值

# HashMap与HashTable的区别

  • HashMap是非线程安全的，HashTable是线程安全的，HashTable内部的方法基本都用了同步锁synchronized修饰。
  • 因为线程安全的问题，所以HashMap要比HashTable效率更高，这也是HashTable几乎要被淘汰的原因。
  • HashMap允许有null值的存在，而在HashTable中键值只要有一个null，就会直接抛出空指针异常。

如果使用的JDK5以上的版本，又需要满足线程安全的话，推荐使用ConcurrentHashMap。

可以使用如下两种方法让HashMap同步，即线程安全：

  • Collections.synchronized(hashMap)
  • 使用ConcurrentHashMap

# HashMap与HashSet的区别

  • HashMap实现了Map接口，HashSet实现了Set接口，所以HashSet中不允许有重复的元素
  • HashMap存储的是键值对，HashSet仅存储了对象
  • HashMap使用key来计算hashcode的值，HashSet使用成员对象来计算hashcode的值。如果两个对象的hashcode值相同，就需要使用equals()方法来判断对象的相等性，如果两个对象不同，就返回false。
  • HashMap比较快，因为是使用唯一的键来获取对象，HashSet较HashMap来说比较慢。
  • HashMap和HashSet都是线程不安全的

使用HashSet，首先要确保在将对象存储在HashSet之前，确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等，因为需要确保set中没有存储相等的对象。

# HashMap与ConcurrentHashMap的区别

  • HashMap是线程不安全的，ConcurrentHashMap是线程安全的。
  • HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。

# Collections工具类常用方法：

  1. 排序
  2. 查找，替换操作
  3. 同步控制（不推荐，需要线程安全的集合类型时请考虑使用JUC包的并发集合）

排序操作

void reverse(List list)	// 反转
void shuffle(List list) // 随机排序
void sort(List list) // 按自然排序的升序排序
void sort(List list, Comparator c) // 定制排序，由Comparator控制排序逻辑
void swap(List list, int i, int j) // 交换两个索引位置的元素
void rotate(List list, int distance) // 旋转。当distance为正数时，将list后distatnce个元素整体移到前面。当distance为负数时，将list的前distance个元素整体移到后面。

查找，替换操作

int binarySearch(List list, Object key) // 对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)	// 根据元素的自然顺序，返回最大元素
int max(Collection coll, Comparator c) // 根据定制排序，返回最大元素，排序规则由Comparatator类控制
void fill(List list, Object obj) // 用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o) // 统计元素出现个数
int indexOfSubList(List list, List target) // 统计target在list中第一次出现的索引
boolean replaceAll(List list, Object oldVal, Object newVal) // 用新元素替换旧元素

同步控制

因为HashSet、TreeSet、ArrayList、LinkedList、HashMap、TreeMap都是线程不安全的。Collections提供了多个synchronizedXxx()静态方法可以把它们包装成线程同步的集合。

最好不要使用下面这些方法，因为效率非常低。

synchronizedCollection(Collection<T> c);
synchronizedList(List<T> list);
synchronizedMap(Map<K, V>, m);
synchronizedSet(Set<T> s);

# Arrays类的常见操作

  1. 排序：sort()
  2. 查找：binarySearch()
  3. 比较：equals()
  4. 填充：fill()
  5. 转列表：asList()
  6. 转字符串：toString()
  7. 赋值：copyOf()

← 线程 →