[数据结构与算法]【动力节点 Java进阶学习笔记】第五章 集合

集合概述

1、集合概述和集合继承结构图

• 集合实际上就是一个容器。可以来容纳其它类型的数据
• 集合可以存放不同类型的数据，存放的对象会被封装成Object添加到集合中
• 集合中存储的是引用

Collection继承结构图：

Map继承结构图：

Collection部分

2、Collection接口常用方法、迭代器Iterator、使用迭代器遍历集合元素

• Collection接口常用方法：add(Object e)、size()、clear()、 contains(Object o)、 remove(Object o)、 isEmpty()、toArray()
• Iterator中的方法：hasNext()、next()
• 存放在一个集合中的类型，一定要重写equals方法。因为contains和remove调用的是o的equals方法
• 在迭代元素的过程当中，一定要使用迭代器Iterator的remove方法，删除元素，迭代器去删除时，会自动更新迭代器，并且更新集合（删除集合中的元素）。不要使用集合自带的remove方法删除元素。

3、List接口中常用方法、ArrayList和LinkedList、数组和链表的特点

• List集合存储元素特点：有序可重复
• List接口特有的常用的方法：
  
• ArrayList集合默认初始化容量10，扩容增长到原容量的1.5倍。
• 数组特点：检索效率比较高、随机增删元素效率比较低、向数组末尾添加元素，效率很高，不受影响。
• 链表特点：随机增删效率较高、检索/查找的效率较低。

单向链表的代码实现：

public class Link<E> {

    int size = 0;
    Node header;

    public int size(){
        return size;
    }

    public void add(E data){
        if(header == null){
            header = new Node(data, null);
        }else{
            Node currentLastNode = findLastNode(header);
            currentLastNode.next = new Node(data, null);
        }
        size ++;
    }
    
    public Node findLastNode(Node node){
        if(node.next == null){
            return node;
        }
        return findLastNode(node.next);
    }
}

public class Node {

    // 存储的数据
    Object data;

    // 下一个节点的内存地址
    Node next;

    public Node(){

    }

    public Node(Object data, Node next){
        this.data = data;
        this.next = next;
    }
}

4、泛型的优缺点和使用、for each的使用

• 泛型只在程序编译阶段起作用，只是给编译器参考的。

• 泛型的优点：
  （1）集合中存储的元素类型统一了。
  （2）从集合中取出的元素类型是泛型指定的类型，不需要进行大量的“向下转型”

• 泛型参考用法：
  ???????List myList = new ArrayList();
  ???????List myList = new ArrayList<>(); 自动类型推断机制。（又称为钻石表达式）
  ???????自定义泛型：public class Link {}

• 增强for（foreach）
  ???????for(元素类型 变量名 : 数组或集合){
  ?????????????? …
  ???????}

5、HashSet和TreeSet集合存储元素特点

• HashSet集合：无序不可重复。放到HashSet集合中的元素实际上是放到HashMap集合的key部分了。

• TreeSet集合：无序不可重复，但是存储的元素可以自动按照大小顺序排序。

Map部分

6、Map接口中常用方法和Map集合的遍历

• Map接口中常用方法
  

• 针对put方法返回值的补充说明：
  ???????调用put方法时，如果已经存在一个相同的key， 则返回的是前一个key对应的value，同时该key的新value覆盖旧value；如果是新的一个key，则返回的是null；

• Map集合的遍历：

  ???????第一种方式：获取所有的key，通过遍历key，来遍历value
  ??????????????Set keys = map.keySet();
  ??????????????通过迭代器或者for each通过get方法来遍历value
  ???????第二种方式：Set<Map.Entry<K,V>> entrySet()
  ??????????????通过迭代器或者for each通过getKey()方法来遍历key，通过getValue()方法来遍历value
  ??????????????for(Map.Entry<Integer,String> e:entrys){
  ?????????????????????System.out.println(e.getKey() + “:” + e.getValue());
  ?????????????? }
  ???????第二种方法效率比较高，因为获取key和value都是直接从node对象中获取的属性值。这种方式比较适合于大数据量。

7、HashMap：哈希表数据结构和方法map.put(k,v)、map.get(k)的使用和实现原理

• 哈希表是一个数组和单向链表的结合体
  ???????数组：在查询方面效率很高，随机增删方面效率很低。
  ???????单向链表：在随机增删方面效率较高，在查询方面效率很低。
  ???????哈希表将以上的两种数据结构融合在一起，充分发挥它们各自的优点。
  ???????哈希表/散列表：一维数组，这个数组中每一个元素是一个单向链表

• 方法map.put(k,v)、map.get(k)的使用和实现原理
  

  ???????向Map集合中存，以及从Map集合中取，都是先调用key的hashCode方法，然后再调用equals方法
  ???????放在HashMap集合key部分的元素，以及放在HashSet集合中的元素，需要同时重写hashCode和equals方法。

• 引申的问题：为何重写equals方法就得重写hashCode方法
  ???????因为必须保证重写后的equals方法认定相同的两个对象拥有相同的哈希值
  ???????分析：
  ??????????????1、hashCode方法中“相同对象必须有相同哈希值”的约定
  ??????????????2、为什么要保证它们的哈希值相等呢：hashCode方法不仅仅是与equals配套使用的，它甚至是与Java集合配套使用的，这是保证Java集合正常运行的前提
  ???????详细讲解可参考：https://zhuanlan.zhihu.com/p/50206657

• HashMap集合的默认初始化容量是16，默认加载因子是0.75，扩容2倍

• Hashtable的key和value都是不能为null的。

• HashMap集合的key和value都是可以为null的，但是key值中null只能有一个

8、Hashtable简要了解，Properties的常用方法

• Properties是一个Map集合，继承Hashtable，Properties的key和value都是String类型。
• 常用方法：
  ???????<object>.setProperty(<key>, <value>);
  ???????<object>.getProperty(<key>);

9、TreeMap：自平衡二叉树数据结构、Comparable与Comparator

• 自平衡二叉树数据结构：
  ???????左小右大，中序遍历取出（左根右，从小到大取出）

• 放到TreeSet或者TreeMap集合key部分的元素要想做到排序，包括两种方式：
  ???????第一种：放在集合中的元素实现java.lang.Comparable接口，并实现compareTo方法
  ???????第二种：在构造TreeSet或者TreeMap集合的时候给它传一个比较器对象。比较器实现 java.util.Comparator接口，并实现compare方法

• 如何选择Comparable和Comparator
  ???????当比较规则不会发生改变的时候，或者说当比较规则只有1个的时候，建议实现Comparable接口。
  ???????如果比较规则有多个，并且需要多个比较规则之间频繁切换，建议使用Comparator接口。

• compareTo中比较规则的制定：
  ???????以比较年龄为例，如果是升序输出则return this.age - o.age；如果是降序输出则return o.age - this.age
  

10、Collections工具类

• java.util.Collection 集合接口
• java.util.Collections 集合工具类，方便集合的操作。
• Collections工具类中常用的一些方法
  ???????（1）变成线程安全的：Collections.synchronizedList(list);
  ???????（2）List集合中元素排序，需要保证List集合中的元素实现了：Comparable接口。
  ??????????????Collections.sort(wuGuis);
  ???????（3）Set集合排序
  ??????????????将Set集合转换成List集合
  ??????????????List myList = new ArrayList<>(set);
  ??????????????Collections.sort(myList);