结合数据结构来看看Java的String类

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 结合数据结构来看看Java的String类

点击蓝字“程序员考拉”欢迎关注!

数据结构中定义字符串是由零个或多个字符组成的有限序列,有限,指出字符串的长度是一个有限的数值;所谓的序列,说明串的相邻字符之间具有前驱和后继的关系。字符串一般记为s=”a1a2…an“(n=0),其中s是字符串的名称,用双引号括起来的字符序列是串的值,注意引号不属于串的内容。字符ai可以由字母,数字或其他字符组成,i(1≤i≤n)就是该字符在串中的位置。

在Java语言中将字符串作为对象来处理,可以通过访问Java API帮助文档java.lang包下的String类来看看字符串的相关方法。

首先看看String继承的超类和实现的接口有哪些?

1.字符串的常用方法

1.1 常用的构造方法底层实现

123456789101112131415161718192021222324252627282930313233
//1.由字符串original复制得到新的字符串public String(String original) {   this.value = original.value;   this.hash = original.hash;}//2.得到值等于value的字符串public String(char[] value) {   this.value = Arrays.copyOf(value, value.length);}//3.返回字符串从第i个位置起的前j个字符public String(char[] value, int offset, int count) {   //判断索引i是否合法   if (offset  0) {       throw new StringIndexOutOfBoundsException(offset);   }   //判断计数值是否合法   if (count = 0) {       if (count  0) {           throw new StringIndexOutOfBoundsException(count);       }       //如果计数值等于0,返回的是空字符       if (offset = value.length) {           this.value = "".value;           return;       }   }   //索引值字符串长度-计数值,抛异常   if (offset  value.length - count) {       throw new StringIndexOutOfBoundsException(offset + count);   }   //其余情况返回要求值   this.value = Arrays.copyOfRange(value, offset, offset+count);}

//1.由字符串original复制得到新的字符串
public String(String original) {
this.value = original.value;
this.hash = original.hash;
}
//2.得到值等于value的字符串
public String(char[] value) {
this.value = Arrays.copyOf(value, value.length);
}
//3.返回字符串从第i个位置起的前j个字符
public String(char[] value, int offset, int count) {
//判断索引i是否合法
if (offset 0) {
throw new StringIndexOutOfBoundsException(offset);
}
//判断计数值是否合法
if (count = 0) {
if (count 0) {
throw new StringIndexOutOfBoundsException(count);
}
//如果计数值等于0,返回的是空字符
if (offset = value.length) {
this.value = “”.value;
return;
}
}
//索引值字符串长度-计数值,抛异常
if (offset value.length - count) {
throw new StringIndexOutOfBoundsException(offset + count);
}
//其余情况返回要求值
this.value = Arrays.copyOfRange(value, offset, offset+count);
}

1.2 equals方法

String中的equals()方法用来判断字符串的内容是否相等。String类中的equals方法是对父类Object类中的equals方法的覆盖,先来看下Object类的equals方法怎么写的:

123
public boolean equals(Object obj) {   return (this == obj);}

public boolean equals(Object obj) {
return (this == obj);
}

这里的this哪个对象调用该方法,this就指代哪个对象。

String中的equals()方法底层源码:

