Java中的基本数据结构

Java数组

Java数组定义与初始化的几种方式:

int[] array1 = {1,2,3,4};
int[][] array2 = {{1,2,3},{4,5,6}};
int[] array3 = new int[5];
int[][] array4 = new int[2][3];

关于默认初始化：

1.基本数据类型的数组在创建之后，已经赋默认值 0 （或0L、0.0D、0.0F）；
2.引用类型的数组在创建之后，已经赋默认值null.
3.boolean类型默认值为false，Integer类型为null.

Java获取数组各维度的长度：

System.out.println(array1.length);
System.out.println(array2[0].length);

Java for-each遍历数组：

for(int x: array1){
	System.out.println(x);
}

Java 数组作为函数参数:

传递的是数组的引用，相当于C中的指针

void test(int[] a) {
	a[1] = 5;
    return;
}
//main:
int[] array1 = {1, 2, 3, 4};
System.out.println(array1[1]);
//print 2
m.test(array1);
System.out.println(array1[1]);
//print 5

java数组的比较：

int[] array1 = {1, 2, 3, 4};
int[] array2 = {1, 2, 3, 4};
int[] array3 = array1;
System.out.println(array1 == array2);
//false == 比较地址
System.out.println(array1.equals(array2));     
//false 基本的数据类型的数组的equals方法没有重载Object的equals方法，所以跟“==”效果一样 
System.out.println(Arrays.equals(array1,array2));
//此时返回者为true，Arrays重写了equals
System.out.println(array3 == array1);
//此时返回true，二者地址一样

java数组与List的转换(并没有更好的方法)：

List<Integer> l = new ArrayList<>();
for(int x : array1){
    l.add(x);
}

java数组的排序：

//升序排序
Arrays.sort(array2);
//指定排序的index区间，左包右不包
//output：[4，1，2，3]
int[] array2 = {4,3,2,1};
Arrays.sort(array2,1,4);
//自定义Comparator
people[] array5 = new people[4]；
Arrays.sort(array5, new Comparator<people>() {
	@Override
	public int compare(people a, people b) {
    			return Integer.compare(a.age, b.age);
              }
}
);
//更简单的写法
Arrays.sort(array5, (a, b) -> Integer.compare(a.age, b.age));
//降序排序
//没有直接的方法，拍完倒着输出即可

Java集合框架

整体结构：

ArrayList

List接口是Collection的子接口，用于定义线性表结构，其中ArrayList可以理解为一个动态数组，而LinkedList可以理解为一个链表。

ArrayList的基本操作：

List<Integer> l = new ArrayList<>();
//插入
l.add(1);
l.add(2);
l.add(3);
l.add(4);
l.add(5);
//获取指定位置元素
System.out.println(l.get(1));
//设置指定位置元素
l.set(1,11);
System.out.println(l);
l.set(1,2);
//删除指定元素(如果是int型的一定要标明数据类型为Integer),只删除第一个找到的
System.out.println(l);
l.remove((Integer) 2);
System.out.println(l);
//删除指定位置元素(传入的值应该标名为(int)类型)
l.remove(2);
System.out.println(l);
//获取子List,index范围同样左包右不包
System.out.println(l.subList(1,3));
//获取list长度
System.out.println(l.size());
//获取指定元素的index,没有时返回-1
l.indexOf(3);
//判断list是否为空
l.isEmpty()

ArrayList排序：

//升序排序
Collections.sort(l);
//降序排序
Collections.sort(l,Collections.reverseOrder());
//自定义类型重写Comparator接口中的compare方法 
Collections.sort(l, new Comparator<people>() {
   @Override
   public int compare(people o1, people o2) {
          return Integer.compare(o1.age, o2.age);
   }
});

HashSet

HashSet不能添加重复的元素，当调用add（Object）方法时候，首先会调用Object的hashCode方法判hashCode是否已经存在，如不存在则直接插入元素； 如果已存在则调用Object对象的equals方法判断是否返回true， 如果为true则说明元素已经存在，如为false则插入元素。

先来看看基本数据类型的HashSet实现：

HashSet<Integer> hs = new HashSet<>();
//添加元素
hs.add(1);
hs.add(2);
hs.add(3);
hs.add(3);
//hs: [1,2,3]，顺序随机
System.out.println(hs);
//是否存在某元素
System.out.println(hs.contains(3));
//删除元素
hs.remove(2);
System.out.println(hs);
//获取set大小
System.out.println(hs.size());
//两种遍历的方式
for(int xx:hs){
    System.out.println(xx);
}
Iterator it = hs.iterator();
while (it.hasNext()){
   	System.out.println(it.next());
}

对于自定义数据类型的HashSet，需要在类中重写hashCode方法和equals方法，用以判断传入集合的元素是否已经存在。

