Java刷题基础语法

一、Java集合概览

​ Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

​ Java 集合框架如下图所示：

• List：存储的元素是有序的、可重复的。
  • ArrayList：Object[] 数组。
  • Vector：线程安全，使用 synchronized 进行同步，了解即可。
  • LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)。
• Set：存储的元素不可重复的。
  • HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
  • LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
  • TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)。
• Queue：按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
  • PriorityQueue: Object[] 数组来实现小顶堆。
  • DelayQueue:PriorityQueue。
  • ArrayDeque: 可扩容动态双向数组。
• Map：使用键值对（key-value）存储。key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
  • HashMap：JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
  • LinkedHashMap：LinkedHashMap 在 HashMap的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
  • Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
  • TreeMap：红黑树（自平衡的排序二叉树）。

二、常见数据结构及用法

1. 数组

1）赋值

1. 初始化时直接赋值

int[] intArray = new int[]{1, 2, 3, 4};

2. 通过 Java Util 类的 Arrays.fill(arrayname,value)

int[] intArray = new int[10];
// Arrays.fill(arrayname, value) 
Arrays.fill(intArray, 100);
// Arrays.fill(arrayname, starting index, ending index, value) 
Arrays.fill(intArray, 3, 6, 50);

注：Arrays.fill只能给一维数组赋初值，二维数组需要循环赋值。如下：

int[][] intArray = new int[10][10];
for(int i = 0; i < intArray.length; ++i) {
	Arrays.fill(intArray[i], 100);
}

2）遍历

1. for循环遍历

for (int i = 0; i < intArray.length; ++i) {
	System.out.println(intArray[i]);
}
// for-each遍历，与for遍历等价
for (int a: intArray) {
	System.out.println(a);
}

3）数组复制

1. 直接赋值（没有拷贝）

intArray2和intArray1是指向同一个数组对象的。

int[] intArray1 = new int[]{1, 2, 3, 4, 5};
int[] intArray2 = intArray1;

2. System.arraycopy（浅拷贝）

方法：arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

返回了一个新的数组对象，但是这两个数组里面的内容都是指向同一个引用的。

int[] intArray1 = new int[]{1, 2, 3, 4, 5};
int[] intArray2 = new int[5];
System.arraycopy(intArray1, 0, intArray2, 0, intArray1.length);

3. Arrays.copyOf和Arrays.copyOfRange（浅拷贝）

方法：copyOf(T[] original, int newLength)和copyOfRange(T[] original, int from, int to)

• 如果newLength不合法，即小于0，那么抛出NegativeArraySizeException异常
• 如果newLength小于源数组长度，则复制指定长度的数组元素
• 如果newLength大于源数组长度，则新数组中超出源数组长度的元素则是默认值

返回了一个新的数组对象，但是这两个数组里面的内容都是指向同一个引用的。

int[] intArray1 = new int[]{1, 2, 3, 4, 5};
int[] intArray2 = Arrays.copyOf(intArray1, intArray1.length);
int[] intArray3 = Arrays.copyOfRange(intArray1, 0, intArray1.length);

4. 对象拷贝（Object.clone）

clone()比较特殊，对于对象而言，它是深拷贝，但是对于数组而言，它是浅拷贝。拷贝数组时会返回一个新的数组对象，但是这两个数组里面的内容都是指向同一个引用的。

4）Arrays 类

java.util.Arrays 类能方便地操作数组，它提供的所有方法都是静态的。

能够给数组赋值、对数组排序、比较数组和查找数组元素。具体如下表：

方法	说明
int binarySearch(Object[] a, Object key)	用二分查找算法在给定数组中搜索给定值的对象。数组在调用前必须排序好的。如果查找值包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。也可以调用**binarySearch(Object[], int fromIndex, int toIndex, Object key)**在指定位置查找给定值。
boolean equals(long[] a, long[] a2)	若两个数组以相同顺序包含相同的元素，则两个数组是相等的。适用于所有的其他基本数据类型。
void fill(int[] a, int val)	将指定的 int 值分配给指定 int 型数组指定范围中的每个元素。适用于所有的其他基本数据类型。
void sort(Object[] a)	对指定对象数组根据其元素的自然顺序进行升序排列。适用于所有的其他基本数据类型。可以传入方法指定按照特定方法排序。例如，Collections.reverseOrder()进行反向排序；String.CASE_INSENSITIVE_ORDER进行忽略大小写排序。
String toString(Object[] a)	能将数组中的内容全部打印出来。适用于所有的其他基本数据类型。