12345678910111213141516171819202122232425
public boolean equals(Object anObject) {   //调用该方法的对象与比较的参数相等,则返回true   if (this == anObject) {       return true;   }   //instanceof 运算符是用来在运行时指出对象是否是特定类的一个实例   if (anObject instanceof String) {       String anotherString = (String)anObject;       int n = value.length;       //首先比较两个字符串实例长度是否相等       if (n == anotherString.value.length) {           char v1[] = value;           char v2[] = anotherString.value;           int i = 0;           //比较两个字符串对应位置的字符是否相等           while (n-- != 0) {               if (v1[i] != v2[i])                   return false;               i++;           }           return true;       }   }   return false;}

public boolean equals(Object anObject) {
//调用该方法的对象与比较的参数相等,则返回true
if (this == anObject) {
return true;
}
//instanceof 运算符是用来在运行时指出对象是否是特定类的一个实例
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
//首先比较两个字符串实例长度是否相等
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
//比较两个字符串对应位置的字符是否相等
while (n– != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}

 也就是说,使用equals()方法是用来比较两个字符串的内容是否相等,它通过以下方法实现:

  • 首先判断两个字符串实例是否是同一个对象,如果是,那么它们的内容相等,返回true;
  • 如果不是同一个对象,判断该对象是否是String类的实例,如果是,将该对象实例强转为String类,判断二者的长度是否相等;
  • 若满足长度相等,再一一比较两个字符串对应位置的字符是否相等;

提到equals方法,就得结合“==”操作符来看了。“==”操作符用来比较操作数的值之间的关系,对于基本数据类型,变量存储的是值本身,而对于引用数据类型,变量存储的是对象的地址,比较的是两个对象的内存地址是否相等。

String类代表字符串,Java程序中的所有字符串文字比如“abc”都被实现为此类的实例。字符串一经创建后,它的值是不可以改变的,也就是说“abc”不可以再变成“abcd”。这就要求我们使用String的时候应该注意:尽量不要做字符串频繁的拼接操作。因为字符串一旦创建不可改变,只要频繁拼接,就会在字符串常量池中创建大量的字符串对象,给垃圾回收带来问题。

为了提升字符串的访问效率,在程序中使用了缓冲技术,所有被双引号括起来的字符串都会在JVM运行时数据区的字符串常量池中新建一份,(字符串常量池存储在方法区中)。如果程序中用到“abc”,会先在字符串常量池中查找有没有该字符串,如果找到直接拿来用,找不到就在字符串常量池中新建一个”abc”。

如下的代码,判断两个字符串是否相等:

123
String A="a";String B="a";System.out.println(A==B);  //true

String A=”a”;
String B=”a”;
System.out.println(A==B); //true

前面提到过“==”是用来比较值相等。程序中第一次出现”a”时,先在字符串常量池中新建一个字符串”a”对象,A指向该对象,当程序中再次出现”a”时,会先在字符串常量池中查找,发现已经创建了”a”,于是直接拿来用了,使用B指向,也就是A,B引用指向的是同一对象,所以打印输出true。

再来看看String中的构造方法:

结合数据结构来看看Java的String类

这个方法是初始化新创建的String对象,使其表示与参数相同的字符序列,换句话说,新创建的字符串时参数字符串的副本。

看下面代码,判断是否相等:

123
String C=new String("a");String D=new String("a");System.out.println(C==D);  //false

String C=new String(“a”);
String D=new String(“a”);
System.out.println(C==D); //false

参数字符串“a”对象,创建之前先在字符串常量池中查找有没有该对象,没有则创建;然后构造方法String(String original)以”a”为参数,new出两个对象存在堆中,C和D引用分别指向这两个对象,很明显C和D引用指向的是两个不同的对象,即上面这两行代码创建了三个不同的对象,方法区中一个,堆中两个。

2.字符串的模式匹配

子串在主串中的定位操作称为串的模式匹配,串的模式匹配应该算串的重要操作之一。来看看朴素的模式匹配算法。

根据要求从主串的第i个位置开始遍历。子串从第0个位置开始,如果相应位置的字符相等,则主串子串各向后移动一位判断下一位字符,如果不等,主串回到匹配位置的下一位,子串从0位开始,循环遍历,直到找到子串,最后返回子串在主串中的索引。简单地说,就是对主串的每一个字符作为子串开头,与要匹配的字符串进行匹配,这种匹配方式称为朴素的模式匹配算法。实现代码如下:

1234567891011121314151617181920212223242526272829303132333435363738
package com.java.String;/** 串的模式匹配* */public class IndexTest { public static void main(String[] args){   int s=indexSearch("eateqweapple","app",8);   System.out.println(s); } //朴素的模式匹配算法,返回子串T在主串S中第pos个字符之后的位置 public static int indexSearch(String S,String T,int pos){   //默认值规定为0   int index=0;   int Slen=S.length();   int Tlen=T.length();   //S位置下标   int i=pos;    //T位置下标   int j=0;    while((iSlen)&&(jTlen)){     char s=S.charAt(i);     char t=T.charAt(j);     if(s==t){       //如果当前位置的相等,都各加1比较下一位置       i=i+1;       j=j+1;     }else{       //否则回到主串S匹配的下一位置,子串从头开始       i=i+1;       j=0;     }     if(jTlen-1){        index=i-Tlen;     }   }   return index; }}

package com.java.String;
/*

  • 串的模式匹配
  • */
    public class IndexTest {
    public static void main(String[] args){
    int s=indexSearch(“eateqweapple”,”app”,8);
    System.out.println(s);
    }
    //朴素的模式匹配算法,返回子串T在主串S中第pos个字符之后的位置
    public static int indexSearch(String S,String T,int pos){
    //默认值规定为0
    int index=0;
    int Slen=S.length();
    int Tlen=T.length();
    //S位置下标
    int i=pos;
    //T位置下标
    int j=0;
    while((iSlen)&&(jTlen)){
    char s=S.charAt(i);
    char t=T.charAt(j);
    if(s==t){
    
     //如果当前位置的相等,都各加1比较下一位置
     i=i+1;
     j=j+1;
    
    }else{
    
     //否则回到主串S匹配的下一位置,子串从头开始
     i=i+1;
     j=0;
    
    }
    if(jTlen-1){
    
      index=i-Tlen;
    
    }
    }
    return index;
    }
    }

算法复杂度分析:

最好的情况,一开始就匹配成功,算法复杂度为O(1); 稍微差一些,每次匹配都是首字母不匹配,但遍历到主串的最后位置匹配成功,算法复杂度为O(n+m);最坏的情况,每次匹配不成功都是发生在子串的最后一个字符,时间复杂度为O((n-m+1)*m)。

 朴素的模式匹配算法算很简单的解决子串定位问题的算法了。想一想Java底层那些封装好的方法,我们真是站在了巨人的肩膀上。

好看的话右下角可以点个”好看”哦!

结合数据结构来看看Java的String类
本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 结合数据结构来看看Java的String类


 上一篇
Java虚拟机的内部体系结构 Java虚拟机的内部体系结构
点击蓝字“程序员考拉”欢迎关注! 1.Java程序执行流程 Java程序的执行依赖于编译环境和运行环境。源码代码转变成可执行的机器代码,由下面的流程完成: Java技术的核心就是Java虚拟机,因为所有的Java程序都在虚拟
下一篇 
【加精】面试必会之ArrayList源码分析&手写ArrayList 【加精】面试必会之ArrayList源码分析&手写ArrayList
注:本文所有方法和示例基于jdk1.8 简介 ArrayList是我们开发中非常常用的数据存储容器之一,其底层是数组实现的,我们可以在集合中存储任意类型的数据,ArrayList是线程不安全的,非常适合用于对元素进行查找,效率非常高。 线