class people{
    public int age;
    public String name;
    people(int age,String name) {
        this.age = age;
        this.name = name;
    }
    @Override
    public int hashCode(){
        return this.name.hashCode();
    }
    @Override
    public boolean equals(Object obj){
        if(this == obj)
            return true;
        if(obj!=null && obj instanceof people){
            people p1 = (people) obj;
            if(this.name.equals(p1.name)){
                return true;
            }
        }
        return false;
    }
}

HashMap

存储键值对采用HashMap实现，具体的方法如下：

HashMap<Integer,String> hm = new HashMap<>();
//添加元素
hm.put(1,"aa");
hm.put(2,"bb");
hm.put(3,"aa");
//判断是否存在键或值
System.out.println(hm.containsKey(4));
System.out.println(hm.containsValue("aa"));
System.out.println(hm);
//{1=aa, 2=bb, 3=aa}
//采用put方法如果已存在键会覆盖
hm.put(3,"bb");
System.out.println(hm);
//{1=aa, 2=bb, 3=bb}
//不想覆盖可采用以下方法
hm.putIfAbsent(3,"aa");
System.out.println(hm);
//{1=aa, 2=bb, 3=bb}
//获取键对应的值
System.out.println(hm.get(3));
//删除给出键的键值对
hm.remove(3);
System.out.println(hm);
//更新键值对
hm.replace(2,"cc");
System.out.println(hm);
//获取键的集合
Set<Integer> ks = hm.keySet();
System.out.println(ks);
//第一种遍历的方法，获取键的Set，构造迭代器
Iterator it = ks.iterator();
while(it.hasNext()){
    int i = (int)it.next();
    System.out.println(hm.get(i));
}
//第二种遍历的方法，获取键值对的entry集合，获取各entry的键与值
Iterator it1 = hm.entrySet().iterator();
while(it1.hasNext()){
    Map.Entry entry = (Map.Entry) it1.next();
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}

Java队列与栈

栈

java中的栈是Vector的一个子类，它实现了一个标准的后进先出的栈

//栈的定义
Stack<Integer> s = new Stack<>();
//入栈
s.push(1);
s.push(2);
//获取栈顶元素,但不出栈
peek = s.peek();
//弹出栈顶元素，出栈
peek = s.pop();
//判断栈是否为空
System.out.println(s.isEmpty());
//获取栈中元素的个数
System.out.println(s.size());
//栈中的其他元素可以通过get方法使用下标访问
System.out.println(s.get(0));

队列

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

//对列的定义
Queue<Integer> q = new LinkedList<>();
//向队列中添加元素
q.offer(1);
q.offer(2);
q.offer(4);
//获得队首元素，但不出队
int first = q.element();
//获得队首元素，出队
first = q.poll();
//判读队列是否为空
System.out.println(q.isEmpty());
//获取队列中元素的个数
System.out.println(q.size());

优先队列

PriorityQueue是一种基于优先级堆的优先级队列。如果不提供Comparator的话，优先队列中元素默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字典序排列，也可以根据 Comparator 来指定，这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）

//定义优先队列，指定队列初始大小(可选)，并自定义排序顺序(可选)，这个例子中是按照降序排序
Queue<Integer> qq = new PriorityQueue<>(3, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
});
//向队列中添加元素
qq.offer(3);
qq.offer(4);
qq.offer(2);
qq.offer(1);
//[4, 3, 2, 1]
System.out.println(qq);
//4
System.out.println(qq.element());
//4,但队首出队
System.out.println(qq.poll());
qq.offer(5);
//[5, 3, 2, 1]
System.out.println(qq);

Java比较器

Comparable接口

如果一个类中已经实现了Comparable接口，可以直接使用java.util.Arrays类，Collections类，优先队列等进行数组的排序操作。

Comparable接口的定义如下：

public interface Comparable<T>{
	public int compareTo(T o);
}
/*
此方法返回一个int类型的数据，但是此int的值只能是一下三种：
1：表示大于
-1：表示小于
0：表示相等
*/

给出一个具体的例子:

class people implements Comparable<people>{
    public int age;
    @Override
    public int compareTo(people a1) {
        if(this.age<a1.age){
            return -1;
        }
        else if(this.age>a1.age){
            return 1;
        }
        return 0;
    }
    people(int age){
        this.age = age;
    }
}

在此例子中，我们可以根据age来定义people的大小关系，比如如果a的age小于a1的age，则定义people a小于people a1(在返回值上反应为-1)。

如果建立people的优先队列，则优先队列的内部情况如下：

people a = new people(1);
people b = new people(2);
Queue<people> qqq = new PriorityQueue<>();
qqq.offer(b);
qqq.offer(a);
//qqq:[a,b]

