Java面试宝典

Java String 类

字符串广泛应用 在 Java 编程中，在 Java 中字符串属于对象，Java 提供了 String 类来创建和操作字符串。
String 类有 11 种构造方法，这些方法提供不同的参数来初始化字符串，比如提供一个字符数组参数:

public class StringDemo{
   public static void main(String args[]){
      char[] helloArray = { 'r', 'u', 'n', 'o', 'o', 'b'};
      String helloString = new String(helloArray);  
      System.out.println( helloString );
   }
}

注意:String 类是不可改变的，所以你一旦创建了 String 对象，那它的值就无法改变了（详看笔记部分解析）。

如果需要对字符串做很多修改，那么应该选择使用 StringBuffer & StringBuilder 类。

字符串长度

用于获取有关对象的信息的方法称为访问器方法。
String 类的一个访问器方法是 length() 方法，它返回字符串对象包含的字符数。

连接字符串
String 类提供了连接两个字符串的方法：

string1.concat(string2);

更常用的是使用’+'操作符来连接字符串，如：

"Hello," + " runoob" + "!"

创建格式化字符串
我们知道输出格式化数字可以使用 printf() 和 format() 方法。

String 类使用静态方法 format() 返回一个String 对象而不是 PrintStream 对象。

String 类的静态方法 format() 能用来创建可复用的格式化字符串，而不仅仅是用于一次打印输出。

如下所示：

System.out.printf("浮点型变量的值为 " +
                  "%f, 整型变量的值为 " +
                  " %d, 字符串变量的值为 " +
                  "is %s", floatVar, intVar, stringVar);

你也可以这样写

String fs;
fs = String.format("浮点型变量的值为 " +
                   "%f, 整型变量的值为 " +
                   " %d, 字符串变量的值为 " +
                   " %s", floatVar, intVar, stringVar);

String 方法
下面是 String 类支持的方法，更多详细，参看 Java String API 文档:

SN(序号)	方法描述
1	char charAt(int index)
返回指定索引处的 char 值。
2	int compareTo(Object o)
把这个字符串和另一个对象比较。
3	int compareTo(String anotherString)
按字典顺序比较两个字符串。
4	int compareToIgnoreCase(String str)
按字典顺序比较两个字符串，不考虑大小写。
5	String concat(String str)
将指定字符串连接到此字符串的结尾。
6	boolean contentEquals(StringBuffer sb)
当且仅当字符串与指定的StringBuffer有相同顺序的字符时候返回真。
7	static String copyValueOf(char[] data)
返回指定数组中表示该字符序列的 String。
8	static String copyValueOf(char[] data, int offset, int count)
返回指定数组中表示该字符序列的 String。
9	boolean endsWith(String suffix)
测试此字符串是否以指定的后缀结束。
10	boolean equals(Object anObject)
将此字符串与指定的对象比较。
11	boolean equalsIgnoreCase(String anotherString)
将此 String 与另一个 String 比较，不考虑大小写。
12	byte[] getBytes()
 使用平台的默认字符集将此 String 编码为 byte 序列，并将结果存储到一个新的 byte 数组中。
13	byte[] getBytes(String charsetName)
使用指定的字符集将此 String 编码为 byte 序列，并将结果存储到一个新的 byte 数组中。
14	void getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin)
将字符从此字符串复制到目标字符数组。
15	int hashCode()
返回此字符串的哈希码。
16	int indexOf(int ch)
返回指定字符在此字符串中第一次出现处的索引。
17	int indexOf(int ch, int fromIndex)
返回在此字符串中第一次出现指定字符处的索引，从指定的索引开始搜索。
18	int indexOf(String str)
 返回指定子字符串在此字符串中第一次出现处的索引。
19	int indexOf(String str, int fromIndex)
返回指定子字符串在此字符串中第一次出现处的索引，从指定的索引开始。
20	String intern()
 返回字符串对象的规范化表示形式。
21	int lastIndexOf(int ch)
 返回指定字符在此字符串中最后一次出现处的索引。
22	int lastIndexOf(int ch, int fromIndex)
返回指定字符在此字符串中最后一次出现处的索引，从指定的索引处开始进行反向搜索。
23	int lastIndexOf(String str)
返回指定子字符串在此字符串中最右边出现处的索引。
24	int lastIndexOf(String str, int fromIndex)
 返回指定子字符串在此字符串中最后一次出现处的索引，从指定的索引开始反向搜索。
