java 集合总结

先上一张集合家族的结构图，对集合框架有一个整体的认识：

本文出处：https://my.oschina.net/liuyuantao/blog/1512252

                https://my.oschina.net/ouyangsihai/blog/1806516

对其中的重点进行总结，这样有利于理解与记忆

对于在集合中常用到的泛型：

泛型：就是类型的参数化，泛型是类型的一部分，泛型 + 类名是一个整体。

泛型的通配符(?)：

上限限定：比如定义方法的时候出现，public void getFunc(List<? extends Animal> an)，

那么表示这里的参数可以传入 Animal，或者 Animal 的子类

下限限定: 比如定义方法的时候出现，public void getFunc(Set<? super Animal> an ),

那么表示这里的参数可以传入 Animal，或者 Animal 的父类

使用泛型的注意点:

1、泛型不支持基本数据类型

2、泛型不支持继承，必须保持前后一致（比如这样是错误的：List<Object> list = new ArrayList<String>();

3、泛型如果不指定具体类型，参数会自动提升我 Object 类型。

Collection 体系：

1.Collection 的主要体系：List、Set

• List：存取有序有索引，元素可重复，主要实现类有：ArrayList, LinkedList,Vector(已过时)
• set：存取无序，元素不可以重复，主要实现类有：HashSet,LinkedHashSet,TreeSet

2.List 体系总结

• ArrayList:底层是数组结构，查询快，增删慢。线程不安全，效率高。由于 ArrayList 底层是维护的一个可变数组，说以在所以若知道我们需要存储数据的容量前提下，创建对象时指定 list 的大小，可避免底层数组频繁扩容 ，提高性能。
• LinkedList:是基于链表结构实现的，查询速度慢，增删速度快，提供了对头尾元素进行增删查的方法，通过对头尾元素增删查的的先后顺序实现实现栈和队列；栈是先进后出，而队列是先进先出

3.Set 体系：

• HashSet: 哈希表是通过 hashCode 和 equals 方法来共同保证元素的唯一性，所以对自定义对象要保证唯一性，一定要重写这两个方法。

  哈希表的存储数据过程（哈希表底层也维护了一个数组）：

  根据存储的元素计算出 hashCode 值，然后根据计算得出的 hashCode 值和数组的长度计算出存储的下标；如果下标的位置无元素，那么直接存储；如果有元素，那么使用要存入的元素和该元素进行 equals 方法，如果结果为真，则已经有相同的元素了，所以直接不存；如果结果假，那么进行存储，以链表的形式存储。所以注意点：在重写 hashCode 方法和 equals 方法时要保证比较结果的一致性。

• LinkedHashSet:是基于链表和哈希表共同实现的，所以具有存取有序，元素唯一的特点

• TreeSet:存取无序，元素唯一，存储过程中会进行排序，TreeSet 是基于二叉树的数据结构  

  二叉树的存储过程：

  如果是第一个元素，那么直接存入，作为根节点，下一个元素进来是会跟节点比较，如果大于节点放右边的，小于节点放左边；等于节点就不存储。后面的元素进来会依次比较，直到有位置存储为止，

  TreeSet 保证元素的唯一性是有两种方式**：**

  1、自定义对象实现 Comparable 接口，重写 comparaTo 方法，该方法返回 0 表示相等，小于 0 表示准备存入的元素比被比较的元素小，否则大于 0；

  2、在创建 TreeSet 的时候向构造器中传入比较器 Comparator 接口实现类对象，实现 Comparator 接口重写 compara 方法。

  如果向 TreeSet 存入自定义对象时，自定义类没有实现 Comparable 接口，或者没有传入 Comparator 比较器时，会出现 ClassCastException 异常

Map 体系

Map 与 List、Set 接口不同，它是由一系列键值对组成的集合，提供了 key 到 Value 的映射。同时它也没有继承 Collection。在 Map 中它保证了 key 与 value 之间的一一对应关系。也就是说一个 key 对应一个 value，所以它不能存在相同的 key 值，当然 value 值可以相同。实现 map 的有：HashMap、TreeMap、HashTable、Properties、EnumMap。

从源码可以看到 TreeSet,HashSet 内部就是通过对应的 map 来实现的所以他们 key 的存储特点及原理是一致的

HashMap 与 TreeMap 区别：

      1、HashMap 通过 hashcode 对其内容进行快速查找，而 TreeMap 中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用 TreeMap（HashMap 中元素的排列顺序是不固定的）。HashMap 中元素的排列顺序是不固定的）。

      2、  HashMap 通过 hashcode 对其内容进行快速查找，而 TreeMap 中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用 TreeMap（HashMap 中元素的排列顺序是不固定的）。集合框架”提供两种常规的 Map 实现：HashMap 和 TreeMap (TreeMap 实现 SortedMap 接口)。

      3、在 Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么 TreeMap 会更好。使用 HashMap 要求添加的键类明确定义了 hashCode()和 equals()的实现。 这个 TreeMap 没有调优选项，因为该树总处于平衡状态。                                   

Hashtable 与 Hashmap 区别

      1、历史原因:Hashtable 是基于陈旧的 Dictionary 类的，HashMap 是 Java 1.2 引进的 Map 接口的一个实现 。

      2、同步性:Hashtable 是线程安全的（方法上有加 synchronized 关键字），也就是说是同步的，而 HashMap 是线程序不安全的，不是同步的 。

      3、值：只有 HashMap 可以让你将空值作为一个表的条目的 key 或 value 。