Comparator接口

如果一个类已经开发完成，但是在此类建立的初期并没有实现Comparable接口，此时肯定是无法进行对象排序操作的，所以为了解决这一的问题，java又定义了另一个比较器的操作接口 Comparator 此接口定义在java.util包中，它的定义为：

public interface Comparator<T>{
	public int compare(T o1，T o2);
    /*
	此方法返回一个int类型的数据，但是此int的值只能是一下三种：
	1：表示o1大于o2
	-1：表示o1小于o2
	0：表示相等
	*/
    boolean equals(Object obj);
}

Java字符串

String

字符串常量池

String类是我们平常项目中使用频率非常高的一种对象类型，jvm为了提升性能和减少内存开销，避免字符的重复创建，其维护了一块特殊的内存空间，即字符串池，当需要使用字符串时，先去字符串池中查看该字符串是否已经存在，如果存在，则可以直接使用，如果不存在，初始化，并将该字符串放入字符创常量池中。

基本操作

String类中使用字符数组保存字符串，因为有“final”修饰符，所以可以知道string对象是不可变的。可选的创建方式有直接赋值和new两种方式

使用String直接赋值：
String str = “abc”;可能创建一个或者不创建对象，如果”abc”在字符串池中不存在，会在java字符串池中创建一个String对象（”abc”），然后str指向这个内存地址，无论以后用这种方式创建多少个值为”abc”的字符串对象，始终只有一个内存地址被分配。==判断的是对象的内存地址，而equals判断的是对象内容。通过以下代码测试：

String str = "abc";
String str1 = "abc";
String str2 = "abc";
System.out.println(str==str1);//true
System.out.println(str==str2);//true
String str = "abc";//在常量池中创建abc
String str1 = "abcd";//在常量池中创建abcd
String str2 = str+"d";//拼接字符串，此时会在堆中新建一个abcd的对象，因为str2编译之前是未知的
String str3 = "abc"+"d";//拼接之后str3还是abcd，所以还是会指向字符串常量池的内存地址
System.out.println(str1==str2);//false
System.out.println(str1==str3);//true
System.out.println(str3==str2);//false

使用new String 创建字符串:

String str2 = new String(“ABC”);至少创建一个对象，也可能两个。因为用到new关键字，肯定会在heap中创建一个str2的String对象，它的value是“ABC”。同时如果这个字符串再java String池里不存在，会在java池里创建这个String对象“ABC”。

String str = new String("abc");
String str1 = new String("abc");
String str2 = new String("abc");
System.out.println(str==str1);//false
System.out.println(str==str2);//false
System.out.println(str1==str2);//false

建议在平时的使用中，尽量使用String = “abcd”;这种方式来创建字符串，而不是String = new String(“abcd”);这种形式，因为使用new构造器创建字符串对象一定会开辟一个新的heap空间，而双引号则是采用了String interning(字符串驻留)进行了优化，效率比构造器高。

与其他类型的转换

String转基本数据类型：一般可以直接调用各数据类型包装类的方法：

String x = "123";
int i = Integer.parseInt(x);
float j = Float.parseFloat(x);

基本数据类型转String：一般也可以直接调用各数据类型包装类的方法：

int i = 1;
String x = Integer.toString(i);
String y = String.valueOf(i);
//第二种更安全，可以处理null值

其他常用方法

String test = "123xyz";
//获取字符串长度
int length = test.length();
//转化成char型数组
char[] mystr = test.toCharArray();
//获得指定字符的第一次出现的位置
System.out.println(test.indexOf('3'));
//获取子字符串，左包右不包
String newstr = test.substring(0,3);
System.out.println(newstr);
//替代所有指定字符，返回替代后的新字符串用I换1
System.out.println(newstr.replace('1','I'));
//根据正则表达式替换所有匹配的字符串，用45替换23
newstr = newstr.replaceAll("23","45");
System.out.println(newstr);

StringBuffer

使用StringBuffer的目的在于String的内容不可更改，而它可以。

//新建StringBuffer类
StringBuffer sb = new StringBuffer("123xyz");
//StringBuffer与String的转换
System.out.println(sb.toString());
//在字符串末尾添加字符
sb.append("456");
System.out.println(sb.toString());
//获取字符串的长度
System.out.println(sb.length());
//在指定index后插入字符(“uvw123xyz456”)
sb.insert(0,"uvw");
System.out.println(sb.toString());
//替换(这里替换为空就是删除)指定index间的字符(左包右不包，这里删除了w(index = 2))
sb.replace(2,3,"");
System.out.println(sb.toString());

类似于StringBuffer的还有StringBuilder。 在字符缓冲区被单个线程使用时优先考虑使用StringBuilder()，效率更高。但StringBuffer对于多线程是安全的。