25	int length()
返回此字符串的长度。
26	boolean matches(String regex)
告知此字符串是否匹配给定的正则表达式。
27	boolean regionMatches(boolean ignoreCase, int toffset, String other, int ooffset, int len)
测试两个字符串区域是否相等。
28	boolean regionMatches(int toffset, String other, int ooffset, int len)
测试两个字符串区域是否相等。
29	String replace(char oldChar, char newChar)
返回一个新的字符串，它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的。
30	String replaceAll(String regex, String replacement)
使用给定的 replacement 替换此字符串所有匹配给定的正则表达式的子字符串。
31	String replaceFirst(String regex, String replacement)
 使用给定的 replacement 替换此字符串匹配给定的正则表达式的第一个子字符串。
32	String[] split(String regex)
根据给定正则表达式的匹配拆分此字符串。
33	String[] split(String regex, int limit)
根据匹配给定的正则表达式来拆分此字符串。
34	boolean startsWith(String prefix)
测试此字符串是否以指定的前缀开始。
35	boolean startsWith(String prefix, int toffset)
测试此字符串从指定索引开始的子字符串是否以指定前缀开始。
36	CharSequence subSequence(int beginIndex, int endIndex)
 返回一个新的字符序列，它是此序列的一个子序列。
37	String substring(int beginIndex)
返回一个新的字符串，它是此字符串的一个子字符串。
38	String substring(int beginIndex, int endIndex)
返回一个新字符串，它是此字符串的一个子字符串。
39	char[] toCharArray()
将此字符串转换为一个新的字符数组。
40	String toLowerCase()
使用默认语言环境的规则将此 String 中的所有字符都转换为小写。
41	String toLowerCase(Locale locale)
 使用给定 Locale 的规则将此 String 中的所有字符都转换为小写。
42	String toString()
 返回此对象本身（它已经是一个字符串！）。
43	String toUpperCase()
使用默认语言环境的规则将此 String 中的所有字符都转换为大写。
44	String toUpperCase(Locale locale)
使用给定 Locale 的规则将此 String 中的所有字符都转换为大写。
45	String trim()
返回字符串的副本，忽略前导空白和尾部空白。
46	static String valueOf(primitive data type x)
返回给定data type类型x参数的字符串表示形式。

数据结构

(1):线性表
[1]:顺序存储结构(也叫顺序表)

一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
[2]:链表
　　　　
链表里面节点的地址不是连续的，是通过指针连起来的。

(2):哈希表

哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

数组的特点是：寻址容易，插入和删除困难；
而链表的特点是：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

Hash 表的查询速度非常的快，几乎是O(1)的时间复杂度。

hash就是找到一种数据内容和数据存放地址之间的映射关系。

散列法：元素特征转变为数组下标的方法。

我想大家都在想一个很严重的问题：“如果两个字符串在哈希表中对应的位置相同怎么办？”,毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用“链表”。我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。

散列表的查找步骤

当存储记录时，通过散列函数计算出记录的散列地址

当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

**缺点：**它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

哈希表的原理：

1，对对象元素中的关键字(对象中的特有数据)，进行哈希算法的运算，并得出一个具体的算法值，这个值 称为哈希值。

2，哈希值就是这个元素的位置。

3，如果哈希值出现冲突，再次判断这个关键字对应的对象是否相同。如果对象相同，就不存储，因为元素重复。如果对象不同，就存储，在原来对象的哈希值基础 +1顺延。

4，存储哈希值的结构，我们称为哈希表。

5，既然哈希表是根据哈希值存储的，为了提高效率，最好保证对象的关键字是唯一的。

这样可以尽量少的判断关键字对应的对象是否相同，提高了哈希表的操作效率。
扩展:

相同的字符串如果存进去，哈希值相同并且equals方法为true，不会存入相同的

只要哈希值相同或者equals方法为true都成立才不会存入，只要其中一条不满足，都会储存

哈希冲突

然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？

哈希冲突的解决方案有多种:

开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）

再散列函数法

链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式

关于hashcode和equals的一些问题，在面试中会问道：

1.两个对象哈希值相同，那么equals方法一定返回true吗？

不一定:取决于如何重写equals，如果重写固定了它返回false，结果就一定是false

2.equals方法返回true，那么哈希值一定相同吗？

一定:如果类中定义一个静态变量（static int a = 1），然后重写hashcode返回a+1，那么每一个对象的哈希值都不一样,不过java中规定：对象相等，必须具有相同的哈希码值，所以这里是一定的

(3)数组
采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

(4)区别
1.数组

优点：(1)随机访问效率高(根据下标查询)，(2)搜索效率较高(可使用折半方法)。

缺点：(1)内存连续且固定，存储效率低。(2)插入和删除效率低(可能会进行数组拷贝或扩容)。

2.链表

优点：(1)不要求连续内存，内存利用率高，(2)插入和删除效率高(只需要改变指针指向)。

缺点：(1)不支持随机访问，(2)搜索效率低(需要遍历)。

3.Hash表

优点：(1)搜索效率高，(2)插入和删除效率较高，

缺点：(1)内存利用率低(基于数组)，(2)存在散列冲突。