举例如下：

int[] intArray = new int[5];
// 调用Arrays.fill进行赋值
Arrays.fill(intArray, 4);
// 调用Arrays.sort进行排序
Arrays.sort(intArray);
// 调用Arrays.sort从指定位置进行排序
Arrays.sort(intArray, 2, 4);
// 调用Arrays.sort进行反向排序
Arrays.sort(intArray, Collections.reverseOrder());
// 调用Arrays.binarySearch查找指定元素
System.out.println(Arrays.binarySearch(arr, 30));
// 调用Arrays.toString打印数组元素
System.out.print(Arrays.toString(intArray));

5）数组与List之间相互转换

- 对象数组转为基本数据类型数组

1. stream流执行转换

int[] intArray = integerArray.stream().mapToInt(Integer::valueOf).toArray();

- 基本数据类型数组转为对象数组

1. stream流执行转换

Integer[] integerArray = Arrays.stream(intArray).boxed().toArray(Integer[]::new);

- 对象数组转为List

1. 最常见方式，但不支持增删（会抛异常）

List intList = Arrays.asList(intArray);

2. 数组转为List后，支持增删改查的方式

ArrayList<Integer> intList = new ArrayList<Integer>(Arrays.asList(intArray));

3. 通过集合工具类Collections.addAll()方法（最高效）

ArrayList<Integer> intList = new ArrayList<Integer>(intArray.length);
Collections.addAll(intList, intArray);

4. 使用stream中的collector

List<Integer> intList = Arrays.stream(intArray).collect(Collectors.toList());

- List转为对象数组

1. toArray()方法，需要传入对应的对象数组构造函数并指定数组的长度

Integer[] intArray = intList.toArray(new Integer[intList.size()]);

2. stream流的toArray()方法，需要传入对应对象的构造方法的方法引用

Integer[] intArray = intList.stream().toArray(Integer[]::new);

- List转为基本数据类型数组

1. stream流执行转换

// 方法引用
int[] intArray1 = intList.stream().mapToInt(Integer::intValue).toArray();
// lambda表达式
int[] intArray2 = intList.stream().mapToInt(i->i).toArray();
// 先使用filter过滤
int[] intArray3 = intList.stream().filter(integer -> integer!=null).mapToInt(i->i).toArray();

- 基本数据类型数组转为List

1. stream流执行转换

List<Integer> intList1 = Arrays.stream(intArray).mapToObj(Integer::new).collect(Collectors.toList());
// 采用boxed装箱
List<Integer> intList2 = Arrays.stream(intArray).boxed().collect(Collectors.toList());

2. 利用CollectionUtils集合工具类进行转换

List<Integer> intList = CollectionUtils.arrayToList(intArray);

2. 列表 List

1）Collection通用方法：

Collection 接口	方法
元素个数	size()
是否为空	isEmpty()
是否包含某元素	contains(Object o)
迭代器	iterator()
清空所有元素	clear()
转为数组	toArray()
增加元素	add(E e)
删除元素	remove(Object o)

2）遍历

1. for循环遍历

for (int i = 0; i < intList.length; ++i) {
	System.out.println(intArray[i]);
}
// for-each遍历，与for遍历等价
for (int a: intList) {
	System.out.println(a);
}

2. for-each遍历

intList.forEach(a -> System.out.println(a));

3）排序

1. 使用List.sort排序。

可以使用lambda函数按照指定顺序排序。例如：

List<Integer> intList = new ArrayList<>();
// 按照从大到小的顺序排序
intList.sort((o1, o2) -> o2 - o1);

2. 使用Collections.sort排序。

同样可以使用lambda函数按照指定顺序排序。例如：

List<Integer> intList = new ArrayList<>();
Collections.sort(intList);
// 按照从大到小的顺序排序
Collections.sort(intList, (o1, o2) -> o2.compareTo(o1));
// 这等价于
Collections.sort(intList, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});

