java集合与数据结构

这里尝试将java集合中的概念与数据结构中的概念相结合，以便更好的记忆。

集合框架体系图

概述：

Collection接口:集合类的基本接口，List、Set和Queue接口都继承自它。
Map接口：映射表的基础接口
Iterator接口：迭代器，可以通过迭代器遍历集合中的数据

集合框架接口图.png

此外，由上图可知，还有一个Iterable接口，它是Collection的父接口。
实现Iterable接口的类的对象可以成为 for-each 循环的目标，所以可以得出结论：对于标准类库中的任何集合都可以使用 “ for-each ”循环。
例如：

List<Object> list = new ArrayList();
for (Object obj: list){}

此外，数组也可以使用 for-each 循环遍历，如下：

Object[] list = new Object[10];
for (Object obj: list){}

下面开始详细介绍常用的几个集合：

List集合

java.util.List 接口继承自 Collection 接口，是单列集合的一个重要分支，习惯性地会将实现了 List 接口的对象称为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过索引来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。
这里容易想到List集合这个概念和数据结构中的线性表是很相似的。（List接口中的方法大多为抽象方法，这与线性表是逻辑结构对应。可以这样认为，List是带索引的线性表）
java List一共三个实现类：分别是ArrayList 、Vector 和 LinkedList。

ArrayList（对应于线性表的物理结构——数组）

ArrayList 是实现了List接口的可扩容数组（动态数组），它的内部是基于数组实现的。它的具体定义如下：

public class ArrayList<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, java.io.Serializable {...}

总结：

ArrayList 是最常用的 List 实现类，底层数据结构是数组，查询快，增删慢。
ArrayList 不是线程安全的容器，如果多个线程中至少两个线程修改了 ArrayList 的结构的话就会导致线程安全问题，作为替代条件可以使用线程安全的 List ，应使用
Collections.synchronizedList。

List list = Collections.synchronizedList(new ArrayList(...))

LinkedList（对应线性表中的物理结构——双向链表）

LinkedList 是一个双向链表，允许存储任何元素（包括null）。它主要特性如下：

LinkedList 底层数据结构是链表，查询慢，增删快。
LinkedList 也不是线程安全的,若多个线程并发访问链表,并且至少其中的一个线程修改了链表的结构,那么这个链表必须进行外部加锁。或者使用

List list = Collections.synchronizedList(new LinkedList(...))

Vector

Vector 同 ArrayList 一样，都是基于数组实现的，只不过 Vector 是一个线程安全的容器，它对内部的每个方法都简单粗暴的上锁，避免了多线程引起的安全性问题，但是通常这种同步方式需要的开销比较大。因此，访问元素的效率要远远低于 ArrayList 。
还有，ArrayList 扩容后数组长度会增加50%，而 Vector 扩容长度后数组会增加一倍。

Set集合

Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。对象的相等性本质是对象由 hashCode 值（java 是依据对象的内存地址计算出的此序号）判断的，如果想要让两个不同的对象视为相等的，就必须覆盖 Object 的 hashCode 方法和 equals 方法。

HashSet（对应的数据结构为Hash表）

哈希表边存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序（和 List 显然不同）而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的 hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法如果 equls 结果为 true ，HashSet 就视为同一个元素。如果equals 为 false 就不是同一个元素。

哈希值相同 equals 为 false 的元素（即同义词）是如何存储呢，就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）。也就是哈希值一样的存一列。如图 1 表示 hashCode 值不相同的情况；图 2 表示 hashCode 值相同，但 equals 不相同的情况。

图1和图2.png

TreeSet（对应的数据结构为二叉树）

TreeSet()是使用二叉树（红黑树）的原理对新 add() 的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。
Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，自己定义的类必须实现Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使用。
注意这个实现不是线程安全的。如果多线程并发访问 TreeSet ，并且至少一个线程修改了 TreeSet ，必须进行外部加锁。或者使用

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))

LinkedHashSet

对于 LinkedHashSet 而言，它继承于 HashSet、又基于 LinkedHashMap 来实现的。LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法操作上又与 HashSet 相同，因此LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个 LinkedHashMap 来实现，在相关操作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可。

Map 接口

集是一个集合，它可以快速地查找现有的元素。但是，要查看一个元素，需要有要查找元素的精确副本。这不是一种非常通用的査找方式。通常，我们知道某些键的信息，并想要查找与之对应的元素。映射（map) 数据结构就是为此设计的。映射用来存放键 / 值对。如果提供了键，就能够查找到值。例如，有一张关于员工信息的记录表，键为员工 ID，值为 Employee 对象。

Java 类库为映射提供了两个通用的实现：HashMap 和 TreeMap。这两个类都实现了 Map 接口。

