java第五部分 集合进阶

目录一、集合1.1 集合的分类1.2 单列集合1.2.1 单列集合的体系结构1.2.2 单列集合的顶层接口 Collection1.2.2.1 Collection 常用方法这几个其实都是抽象方法最底层子类自己实现的1对于 add 方法2对于 contains 方法1.2.2.2 Collection 遍历方式1迭代器遍历依赖指针移动实现2增强 for 遍历3Lambda 表达式遍历4三种遍历方式的使用场景1.2.3 单列集合中的 List 分支​编辑1.2.3.1 List 集合的特有方法1关于 remove 的小细节1.2.3.2 List 集合的特有遍历方式在之前三种的基础上加上第二条和第五条1普通 for 循环2列表迭代器3五种迭代方式的选择1.2.3.3 ArrayList 源码还没看用到补对应集合进阶 061.2.3.4 LinkedList1特点2特有方法但是很少使用一般直接用 Collection 和 List 里的方法即可源码还没看后面补对应集合进阶 071.2.4 单列集合中的 Set 分支源码还没看对应集合进阶的13-181.2.4.1 HashSet1哈希值2哈希表3HashSet 存取顺序不一致的原因4HashSet 去重原理5小细节下面两条不太严谨1.2.4.2 LinkedHashSet效率比 HashSet 低1.2.4.3 TreeSet1特点2对于 Java 已有类型的排序结果规律3TreeSet 添加的底层原理4一些思考1.2.5 单列集合的使用场景1.3 双列集合后面习题没看如果有用可以补上1.3.1 双列集合的体系结构1.3.2 单列集合顶层接口map1.3.2.1 map常用方法1.3.2.2 map集合的遍历方法1键找值2键值对3lambda表达式1.3.3 hashmap没有特殊要求时map系列中优先使用hashmap1.3.4 linkedhashmap1.3.5 treemap1.3.6 一些思考1.3.7 map在计数中的应用1.4 不可变集合二、泛型2.1 概念2.1.1 如果没有泛型2.1.2 泛型的小细节1Java 中的泛型是伪泛型只在编译时有效即使在 Java 文件中写了泛型在编译后翻译仍然会消失这叫做泛型的擦除。2即使使用了泛型那将数据存储进集合后依然会被当作 Object 类型只不过在取数据时会自动转换为原类型。3它可以规定集合里存储数据的类型在编译时期检查你往集合里存的数据类型是否合法。不合法则编译报错。2.2 泛型的用途2.2.1 泛型类2.2.2 泛型方法2.2.3 泛型接口1定义格式2使用方法方法一实例方法二实例2.3 泛型的继承和通配符1泛型不具备继承性例子如下函数中定义了一个形参 ArrayList 此时只能传递泛型为 Ye 的 ArrayList不能传递泛型为 Ye 的子类的 ArrayList。2泛型的通配符同样用于中三、数据结构3.1 树二叉树、二叉排序树和平衡二叉树都满足3.2 二叉树1定义2遍历方式3.3 二叉查找树1定义2插入与查找3中序遍历二叉查找树时结果序列是从小到大排列的3.4 平衡二叉树1出现原因2定义3插入节点与维持平衡的方式四、其他知识点4.1可变参数一、集合注意集合特点1集合长度可以动态变化添加元素长度增加删除元素长度减少长度和元素个数一致2只能存引用数据类型要存整数等要存其对应的包装类1.1 集合的分类集合可以分为单列集合每次添加一个元素和双列集合每次添加一对元素。1.2 单列集合1.2.1 单列集合的体系结构List 系列集合的有序特性是指存取顺序是一致的存 1, 2, 3取就是 1, 2, 3。1.2.2 单列集合的顶层接口 Collection1.2.2.1 Collection 常用方法这几个其实都是抽象方法最底层子类自己实现的1对于 add 方法2对于 contains 方法比如list.contains(a)内部会调用indexOf方法再内部会调用indexOfRange方法这两个方法的发起者依然是 list在indexOfRange中会使用字符串 a 的equals方法去和 list 的每个元素进行比较是否相等如果有则返回索引。由上述即可得到以下结论equals方法定义在object类中1.2.2.2 Collection 遍历方式这几个是 Collection 系列集合通用的遍历方式没有写 for 循环是因为 Set 分支下的集合没有索引。1迭代器遍历依赖指针移动实现通用代码如下小细节迭代器指针是不会重新指向集合中第一个元素的只能重新获取迭代器对象。遍历时不能用集合的方式进行集合元素添加或删除以下写法会报错删除的话用迭代器提供的方法代替添加的话目前没有办法红线部分改为it.remove()即可进行删除这是迭代器里的方法不会报错。2增强 for 遍历增强 for 的原理就是迭代器只不过书写更简单。3Lambda 表达式遍历forEach本来是要传入 Consumer 接口的实现类对象但是可以传入匿名内部类并简化为 Lambda 表达式。forEach内部其实就是以增强for的方式遍历集合的每个元素交给accept函数处理。4三种遍历方式的使用场景1.2.3 单列集合中的 List 分支三种集合都符合1.2.3.1 List 集合的特有方法1关于 remove 的小细节由于 List 接口中有两个 remove一个来自 Collection一个是自定义的那 remove 传入的参数是哪个类型就调用哪个方法。1.2.3.2 List 集合的特有遍历方式在之前三种的基础上加上第二条和第五条1普通 for 循环2列表迭代器相比于普通迭代器它可以在遍历的过程中添加元素普通迭代器只能删除。下面这种方式是在 bbb 后面添加 qqq3五种迭代方式的选择1.2.3.3 ArrayList 源码还没看用到补对应集合进阶 061.2.3.4 LinkedList1特点2特有方法但是很少使用一般直接用 Collection 和 List 里的方法即可源码还没看后面补对应集合进阶 071.2.4 单列集合中的 Set 分支源码还没看对应集合进阶的13-181.2.4.1 HashSet1哈希值2哈希表存储位置计算方法是把两个数转为二进制按位与具体添加元素的方式第六点当链表长度大于8且数组长度大于等于64时链表会自动变为红黑树jdk8及以后对于第二点就是先获取对象的哈希值再按照上面的公式计算应当存入的位置对于第四点位置部位null时会使用equals方法将要添加的元素和该位置的所有元素进行表如果均不相同再添加对于扩容当数组存入的元素个数达到16*0.75也就是12时会扩容到32小注意点如果不重写他们是针对地址值的应当重写让他们针对属性值3HashSet 存取顺序不一致的原因hashset遍历时是从哈希表的0索引开始碰到元素就取出来4HashSet 去重原理存储自定义对象时重写hashcode和equals方法后相同对象的hashcode得到的哈希值相同插入数组的位置也就相同插入时通过equals判断结尾为相同因此不插入5小细节下面两条不太严谨不重写hashcode时两个对象的哈希值可能相同也可能不相同按照idea方法重写hashcode时那两个对象属性相同他们的哈希值一定相同equals默认比较的是两个对象的地址值。重写后idea默认方式比较的是属性值1.2.4.2 LinkedHashSet效率比 HashSet 低linkedhashset相比于hashset多了一个双向链表按照添加顺序把每个元素连起来遍历linkedhashset时按照链表遍历就可以做到存取顺序一致1.2.4.3 TreeSet1特点2对于 Java 已有类型的排序结果规律对于字符串来说是一个字符一个字符的比较能确定大小是就不看后面了空是比有字符要小的3TreeSet 添加的底层原理往treeset里添加元素逻辑上其实就是在构建一颗红黑树添加元素时严格按照之前学的红黑树规则他会通过本元素调用compareto方法或者调用compare方法和路径上的元素不断比这两个方法的比较逻辑根据当时的规则来确定大则返回正数小则负数相等则0看要添加的原始是大还是小找到合适的位置存入后续可能涉及到红黑调整。这也就引出了treeset比较方式的两种实现方法对于这两种方法的返回值要求要添加的元素小则返回负数大则返回正数相同则0.大小根据当时制定的比较规则来确定方式一通过实现comparable方法重写compareto方法实现比较逻辑comparable接口只有一个compareto方法泛型就是这个方法要传入的参数类型其实就是添加元素的类型方式二对于第二种排序方式当一个类已经实现了compareto方法但是不符合我们的要求这时就可以用o1指的是要插入的元素例子如下4一些思考先人为规定“什么算小、什么算大”然后用compare/compareTo把这个规则实现出来TreeSet最终就会按照这套规则从“小”到“大”排列。1.2.5 单列集合的使用场景优先使用arraylist和hashset就行1.3 双列集合后面习题没看如果有用可以补上1.3.1 双列集合的体系结构添加元素时每次添加一个键值对也叫键值对对象entry对象键不能重复1.3.2 单列集合顶层接口map1.3.2.1 map常用方法1.3.2.2 map集合的遍历方法1键找值就是先把map的所有键放到set集合里面然后遍历set拿到所有键遍历方式可以在set系列的三种遍历方式中选用键到map里拿值2键值对注意既然map中的键值对对象以set集合的方式返回拿set的泛型该怎么写呢泛型也就是集合里所装元素的类型也就是Entry但Entry本身自带泛型所以填Entry键类型值类型3lambda表达式依然是老套路匿名内部类简化为lambda表达式foreach方法内部其实是用2的方法获取每个键值对的值来传给accept方法简化后1.3.3 hashmap没有特殊要求时map系列中优先使用hashmap1特点无序不重复键无索引底层和hashset一样是哈希表hashmap添加键值对时会先创建entry对象然后根据键的hashcode方法来获取哈希值计算要插入的位置如果不为null会使用键的equals来比较二者键是否相同如果不同直接添加相同则覆盖原对象hashset是不添加对于自定义对象作为键的情况如果使用idea默认的方法重写hashcode和equals方法也就是属性相同则哈希值相同且equals判断为true那么最终的效果就是hashmap中只要键的属性值相同就只存一份不太严谨1.3.4 linkedhashmapLinkedHashMap HashMap 的存储结构 双向链表维护顺序1.3.5 treemap1特点2对于 Java 已有类型的排序结果规律其实还是因为这些类按某种规则实现了compareto方法排序是针对键的3自定义比较规则依然是两种比较规则当插入键值对到treemap时通过键来决定插入的位置会调用键的compareto方法或者说使用compare方法来比较要插入元素的键与路径上键的大小可以人为定义 key 之间的比较规则然后通过 key 实现Comparable的compareTo()方法或者创建TreeMap时传入Comparator的compare()方法。TreeMap会按照这套规则组织红黑树因此遍历 key 时会得到按照该规则从“小”到“大”的顺序。方式二当默认的compareto比较规则不符合我们的预期时我们可以通过传入comparetor实现类对象来重新定义比较规则上述例子中例子中我们希望543这种方式来排序所以我们按照4比5大的这种规则来实现compare方法就可以实现这种效果但是integer的compareto方法是按照4比5小的该规则来实现的因此我们要使用方法二重写compare方法所以要返回的就是o2-o11.3.6 一些思考在map这边如果在添加过程中发现键重复了会覆盖之前的元素因为值可能会更新在set时如果发现的元素和已有元素相同直接丢弃1.3.7 map在计数中的应用当要计数的元素过多或者数量不确定时为每个元素定义变量来计数就不适用了此时可以用maptreemap例子如下此时顺序其实就abcd1.4 不可变集合1定义不可变集合就是不能被修改的集合2获取方式由于set系列集合不可重复的性质所以参数不能有重复的值否则会报错对于map对于of方法如果键值对个数超过10个那可以使用如下方法来创建不可变集合先把键值对存在map里然后获取对应的键值对set集合再把set集合转换为数组之后调用map.ofentries获得对应的不可变集合上述代码可以简化为以下写法最简单的写法内部其实和上面原理一样二、泛型2.1 概念2.1.1 如果没有泛型如果创建集合时不加泛型集合里的类型任意。此时存储进去的元素会被作为 Object 类型但是拿出来后依然是 Object 类型需要进行强转恢复为原本的类型去使用这很麻烦。2.1.2 泛型的小细节1Java 中的泛型是伪泛型只在编译时有效即使在 Java 文件中写了泛型在编译后翻译仍然会消失这叫做泛型的擦除。2即使使用了泛型那将数据存储进集合后依然会被当作 Object 类型只不过在取数据时会自动转换为原类型。3它可以规定集合里存储数据的类型在编译时期检查你往集合里存的数据类型是否合法。不合法则编译报错。2.2 泛型的用途2.2.1 泛型类由于当前 List 里要存储的数据类型不确定我们可以将它暂定为 E待创建对象时来指定。带有泛型的类相比于不带泛型的类在创建对象时要在类名后多加个 给泛型赋值。注意泛型类还能一次写两个泛型参数。2.2.2 泛型方法例子如下调用时不用显式地指出 E 对应的类型由于 list 的泛型是 StringE 也就被当作了 String。2.2.3 泛型接口1定义格式2使用方法方法一实例List 是个泛型接口。这其实就是相当于把接口里的泛型替换成 String 再进行实现此时 MyArrayList 不是泛型类直接类名创建对象就好。方法二实例当一个泛型类实现泛型接口时可以将本类的泛型参数传递给接口使类和接口使用同一个类型参数。2.3 泛型的继承和通配符1泛型不具备继承性例子如下函数中定义了一个形参ArrayListYe此时只能传递泛型为 Ye 的 ArrayList不能传递泛型为 Ye 的子类的 ArrayList。2泛型的通配符同样用于中三、数据结构3.1 树二叉树、二叉排序树和平衡二叉树都满足树中的每个节点长这样度每个节点子节点的数量3.2 二叉树1定义任意节点的度都小于等于二2遍历方式3.3 二叉查找树1定义2插入与查找都是从根节点开始比较小的往左走大的往右走3中序遍历二叉查找树时结果序列是从小到大排列的3.4 平衡二叉树1出现原因普通的二叉排序树可能会出现节点很少层数很高的情况这时查找效率太低2定义在二叉排序树的基础上进一步要求所有节点的左右子树高度差小于等于13插入节点与维持平衡的方式a. 大致流程插入节点↓从插入位置向上寻找第一个失衡节点A找不到就完成了↓判断属于LL在左子树的左子树上添加节点导致的不平衡/LR/RR/RL这个是针对不平衡节点A来说的↓按照固定旋转规则调整↓恢复平衡b. 各种情况以及处理规则LL右旋失衡节点ARR左旋失衡节点ALR先左旋A的左孩子再右旋ARL先右旋A的右孩子再左旋Ac. 具体的旋转方法以左旋为例右旋同理其实就是原本的父节点作为右子节点的左子节点如果右子节点原本有左子节点那就把这个左子节点作为父节点的右子节点3.4 查找效率二叉树二叉排序树平衡二叉树3.5 红黑树3.5.1红黑树与平衡二叉树对比平衡二叉树高度平衡查找效率高但是添加节点时要通过旋转维持平衡会浪费太多时间红黑树依然是二叉查找树但是不是高度平衡的只有不符合红黑规则时才会有额外操作红黑树的增删改查性能都很好3.5.2 特点1红黑树节点长这样2红黑树规则对于第三条就是说如果一个节点没有子节点那相应的指针就该记录为nil但是这个节点应当被看作有叶节点且是黑色的也就是说一个节点没有子节点那他就有黑色nil子节点对于第五条简单路径就是一路往下走3添加元素添加的节点默认是红色的效率高某些情况下调整的次数少添加节点的流程就是先添加然后检查是否违反规则如果添加的是非跟节点且父为黑色一定不违反红黑规则然后找对应解决方法下面是添加节点时违反了红黑规则时的处理方案大部分处理还是修改颜色消耗时间很短而旋转比较耗时因此红黑树效率高对于非根且父红色且叔叔红色的说明 步骤四是指把祖父当作新添加进来的节点再次直接对照处理规则表进行处理对于非根且父红色且叔叔黑当前节点是父节点的左孩子的说明步骤三旋转时不用考虑nil节点当作没有即可对于非根且父红色且叔叔黑当前节点是父节点的右孩子的说明就是说把父节点当作刚添加进来的节点旋转后直接进入处理规则进行处理四、其他知识点4.1可变参数此时arr其实就是个数组可以用数组的方式去访问可以给可变参数传0个元素可以直接给可变参数传数组因为他底层本就是数组