4）Collections工具类

• 排序操作

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后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

• 查找,替换操作

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

3. 队列 Queue

1）基础队列

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

2）优先队列 PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。方法与Queue相同。

PriorityQueue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

利用Lambda表达式自定义比较函数。例如：

PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2-o1);

这等价于：

PriorityQueue<Integer> q = new PriorityQueue<Integer>(
	new Comparator<Integer>() {
       @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
	}
);

注：Java中默认为小根堆，C++中默认为大根堆。

3）双端队列 Deque

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口，增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

Deque 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

4. 栈 Stack

Stack继承自Vector，与Vector一样使用synchronized关键字修饰来保证线程安全，但也因此效率低下。因此，在实际应用中多采用Deque来实现栈的功能。例如：

Deque deque = new LinkedList<Integer>();

另外，从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。ArrayDeque 也可以用于实现栈。使用如下：

Deque deque = new ArrayDeque<Integer>();

当作为栈使用时，可以采用如下方法：

Deque 接口	抛出异常	返回特殊值
入栈	push(E e)
出栈	pop()	poll()
查看栈顶	element()	peek()

5. 字符串 String

方法说明	方法
指定索引处的 char 值	char charAt(int index)
字符串长度	int length()
判断字符串是否为空	boolean isEmpty()
返回字符串的副本，忽略前导空白和尾部空白。	String trim()
将String 中的所有字符都转换为小写	String toLowerCase()
将String 中的所有字符都转换为大写	[String toUpperCase()
比较两个字符串	int compareTo(String anotherString)
比较两个字符串是否相等	boolean equals(Object anObject)
连接字符串	String concat(String str)
将此字符串转换为一个新的字符数组	char[] toCharArray()
返回一个新的字符串，是此字符串的子字符串	String substring(int beginIndex)
	String substring(int beginIndex, int endIndex)
字符串是否有指定前缀/后缀	boolean startsWith(String prefix)
	boolean startsWith(String prefix, int toffset)
	boolean endsWith(String suffix)
指定字符第一次出现的索引	int indexOf(String str)
	int indexOf(String str, int fromIndex)
指定字符最后一次出现的索引	int lastIndexOf(String str)
	int lastIndexOf(String str, int fromIndex)
替换字符串	String replace(char oldChar, char newChar)
	String replaceAll(String regex, String replacement)
	String replaceFirst(String regex, String replacement)
拆分字符串	String[] split(String regex)
	String[] split(String regex, int limit)

6. 字典 Map

1）基本操作

方法说明	方法
map的长度	size()
插入元素	put(Object key, Object value)
获取元素	get(Object key)
移除元素	remove(Object key)
清空map	clear()
map是否为空	isEmpty()
是否包含指定key	containsKey(Object key)
是否包含指定value	containsValue(Object value)

2）排序

Map<String, String> map = new TreeMap<String, String>((o1, o2)->o2-o1);
// 这等价于
Map<String, String> map = new TreeMap<String, String>(new Comparator<String>() {
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);
    }
});

3）for循环遍历

- keySet()遍历

for (String key : map.keySet()) {
    System.out.println(key + " ：" + map.get(key));
}
// 这等价于
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
    String key = iterator.next();
    System.out.println(key + "　：" + map.get(key));
}

- entrySet()遍历

for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " ：" + entry.getValue());
}
// 这等价于
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, String> entry = iterator.next();
    System.out.println(entry.getKey() + "　：" + entry.getValue());
}

- for-each遍历

map.forEach((k, v)->times.add(v));

三、常用算法

1. 通过stream()

1）List取最值

intList.stream().max(Integer::compareTo).get();
intList.stream().min(Integer::compareTo).get();

2）List取平均值

intList.stream().mapToInt(Integer::intValue).average().orElse(0D);

3）List求和

integers.stream().reduce(Integer::sum).get();

四、参考文档

Java集合常见面试题总结

java中数组拷贝（深拷贝）的四种方法

Java map 详解 - 用法、遍历、排序、常用API等

Java8 stream平均值、最小数、最大数、求和