数据结构和对应的集合【黑马java培训】

更新时间:2019年07月26日 10时48分54秒来源:黑马程序员论坛

栈结构和队列结构
栈：
先进后出。

队列：
先进先出。

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);

}

推荐了解热门学科

java培训	Python人工智能	Web前端培训	PHP培训
区块链培训	影视制作培训	C++培训	产品经理培训
UI设计培训	新媒体培训	产品经理培训	Linux运维
大数据培训	智能机器人软件开发

传智播客是一家致力于培养高素质软件开发人才的科技公司，“黑马程序员”是传智播客旗下高端IT教育品牌。自“黑马程序员”成立以来，教学研发团队一直致力于打造精品课程资源，不断在产、学、研3个层面创新自己的执教理念与教学方针，并集中“黑马程序员”的优势力量，针对性地出版了计算机系列教材50多册，制作教学视频数+套，发表各类技术文章数百篇。

传智播客从未停止思考

传智播客副总裁毕向东在2019IT培训行业变革大会提到，“传智播客意识到企业的用人需求已经从初级程序员升级到中高级程序员，具备多领域、多行业项目经验的人才成为企业用人的首选。”

中级程序员和初级程序员的差别在哪里?
项目经验。毕向东表示，“中级程序员和初级程序员最大的差别在于中级程序员比初级程序员多了三四年的工作经验，从而多出了更多的项目经验。“为此，传智播客研究院引进曾在知名IT企业如阿里、IBM就职的高级技术专家，集中研发面向中高级程序员的课程，用以满足企业用人需求，尽快补全IT行业所需的人才缺口。

何为中高级程序员课程?

传智播客进行了定义。中高级程序员课程，是在当前主流的初级程序员课程的基础上，增加多领域多行业的含金量项目，从技术的广度和深度上进行拓展。“我们希望用5年的时间，打造上百个高含金量的项目，覆盖主流的32个行业。”传智播客课程研发总监于洋表示。

黑马程序员热门视频教程【点击播放】

Python入门教程完整版（懂中文就能学会）	零起点打开Java世界的大门
C++\| 匠心之作从0到1入门学编程	PHP\|零基础入门开发者编程核心技术
Web前端入门教程_Web前端html+css+JavaScript	软件测试入门到精通

全国中心

数据结构和对应的集合【黑马java培训】

相关阅读