A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 blovedr 于 2018-11-15 10:39 编辑

2018.11.13  9:29   day03
1.2 02 数据结构  栈
   数据结构_栈  先进后出
        入口和出口在同一侧
1.3 数据结构  队列
    数据结构_队列   先进先出
        入口和出口在集合的两侧

李推荐书: 《深入理解java虚拟机》   ---2018.11.13
    推荐重点看:内存模型  算法   类加载器   高并
1.4数据结构  数组
数据结构_数组
    查询快  数组地址是连续的,通过数组首地址可以找到数组, 通过数组索引可以快速查找到某一个元素
    增删慢   数组长度是固定的,要增/删数组一个元素, 必须创建一个新的数组,把数组元素复制过来
1.5数据结构  链表【参见视频】
1.6数据结构  红黑树
    二叉树: 分支不能超过两个
排序树/查找树     猜数字小游戏:1-100之间的数字,从50开始猜,一下减一半
    在二叉树的基础上, 元素是有大小顺序的
    左子树小, 右子树大
    平衡树: 左孩子和右孩子相等
    不平衡树: 左孩子!= 右孩子
红黑树
    特点: 趋近于平衡树, 查询速度非常快, 查询叶子节点最大次数和最小次数不能超过2倍。
      约束:
1.  节点可以是红色或者黑色的
2.  根节点是黑色的
3.  叶子节点(空节点)是黑色的
4.  每个红色节点的子节点都是黑色的
5.  任何一个节点到每一个叶子节点的所有路径上黑色节点数相同。
3.2  LinkedList集合(类)
     java.util. LinkedList集合 implements List接口
     LinkedList集合特点:
1.  底层是一个链表结构:查询慢, 增删快
2.  里面包含了大量操作首尾元素的方法
注意:使用LinkedList集合特有的方法, 不能使用多态
-         publicvoid addFirst(E e): 将指定元素插入此列表的开头
-         publicvoidaddLast(E e) 将指定元素添加到此列表的结尾。
-         publicvoidpush(E e) 将元素推入此列表所表示的堆栈。 相当于addFirst(E e)
-         
-         publicE getFirst() 返回此列表的第一个元素。
-         publicEgetLast() 返回此列表的最后一个元素。
-         publicE removeFirst() 移除并返回此列表的第一个元素。
-         publicEremoveLast() 移除并返回此列表的第一个元素。
-         publicE pop() 从此列表所表示的堆栈处弹出一个元素 相当于removeFirst()
-         publicboolean isEmpty(): 如果列表不包含元素, 则返回true

3.1  Set集合(接口)
Java.util.Set接口 extendsCollection接口
Set接口特点:
1.  不允许存储重复的元素
2.  没有索引, 没有带索引的方法, 也不能使用普通的for循环遍历
Java.util.HashSet集合 implements Set 接口
HashSet特点;
1.  不允许存储重复的元素
2.  没有索引, 没有带索引的方法, 也不能使用普通的for循环遍历
3.  是一个无序的集合, 存储元素和取出元素的顺序有可能不一致
4.  底层是以哈希表结构(查询的速度非常的快)
哈希值:是一个十进制的整数,有系统随机给出(就是对象的地址值, 是一个逻辑地址, 是模拟出来得到地址, 不是数据实际存储的物理地址)
在Object类有一个方法, 可以获得对象的哈希值
Int hashCode() 返回该对象的哈希码值
hashCode方法源码:
    public native inthashCode();
    native:代表该方法调用的是本底操作系统的方法
        String类(字符串类)的哈希值
             String类重写Object了的HashCode方法
第五章  Collections类【参考视频】   2018.11.13 17:05
   
注意:
    Sort(list<T>list)使用前提
    重写排序的规则   
return 0; // 认为元素都是相同的

Comparable接口的排序规则:
    自己(this)- 参数:升序
比较此对象与指定对象的顺序
如果返回负数,代表this小于指定对象(传进来的对象)  
如果返回0,代表this等于指定对象(传进来的对象)
如果返回正整数,代表this大于指定对象(传进来的对象)
    默认是升序,如果把规则反过来, 则变成了降序
数据结构: (李)
栈:
特点:
1. 只能在一端进行元素的添加和删除
2.  先进后出(*)
队列:
特点:
1. 先进先出(*)
2.  入口和出口分别在两侧
数组:
特点:ArrayList底层是数组的实现
1. 增删慢(长度不可变)
2.  查询快(元素有对应的索引,是一片连续的内存空间)
      
链表:
特点:
1. 增删快(增删元素不会改变原有内容)
2. 查询慢(只能通过前一个元素找到下一个元素)
        链表结构:
            每个元素都是一个对象, 对象中包含的元素数据,指针
            每个元素之间, 通过指针相连
           单向链表:
               特点:
1. 增删快
2. 查询慢
           双向链表:
               特点:
相比于单向链表: 查询稍微快一点
红黑树:
特点:
            查询快
        名词解释:
            二叉树:分支不超过两个
查找树/排序树:是一个有序的二叉树(左子树小于节点, 右子树大于节点) 左中右, 则是从小到大排列
            平衡树:左右子树高等差不超过1
            红黑树:趋近于平衡树, 查询速度非常快
            
