JavaSE基础篇 -- 集合框架详述_超集大合集

LinkedList：特殊的方法。 addFirst(); addLast(); 在jdk1.6以后。 offerFirst(); offerLast(); getFirst()：获取链表中的第一个元素。如果链表为空，抛出NoSuchElementException; getLast(); 在jdk1.6以后。 peekFirst();获取链表中的第一个元素。如果链表为空，返回null。 peekLast(); removeFirst()：获取链表中的第一个元素，但是会删除链表中的第一个元素。如果链表为空，抛出NoSuchElementException removeLast(); 在jdk1.6以后。 pollFirst();获取链表中的第一个元素，但是会删除链表中的第一个元素。如果链表为空，返回null。 pollLast(); ______________________________________________________________________________ Set集合：不允许重复元素。和Collection的方法相同。Set集合取出方法只有一个：迭代器。 |--HashSet：底层数据结构是哈希表(散列表)。无序，比数组查询的效率高。线程不同步的。 -->根据哈希冲突的特点，为了保证哈希表中元素的唯一性， 该容器中存储元素所属类应该复写Object类的hashCode、equals方法。 |--LinkedhashSet：有序，HashSet的子类。 |--TreeSet：底层数据结构是二叉树。可以对Set集合的元素按照指定规则进行排序。线程不同步的。 -->add方法新添加元素必须可以同容器已有元素进行比较， 所以元素所属类应该实现Comparable接口的compareTo方法，以完成排序。 或者添加Comparator比较器。 ------------------------------------------------------------------------------ HashSet：用于存储元素和哈希值对应关系的容器称之为哈希表。 哈希表的原理： 1.对对象元素中的关键字(对象中的特有数据)，进行哈希算法的运算，并得出一个具体的算法值，这个值称为哈希值。 2.哈希值就是这个元素的位置。 3.如果哈希值出现冲突，再次判断这个关键字对应的对象是否相同。 如果对象相同，就不存储，因为元素重复。如果对象不同，就存储，在原来对象的哈希值基础 +1顺延。 4.存储哈希值的结构，我们称为哈希表。 5.既然哈希表是根据哈希值存储的，为了提高效率，最好保证对象的关键字是唯一的。 这样可以尽量少的判断关键字对应的对象是否相同，提高了哈希表的操作效率。 哈希表结构的特点： 1.不允许存储重复元素，因为会发生查找的不确定性。 2.不保证存入和取出的顺序一致，即不保证有序。 3.比数组查询的效率高。 哈希冲突： 当哈希算法算出的两个元素的值相同时，称为哈希冲突。 冲突后，需要对元素进行进一步的判断。判断的是元素的内容，equals。 如果不同，还要继续计算新的位置，比如地址链接法，相当于挂一个链表扩展下来。 在堆内存中，底层就是一种哈希表结构，需要通过哈希算法来计算对象在该结构中存储的地址。 这个方法每个对象都具备，叫做hashCode()方法，隶属于java.lang.Objecct类。 hashCode本身调用的是wondows系统本地的算法，也可以自己定义。 ArrayList存储元素依赖的是equals方法。比如remove、contains底层判断用的都是equals方法。 HashSet判断元素是否相同：依据的是hashCode和equals方法。如果哈希冲突(哈希值相同)，再判断元素的equals方法。如果equals方法返回true，不存；返回false，存储！ 如何保证哈希表中元素的唯一性？ 元素必须覆盖hashCode和equals方法。 覆盖hashCode方法是为了根据元素自身的特点确定哈希值。 覆盖equals方法，是为了解决哈希值的冲突。 如何实现有序？ LinkedHashSet类，可以实现有序。 ------------------------------------------------------------------------------ TreeSet：可以对元素排序。 有序：存入和取出的顺序一致。--> List 排序：升序or降序。--> TreeSet TreeSet排序方式： 需要元素自身具备比较功能。所以元素需要实现Comparable接口。覆盖compareTo方法。 如果元素不具备比较性，在运行时会发生ClassCastException异常 TreeSet能够进行排序。但是自定义的Person类并没有给出排序的规则。 即普通的自定义类不具备排序的功能，所以要实现Comparable接口，强制让元素具备比较性，复写compareTo方法。 如何保证元素唯一性？ 参考的就是比较方法(比如compareTo)的返回值是否是0。是0，就是重复元素，不存。 注意：在进行比较时，如果判断元素不唯一，比如，同姓名同年龄，才视为同一个人。 在判断时，需要分主要条件和次要条件，当主要条件相同时，再判断次要条件，按照次要条件排序。 如何实现有序？ 保证二叉树只return一边，比如： public int compareTo(Object o){ if (this.age == o.age) return 0;//保证TreeSet不存入自定义的重复元素。 return 1;//保证添加的元素都存入二叉树的右子树。 } TreeSet二叉树建立过程： TreeSet底层是二叉树结构，二叉树结构特点是可以排序。并且对二叉树的建立过程内部优化，以减少比较次数。 例子中将已排序的xiaoming:22作为根节点，是基于折半的排序思想。 xiaoqiang:20、xiaoming:22、daniu:24已经按照顺序存好，为了提高效率，在已排序的数组中去找一个新元素存放的位置，折半的方法最快。 所以第四个进来的元素huanhuan:22会先和中间的xiaoming:22比较，然后确定往大的方向还是小的方向走。 按照改进前的规则，huanhuan:22和xiaoming:22属重复元素，不存。tudou:18进来，再和已排序的中间元素xiaoming:22比较。 比xiaoming:22小，往小的方向走，接着和xiaoqiang:20比较，比它小，tudou:18放在xiaoqiang:20左子树位置上。 此时，已排序的依次为：tudou:18、xiaoqiang:20、xiaoming:22、daniu:24。中间元素为xiaoming:22。 dahuang:19先和xiaoming:22比，比它小；再和xiaoqiang:20比，比它小；接着和tudou:18比，比它大，放在tudou:18的右子树上。 建树完毕，TreeSet容器存入元素完毕。 取出元素过程： 根节点的左子树<右子树，所以先遍历左子树，再根节点，最后右子树即可。 xiaoqiang:20......xiaoqiang:20 daniu:24......xiaoqiang:20 xiaoming:22......xiaoqiang:20 xiaoming:22......daniu:24 huanhuan:22......xiaoming:22 huanhuan:22......xiaoqiang:20 tudou:18......xiaoming:22 tudou:18......xiaoqiang:20 dahuang:19......xiaoming:22 dahuang:19......xiaoqiang:20 dahuang:19......tudou:18 tudou:18 dahuang:19 xiaoqiang:20 huanhuan:22 xiaoming:22 daniu:24 ------------------------------------------------------------------------------- TreeSet第一种排序方式：需要元素具备比较功能。 所以元素需要实现Comparable接口。覆盖compareTo方法。 需求中也有这样一种情况，元素具备的比较功能不是所需要的，也就是说不想按照 自然排序的方式，而是按照自定义的排序方式，对元素进行排序。 而且，存储到TreeSet中的元素万一没有比较功能，该如何排序呢？ 这时，就只能使用第二种排序方式--是让集合具备比较功能，定义一个比较器。联想到集合的构造函数，去查API。 TreeSet第二种排序方式：需要集合具备比较功能，定义一个比较器。 所以要实现Comparator接口，覆盖compare方法。将Comparator接口的对象，作为参数传递给TreeSet集合的构造函数。 TreeSet集合排序有两种方式，Comparable和Comparator区别： 1.让元素自身具备比较性，需要元素对象实现Comparable接口，覆盖compareTo方法。 2.让集合自身具备比较性，需要定义一个实现了Comparator接口的比较器，并覆盖compare方法，并将该类对象作为实际参数传递给TreeSet集合的构造函数。 3.容器使用Comparator比较器接口对元素进行排序，只要实现比较器对象就可以 -->降低了比较方式和集合之间的耦合性-->自定义比较器的方式更为灵活。 元素自身可以具备比较功能 -->自然排序通常都作为元素的默认排序。 4.Comparable接口的compareTo方法，一个参数；Comparator接口的compare方法，两个参数。 List是数组或者链表结构，允许重复元素。 HashSet是哈希表结构，查询速度快。 TreeSet是二叉树数据结构。二叉树结构可以实现排序，一堆数据只要存入二叉树，自动完成排序。 ________________________________________________________________________________________ 技巧： jdk1.2以后出现的集合框架中的常用子类对象，存在的规律。 需要唯一吗？ 需要：Set 需要制定顺序： 需要：TreeSet 不需要：HashSet 但是想要一个和存储一致的顺序(有序)：LinkedHashSet 不需要：List 需要频繁增删吗？ 需要：LinkedList 不需要：ArrayList 如何记录每一个容器的结构和所属体系呢？看名字！ List |--ArrayList |--LinkedList Set |--HashSet |--TreeSet 前缀名是数据结构名，后缀名是所属体系名。 ArrayList：数组结构。看到数组，就知道查询快，看到List，就知道可以重复。可以增删改查。 LinkedList：链表结构，增删快。xxxFirst、xxxLast方法，xxx：add、get、remove HashSet：哈希表，查询速度更快，就要想到唯一性、元素必须覆盖hashCode、equals。不保证有序。看到Set，就知道不可以重复。 LinkedHashSet：链表+哈希表。可以实现有序，因为有链表。但保证元素唯一性。 TreeSet：二叉树，可以排序。就要想到两种比较方式(两个接口)：一种是自然排序Comparable，一种是比较器Comparator。 而且通常这些常用的集合容器都是不同步的。