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方法的时候， 除了传递被排序的集合， 还传递以比较器实现类对象

// 需求： 分别用两种方式实现对集合元素的排序

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方法的时候， 除了传递被排序的集合， 还传递以比较器实现类对象

// 需求： 分别用两种方式实现对集合元素的排序