栈结构和队列结构
栈：
先进后出。
队列：
先进先出。
6.数组和链表
数组：
在内存中是一片连续的空间。
查询快，增删慢。
查询快：因为可以通过数组的地址值和索引直接定位到某个元素。
增删慢：因为数组不可变，每次要添加或者删除都要创建一个新的数组。
把老数组中的元素赋值给新数组。
链表：
是多个节点组成的。
每一个节点都是单独new出来的对象，在内存中链表不是一个连续的空间。
是通过互相记录地址值实现的。
单向链表：
前一个记录后一个地址值。
但是后一个不会记录前一个地址值。
双向链表
也是由节点组成的。
前一个记录后一个地址值。
后一个也会记录前一个。
7.ArrayList 和 LinkedList
ArrayList ： 底层是一个数组。
特点：查询快，增删慢
LinkedList ： 底层是一个双向链表。
特点：查询慢，增删快
总结：
ArrayList 和 LinkedList 基本使用是一模一样的。
增 删 改 查，所写代码几乎一样。
但是在底层数据结构是不一样的。
8.LinkedList
void addFirst(E e) 向集合中第一个位置添加元素
void addLast(E e) 向集合中最后一个位置添加元素
E getFirst() 获取集合中第一个元素
E getLast() 获取集合中最后一个元素
E removeFirst() 删除集合中第一个元素
E removeLast() 删除集合中最后一个元素
目前为止：
List集合已经全部学习完毕了
ArrayList ：此时查询较多
LinkedList ：此时增删较多
Vector 是List中最为古老的一个集合在JDK1.0的时候就出现了。
在JDK1.2的时候Java提出了集合理论。
把ArrayList全面替代了Vector
疑问：
我也不知道增删多还是查询多怎么办？
当你不知道用什么的时候，请使用: ArrayList
9.单列集合的第二分支 Set
List： 有序 有索引 可以重复
Set ： 无序 无索引 不可以重复
注意点：
当你使用到Set的时候，就不要想着他存取有序了。
10.哈希值
问:
1.什么是哈希值？
其实就是根据"地址值"或者内部"元素的属性值"计算出来的一个数值。
2.什么时候根据地址值计算？
Object 中的hashCode 返回的就是根据地址值计算出来的哈希值。
3.什么时候根据元素的属性值计算？
在任意一个已经将hashCode进行重写之后。
只要重写了，就按照元素的属性值进行计算,此时跟地址值就没有任何关系了。比如： String Integer Character...
4.如果属性值不同，那么哈希值有可能相同吗？
有可能，几率比较低。
哈希值是一个int类型 -21亿 ~ 21亿 一共有42亿多的值。
那么现在我创建了50亿个对象分别调用他的hashCode方法。
其中至少8亿左右的对象哈希值是重复的。
作用：
一般不单独使用。
跟 HashSet ， LinkedHashSet ， HashMap 这三个集合有关。
11.HashSet集合保证元素唯一性源码分析
得出一个结论：
HashSet集合保证唯一性是依赖两个方法：
hashCode和equlas
12.HashSet的底层分析：
a.HashSet底层其实依赖的是HashMap集合的键位置。
每次在存储的时候，元素放到键位置，值就是一个 new Object();
b.哈希表
其实HashSet LinkedHashSet HashMap 这三个集合中底层一个数据结构。
哈希表其实就是一个数组跟链表的结合体
到了JDK1.8 哈希表 = 数组 + 链表 + 二叉树
总结：
HashSet LinkedHashSet HashMap的键
在存储元素的时候，这个类里面一定要重写hashCode和equals方法。
String Integer ...Java中已经提供的这些类已经帮我们重写好了这两个方法。
"当我们要在这些集合中存储自定义对象时，要重写hashCode和equals方法。"
13.LinkedHashSet
特点：
有序 + 不可以重复
ArrayList
//当实在不知道用什么的时候。
//查询多，增删少。
LinkedList
//查询少，增删多。
Vector//肯定不用
HashSet
//数据需要去重时
LinkedHashSet
//数据需求去重且存取有序。
练习1：
键盘录入3个不重复的字符串？
HashSet<String> hs = new HashSet();
Scanner sc = new Scanner(System.in);
while(true){
if(hs.size == 3){
break;
}else{
String line = sc.nextLine();
hs.add(line);//如果已经有了，此时就存储失败
//如果没有，才能存到集合中。
}
}
练习2：
让多个数据进行整体去重
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("a");
list.add("a");
list.add("a");
list.add("a");
list.add("a");
list.add("a");
list.add("a");
//去重里面重复的元素
HashSet<String> hs = new HashSet();
hs.addAll(list);//把list集合中所有的元素添加到hs里面
System.out.println(hs);//此时就已经是去重之后的结果了。
14.TreeSet
误区：
哈希表，哈希值只跟 HashSet LinkedHashSet HashMap的键有关
TreeSet 跟哈希值，哈希表，hashCode方法，equals方法都是无关的。
特点：
可以排序。//我们得给他指定一个排序的规则，如果没有这样的规则，会报错的。
TreeSet<String> ts = new TreeSet<>(); //采取的是默认方式进行比较。
TreeSet<String> ts = new TreeSet<>(比较的规则);//采取传递的规则进行比较。
底层结构：
二叉树结构
15.TreeSet的默认比较方式。
自然排序。
案例：
TreeSet<Student> ts = new TreeSet<>();
//现在要存谁，this就表示谁。
//现在要跟谁比较，o就表示谁。
ts.add(new Student("zhangsan",23,"男"));
ts.add(new Student("lisi",24,"男"));
ts.add(new Student("wangwu",25,"女"));
System.out.println(ts);
注意点， Student类要实现接口Comparable
@Override
public int compareTo(Student o) {
System.out.println(this);
//按照年龄从大到小，年龄相同就不要。
int result = o.age - this.age;
return result;
}
16.比较器排序Comparator
代码的书写方式跟第一种基本是一样。
注意点：
1.当第一种和第二种同时存在时，听第二种的。
2.第二种方式什么时候用？
当我们不知道用哪一种的时候我们使用第一种方式。
当第一种无法满足的时候，会使用第二种。
练习1：
我要按照字符串的长度排序？
默认使用自然排序，但是自然排序的规则是:字典顺序。
因为String是Java提供的，我们无法修改源代码的。
在这种情况下：第一种自然排序就无法满足我现在的要求了。
所以此时用第二种。
总结：
如果Java提供好的类中排序方式不能满足现在的要求，用第二种。
自定义类可以使用第一种。
TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//o1 现在要存入的元素
//o2 已经存在的元素
//o1和o2所表示的含义不重要，最多就是运行完毕后，修改一下前后顺序就可以了
//重点就是比较规则的书写。
return o2.length() - o1.length();
}
});
ts.add("b");
ts.add("aaa");
ts.add("aa");
ts.add("aaaaa");
ts.add("aaaa");
System.out.println(ts);
练习2：
我要按照字符串的长度排序？如果长度一样，请按照字典顺序排？
TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
int temp = o1.length() - o2.length();
temp = temp == 0 ? o1.compareTo(o2) : temp;
return temp;
}
});
ts.add("b");
ts.add("aaa");
ts.add("aa");
ts.add("aaaaa");
ts.add("aaaa");
ts.add("a");
System.out.println(ts);
}
|
|
收藏
淘帖
踩
