java学习与应用（3.2）--数据结构相关

集合拓扑

集合的常用方法说明

集合，不同于数组，长度可变，存储对象。 Collection接口，常用功能如：add添加，clear清空，remove移除，contains是否包含，inEmpty是否为空，size个数，toArray存储到数组 Iterator迭代器接口，取出集合中的元素，直到集合中没有元素。常用如hasNext有下一个元素，和next取出下一个元素方法。 使用迭代器遍历集合，使用collection的iterator方法获取迭代器（含泛型），然后遍历。迭代器实质是从-1指针位置开始向后的移动遍历。 针对遍历的增强for循环，其格式简化了迭代器的书写。for(变量，变量名:集合/数组名){访问变量名}

泛型

泛型，一种未知的数据类型，E代表未知的数据类型，在创建对象时候确定其类型E。默认的E为Object类型。 泛型可以在集合中的数据存储和取出保存相同的类型。在编译期检查代码规范。 创建含有泛型的类，能够让类有通用数据类型的广泛使用。格式为public class Name<E>{ private E xxx 等}，实现中使用E代表返回值和数据定义等。 含有泛型的方法，换如M表示，传递到内部数据，并返回。格式如public [static] <M> void method01(M[使用泛型] m){xxx} 含有泛型的接口，格式如public interface Xxx<E>{ xxxx}。然后创建实现类，定义泛型的数据类型。也可以继承之前的泛型，然后重写。 泛型的通配符，使用?表示任意接收数据，其实质是Object对象，只能在参数传递时候使用（定义时候不能使用） 泛型的上限限定: ? extends E 代表使用的泛型只能是E类型的子类/本身，泛型的下限限定: ? super E 代表使用的泛型只能是E类型的父类/本身，限定其<>中使用的范围 Collections集合工具类，shuffle方法可以打乱集合中的顺序。增强for循环可以使用idea快捷生成

基本数据结构

Java数组的删除等操作，可能更改其首地址（频繁开辟空间）。 排序树，二叉树的基础上，左子树大，右子树小。平衡树，左孩子和右孩子数量相同。不平衡树，左右不等。 红黑树，趋近于平衡树，查询的速度非常的快，查询叶子节点最大次数和最小次数不能超过2倍。查询速度快。

List接口

List接口，有序集合，有索引，允许存储重复元素。常用的方法有add增加元素到指定位置，get返回指定位置元素，remove删除指定位置元素，set设置指定位置元素。可以使用迭代器，get与for等方法进行遍历。 ArrayList数组，使用多线程技术，在增删过程反复开辟空间和赋值，导致增删慢。 LinkedList链表，同样多线程技术，add，addFirst，addLast，push添加元素，getFirst，getLast获取元素，clear清空元素，removeFirst，removeLast，pop移除元素，等等的首尾元素的方法 Vector集合，单线程技术，同步。同样可变长数组。

Set接口

Set接口，不包含重复元素，没有索引，不能使用for遍历。 HashSet集合，哈希表结构（查询快），无序，不同步，使用迭代器或增强for遍历。hashCode方法，获取操作系统随机给出的十进制整数（哈希值（模拟地址值））。 String类重写了hashCode方法。不同字符串可能有相同的哈希值。 java1.8以后，哈希表使用数组，链表和红黑树提高查询速度。 数组结构:把元素进行了分组(相同哈希值的元素是一组，链表/红黑树结构把相同哈希值的元素连接到一起。每组数量大于8则将链表变成红黑树。数组长度定为16。 因在哈希冲突后，会比较组内的元素是否存在，确定是否存储，以保障Set集合中元素不重复。存储的引用类型数据必定重写了hashCode和equals方法（保障数据不重复）。 自定义的数据类型可以通过idea自动生成hashCode和equals方法。 LinkedHashSet集合，哈希表+链表与红黑树结构，另外多了一条链表用于保障元素有序。遍历有序。 可变参数，类型确定，个数不定，格式如int ...arr，其实质为创建数组。使用增强for遍历。可变参数只有一个，且位于所有变量末尾。另外如：Object ...args。

Collections工具类

Collections的工具类，包含静态方法如：add添加元素，shuffle打乱元素，addAll添加多个元素，sort按默认规则排序（自定义类需要实现接口Comparable，重写方法compareTo） sort排序（使用Comparator匿名类重写compare方法作为参数进行排序）其中自定义的排序方法可以组合进行多个关键字排序

Map接口

Map接口，包含K和V两个泛型（键、值）（双列集合，一一对应，键值不能重复）。HashMap集合，实现了Map接口，集合底层为哈希表，查询快。LinkedHashMap底层是哈希表和链表（保障数据顺序）。 Map的方法，put放入（返回被替换的键），get获取，remove删除（返回删除值），containsValue，containsKey是否包含。 keySet方法，返回的key会放到Set集合中，使用迭代器或增强for进行遍历key，键找值，进行遍历。 Map接口的实现集合被创建后，为每个键值对其内部的创建了Entry对象（Map.Entry），多个Entry用于记录键值对映射关系的集合（使用entrySet取出）。使用Entry中的getKey方法获取key，使用getValue创建vaule。 HashMap类存储自定义类型，key需要重写hashCode和equals方法，保障key的唯一性。 LinkedHashMap类，有序集合存储。HashTable键和值都不为空，同步单线程，双列集合（区别于HashMap的允许空值等）。 哈希表的优点和利用在于其快速查找，配合Map可以快速统计。 of方法，一次性添加多个元素，适用于List，Set，Map接口，返回的集合不能改变（JDK9）。