java集合

java里的集合（Collection）是java里面非常重要的一个概念。刚开始看java数组的时候出于先入为主的影响，总是难免会以为是JS里面的Array，区别也就在于java里面的数组里的每一项都是单一类型的（毕竟是强类型语言）。然而java里面的数组长度是不可变的，也就不可能出现JS里面类似push，shift等直接改变数组长度的操作了，可是前后端交互时我们通过ajax拿到的数据分明就是一个数组，长度也不是固定的。没错，实际上JS里面的数组在java里面更像是ArrayList，它继承List，而List又继承了本文的主角Collection。

什么是集合，下面是java文档的原文

A collections framework is a unified architecture for representing and > manipulating collections. All collections frameworks contain the following:

• Interfaces: These are abstract data types that represent collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages, interfaces generally form a hierarchy.
• Implementations: These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.
• Algorithms: These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces. The algorithms are said to be polymorphic: that is, the same method can be used on many different implementations of the appropriate collection interface. In essence, algorithms are reusable functionality.

最核心的集合如下图所示

Two interface trees, one starting with Collection and including Set, SortedSet, List, and Queue, and the other starting with Map and including SortedMap.

List

数组(Array)

在集合类中，List是最基础的一种集合：它是一种有序列表。在数据结构里面，我们有两种表示有序集合的结构。

数组(Array)

数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构，在各种编程语言中都有对应。一个数组可以分解为多个数组元素，按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。

链表( Linked List)

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。

java针对这两种结构实现了ArrayList和LinkedList ，通过名字我们也很容易知道对应的种类，下面是主要的区别。

ArrayList	LinkedList
获取指定元素	速度很快	需要从头开始查找元素
添加元素到末尾	速度很快	速度很快
在指定位置添加/删除	需要移动元素	不需要移动元素
内存占用	少	较大

在需要索引值来定位的地方使用ArrayList要更合理，所以实际开发中ArrayList使用的场合要比LinkedList多一些。
另外，要使用foreach的方式去遍历

  for (String s : list) {
            System.out.println(s);
        }

如果采用下面的方法，在遍历非ArrayList的时候，索引越大，遍历越慢。

        for (int i=0; i<list.size(); i++) {
            String s = list.get(i);
            System.out.println(s);
        }

Map

上面我们说了前后端交互的时候java一般会以ArrayList的结构去返回值，那形如

{
    a:1,
    b:2
}

的结构也就是Map 了，Map主要有三种实现 HashMap, TreeMap, 和 LinkedHashMap。

HashMap

性能最高的map，由于采用的是散列（Hash）的数据结构，是用空间换时间的方式，效率高，但是不能保证顺序。

image.png

我们可以看到遍历的顺序不能保证。

TreeMap

使用红黑树（red-black tree）的数据结构储存key，比hashmap要慢，在不自定义实现Comparable的情况下会以自然顺序排序(类似1->2->3 a->b->c)

LinkedMap

内部使用链表（linked list）的数据结构储存key，在不自定义实现Comparable的情况下会以元素添加的顺序排序。上面那个例子会以“apple”，“pear”，“banana”的顺序返回。

Set

Map用于存储key-value的映射，对于充当key的对象，是不能重复的，并且，不但需要正确覆写equals()方法，还要正确覆写hashCode()方法。

如果我们只需要存储不重复的key，并不需要存储映射的value，那么就可以使用Set。

与Map类似，Set实现了HashSet, TreeSet, 和 LinkedHashSet，基本都是在对应map类上的一些封装，这里就不再赘述了。

---

另外，js现在也有了Map和Set，mdn上的描述如下

Map 对象保存键值对，并且能够记住键的原始插入顺序。任何值(对象或者原始值) 都可以作为一个键或一个值。

Set对象是值的集合，你可以按照插入的顺序迭代它的元素。 Set中的元素只会出现一次，即 Set 中的元素是唯一的。

相信看了上面的知识，会很容易就知道js Map和Set的数据结构是哪一种了。