Java.util.List
概述:
是Collection下的一个子接口,在List接口下的集合有以下特点:
1. 有序(有序列)
2. 有索引
3. 允许重复
       List中的特有功能(和索引相关的增删改查的功能)
            void add(int index, E element): 指定索引位置添加元素
            E remove(int index): 删除指定索引位置元素, 把被删除的元素返回
            E set(int index, E element): 修改指定索引位置的元素为指定值,把被修改的元素返回
            E get(int index):获取指定索引位置的元素
            // 需求:
1.  添加五个英文字符串到集合中
2.  在第三个位置插入一个新字符串
3.  将索引为奇数的字符串转为大写
4.  分别使用迭代器和增强for循环遍历集合
       ArrayList:底层实现的数组(查询快, 增删慢)
       LinkedList:底层实现的列表(查询慢, 增删快)
           特有功能:
               针对于链表的首尾位置元素的操作:
               E getFirst()
             E getLast()
            
               E removeFirst()
               E removeLast()
               addFirst(E e)
               addLast(E e)
               
               可以模拟栈和队列
               当对集合中元素增删操作比较多的时候, 推荐使用LinkedList
当对集合中元素查询操作比较多的时候,推荐使用ArrayList
     Vector:
          和ArrayList实现功能是一致的(底层也是数组的实现)
          唯一区别:
              ArrayList是不同步的*(效率高,安全性低)
              Vector是同步的(效率低, 安全性高)
     ArrayList把Vector取代了,唯一区别是Vector是同步
    Java.util.Set:
          特点:
1. 无序(不保证存取的顺序)
2. 无索引
3. 不允许重复元素

         
数组:当知道元素索引, 查询很快。 但是如果不知道索引, 只能从头到尾去遍历
       Hast表: 看到元素可以直接知道lisi 这个元素的位置。
        HashSet:
            底层是hash表的实现,查询的效率非常高
            哈希值:
默认情况: 根据对象的物理地址算出来的整数, 一般我们调用hashCode可以获得Hash值
              我们实现代码的时候: 我们可以重写hashCode方法去影响对象的hash值
              当我们用HashSet存储自动以对象的时候, 如果想保证元素的唯一性,则需要重写hashCode和equals方法
/*
       哈希表:
           本质: 数组(存储了链表的数组), 数组中的元素是一个个链表
           存储元素;
               先将元素获取其hash值,再通过hash表的长度来确定元素的索引位置
           种地    通话    9999(计算元素hash值)   4(确定元素索引位置)
          元素的获取:
               Heihei 根据之前的算法可以得知其位置在0索引, 拿到索引号, 直接就能获取heihei元素
         当存储的元素过多, 如果容量没有发生变化, 则链表长度会越来越长, 导致查询的速度变慢,JDK8后, 则会将链表长度大于8的转化为红黑树, 让查询效率会更高。
            HashSet存储原理:
                通过hashCode方法确定索引位置
                再通过equals方法去除重复元素
            // 问题:没有办法去重复
           // 解决方案: 重写hashCode方法,让hashCode放回值和地址值不相干, 跟属性相关
1.  首先通过元素hashCode方法获取哈希值, 计算出元素在哈希表中的位置
2.  如果对应位置已经有元素了, 通过equals比较元素的内容
则比较equals的返回值,
如果是true, 则认为元素重复不添加
如果是false, 则认为元素不重复, 则添加元素。

            总结:
                 存储元素的操作:
1.  先获取对象的hash值去存储元素
1.1hash值不一样, 直接存储
1.2hash值一样
则比较equals的返回值,
如果是true,则认为元素重复不添加
如果是false,则认为元素不重复, 则添加元素。
                当我们用HashSet存储自动以对象的时候, 如果想保证元素的唯一性, 则需要重写hashCode和equals方法
                        使用HashSet存储自定义对象, 其中有两个元素属性值一样, 先不重写hashCode和equals方法, 再重写之后再输出
*/
LinkedHashSet: 本质就是一个有序的HashSet:  hast表+链表
    Hash表用于存储
链表用于记录元素存储的顺序, 当我们获取元素的时候, 则会通过链表记录的顺序去获取元素
可变参数:
一种特殊的参数类型: 可以接收任意多个同种数据类型的数据:0个,1个,多个,
     格式:
           数据类型… 参数名
     原理:
          将传递的任意多个元素, 封装到一个数组中, 最好在传递给可变参数。
    // 定义方法,求任意多个元素的和,并返回
Comparable接口的排序规则:
    自己(this)- 参数:升序
比较此对象与指定对象的顺序
如果返回负数,代表this小于指定对象(传进来的对象)  
如果返回0,代表this等于指定对象(传进来的对象)
如果返回正整数,代表this大于指定对象(传进来的对象)
    默认是升序,如果把规则反过来, 则变成了降序
    // 定义一个ArrayList集合, 存储四个自定义对象, 用Collections.sort进行排序,按照年龄排序
结论:
升序: this – o…
降序: o – this…
1. Comparator比较器对象

2. Comparable让对象所在的类去实现,实现后,则可以使用sort方法实现对元素的排序
在调用Collections.sort方法的时候, 除了传递被排序的集合, 还传递以比较器实现类对象
// 需求: 分别用两种方式实现对集合元素的排序

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马