散列映射对键进行散列，树映射用键的整体顺序对元素进行排序，并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。

应该选择散列映射还是树映射呢？与集一样，散列稍微快一些，如果不需要按照排列顺序访问键，就最好选择散列。

HashMap

下列代码将为存储的员工信息建立一个散列映射：

Map<String, Employee>staff = new HashMap<>();
// HashMap implements Map
Employee harry = new Employee("Harry Hacker");
staff.put(”987-98-9996", harry);

每当往映射中添加对象时，必须同时提供一个键。在这里，键是一个字符串，对应的值是 Employee 对象。
要想检索一个对象，必须使用（因而，必须记住）一个键。

String id = "987-98-9996"; 
e = staff,get(id);// gets harry

如果在映射中没有与给定键对应的信息， get 将返回 null。

总结：

HashMap 是一个利用哈希表原理来存储元素的集合，并且允许空的 key-value 键值对。
HashMap 不是线程安全的,而 Hashtable 是线程安全的容器。
可以使用 Collections.synchronizedMap(new HashMap(...)) 来构造一个线程安全的 HashMap。
在java7中其底层是由数组+链表组成的，到了java8是由数组+链表+红黑树组成。

TreeMap

TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器（通过 Comparator 进行定制排序），当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。

如果使用排序的映射，建议使用 TreeMap。

在使用 TreeMap 时，key 必须实现Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常。

LinkedHashMap（记录插入顺序）

LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

Collections 类

java.utils.Collections 是集合工具类，用来对集合进行操作。部分方法如下：

public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素。
public static void shuffle(List<?> list) 打乱顺序 :打乱集合顺序。
public static <T> void sort(List<T> list) :将集合中元素按照默认规则排序。
public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。

代码演示

public class CollectionsDemo { 
  public static void main(String[] args) {             
    ArrayList<Integer> list = new ArrayList<Integer>(); 
    //原来写法 
    //list.add(12); 
    //list.add(14); 
    //list.add(15); 
    //list.add(1000); 
    //采用工具类完成往集合中添加元素     
    Collections.addAll(list, 5, 222, 1，2); 
    System.out.println(list); 
    //排序方法 
    Collections.sort(list); 
    System.out.println(list); 
  } 
}
结果： 
[5, 222, 1, 2] 
[1, 2, 5, 222]

代码演示之后，发现我们的集合按照顺序进行了排列，可是这样的顺序是采用默认的顺序，如果想要指定顺序那该怎么办呢？

我们发现还有个方法没有讲， public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。接下来讲解一下指定规则的排列。

Comparator比较器

在JAVA中提供了两种比较大小的方式，一种是比较死板的采用 java.lang.Comparable 接口去实现，一种是灵活的当我需要做排序的时候再去选择的 java.util.Comparator 接口来完成。

那么我们采用的 public static <T> void sort(List<T> list) 这个方法完成的排序，实际上要求了被排序的类型需要实现Comparable接口完成比较的功能，在String类型上如下：

public final class String implements java.io.Serializable, Comparable<String>, CharSequence {

String类实现了这个接口，并完成了比较规则的定义，但是这样就把这种规则写死了，那比如我想要字符串按照第一个字符降序排列，那么这样就要修改String的源代码，这是不可能的了，那么这个时候我们可以使用 public static <T> void sort(List<T> list，Comparator<? super T> ) 方法灵活的完成，这个里面就涉及到了 Comparator 这个接口，位于位于java.util包下，排序是comparator能实现的功能之一,该接口代表一个比较器，比较器具有可比性！顾名思义就是做排序的，通俗地讲需要比较两个对象谁排在前谁排在后，那么比较的方法就是：

public int compare(String o1, String o2) ：比较其两个参数的顺序。

两个对象比较的结果有三种：大于，等于，小于。
如果要按照升序排序，则o1 小于o2，返回（负数），相等返回0，01大于02返回（正数）如果要按照降序排序则o1 小于o2，返回（正数），相等返回0，01大于02返回（负数）

操作如下：

public class CollectionsDemo3 { 
  public static void main(String[] args) { 
    ArrayList<String> list = new ArrayList<String>();                 
    list.add("cba"); 
    list.add("aba"); 
    list.add("sba");
    list.add("nba"); 
    //排序方法 按照第一个单词的降序 
    Collections.sort(list, new Comparator<String>() {
      @Override 
      public int compare(String o1, String o2) { 
          return o2.charAt(0) ‐ o1.charAt(0); 
      } 
  }); 
  System.out.println(list); 
  } 
}

结果如下：

[sba, nba, cba, aba]

集合实现类特征图

集合实现类特征图.png