Java基础教程(11)-Java中的集合类

集合类型也是Java标准库中被使用最多的类型；
通常也是面试时最常被问到的问题；

Java中的集合

在Java中，如果一个Java对象可以在内部持有若干其他Java对象，并对外提供访问接口，我们把这种Java对象称为集合。

Java的数组可以看作是一种集合

Java标准库自带的 java.util 包提供了集合类： Collection ;

Collection 除 Map 外所有其他集合类的根接口; 所以也可以时候集合类有两种：Collection和Map,各自有实现的子类；

Java的 java.util 包主要提供了以下三种类型的集合：

• List ：一种有序列表的集合
• Set ：一种保证没有重复元素的集合;
• Map ：一种通过键值（key-value）查找的映射表集合;

还有一小部分集合类是遗留类，不常使用：

• Hashtable ：一种线程安全的 Map 实现；
• Vector ：一种线程安全的 List 实现；
• Stack ：基于 Vector 实现的 LIFO 的栈。

Java访问集合总是通过统一的方式——迭代器（Iterator）来实现，它最明显的好处在于无需知道集合内部元素是按什么方式存储的。

Collection 和 Collections 区别

Collection 是一个集合接口。 它提供了对集合对象进行基本操作的通用接口方法。
Collection 接口在 Java 类库中有很多具体的实现。是 list，set 等的父接口。

Collections 是一个包装类。 它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于 Java 的 Collection 框架;

List和Set

Set 和 List 区别:

• List，Set 都是继承自 Collection 接口。都是用来存储一组相同类型的元素的。
• List 特点：元素有放入顺序，元素可重复 。有顺序，即先放入的元素排在前面。
• Set 特点：元素无放入顺序，元素不可重复。无顺序，即先放入的元素不一定排在前面。 不可重复，即相同元素在 set 中只会保留一份。

List

在集合类中， List 是最基础的一种集合：它是一种有序链表。
List 的行为和数组几乎完全相同： List 内部按照放入元素的先后顺序存放，每个元素都可以通过索引确定自己的位置， List 的索引和数组一样，从 0 开始。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * List和Array转换
 */
public class ListDemo {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("123");
        list.add("456");

        //第一种是调用 toArray() 方法直接返回一个 Object[] 数组
        //会丢失类型信息
        Object[] objects = list.toArray();
        System.out.println(objects.length);
        //第二种方式是给 toArray(T[]) 传入一个类型相同的 Array ，
        // List 内部自动把元素复制到传入的 Array 中
        String[] strings = list.toArray(new String[0]);
        System.out.println(strings[1]);
        strings = list.toArray(new String[1]);
        //如果传入的数组不够大，那么 List 内部会创建一个新的刚好够大的数组，填充后返回；
        System.out.println(strings[1]);
        strings = list.toArray(new String[2]);
        System.out.println(strings.length);
        // 如果传入数组比 List 元素还要多，那么填充完元素后，剩下的数组元素一律填充 null
        strings = list.toArray(new String[3]);
        System.out.println(strings[2]);
        //最常用的是传入一个“恰好”大小的数组
        strings = list.toArray(new String[list.size()]);

        //数组转换为List 使用
        list = Arrays.asList(strings);

    }
}

Arrays.asList 获得的 List 使用时需要注意:

• 1、asList 得到的只是一个 Arrays 的内部类，一个原来数组的视图 List，因此如果对它进行增删操作会报错。
• 2、用 ArrayList 的构造器可以将其转变成真正的 ArrayList。

List 主要有 ArrayList、LinkedList 与 Vector 几种实现；可以通过new一个对象来创建;

ArrayList 是一个可改变大小的数组.当更多的元素加入到 ArrayList 中时,其大小将会动态地增长.内部的元素可以直接通过 get 与 set 方法进行访问,因为 ArrayList 本质上就是一个数组。

LinkedList 是一个双链表,在添加和删除元素时具有比 ArrayList 更好的性能.但在
get 与 set 方面弱于 ArrayList。

Vector 和 ArrayList 类似,但属于强同步类。如果你的程序本身是线程安全的(thread-safe,没有在多个线程之间共享同一个集合/对象),那么使用 ArrayList 是更好的选择。

Vector 和 ArrayList 在更多元素添加进来时会请求更大的空间。Vector 每次请求其大
小的双倍空间，而 ArrayList 每次对 size 增长 50%。而 LinkedList 还实现了 Queue 接口,该接口比List提供了更多的方法,包括 offer(), peek(),poll()等。

遍历一个List可以使用迭代器 Iterator 来访问 。

Iterator 本身也是一个对象，但它是由 List 的实例调用 iterator() 方法的时候创建的。 Iterator 对象知道如何遍历一个 List ，并且不同的 List 类型，返回的 Iterator 对象实现也是不同的;

只要实现了 Iterable 接口的集合类都可以直接用 for each 循环来遍历，Java编译器本身并不知道如何遍历集合对象，但它会自动把 for each 循环变成 Iterator 的调用，原因就在于 Iterable 接口定义了一个 Iterator<E> iterator() 方法，强迫集合类必须返回一个 Iterator 实例

Set

Set 用于存储不重复的元素集合，它主要提供以下几个方法：

• 将元素添加进 Set<E> ： boolean add(E e)
• 将元素从 Set<E> 删除： boolean remove(Object e)
• 判断是否包含元素： boolean contains(Object e)

最常用的 Set 实现类是 HashSet; 其他实现类还有SortedSet; SortedSet 接口保证元素是有序的,实现类包含有TreeSet：

• HashSet 是无序的，因为它实现了 Set 接口，并没有实现 SortedSet 接口；

HashSet 是哈希表实现的,HashSet 中的数据是无序的，可以放入 null，但只能放入一个 null，两者中的值都不能重复;

• TreeSet 是有序的，因为它实现了 SortedSet 接口。

TreeSet 是二叉树实现的,Treeset 中的数据是自动排好序的，不允许放入 null 值

Map

Map 是一种键值（key-value）映射表的数据结构，作用是能高效通过 key 快速查找 value （元素）；

Map<K, V> 是一种键-值映射表，当我们调用 put(K key, V value) 方法时，就把 key 和 value 做了映射并放入 Map 。当我们调用 V get(K key) 时，就可以通过 key 获取到对应的 value 。如果 key 不存在，则返回 null 。和 List 类似， Map 也是一个接口，最常用的实现类是 HashMap 。

HashMap 之所以能根据 key 直接拿到 value ，原因是它内部通过空间换时间的方法，用一个大数组存储所有 value ，并根据key直接计算出 value 应该存储在哪个索引; 通过 key 计算索引的方式就是调用 key 对象的 hashCode() 方法，它返回一个 int 整数。

Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉。虽然 key 不能重复，但 value 是可以重复的;

面试题：
HashMap 和 HashTable 有何不同？

线程安全：HashTable 中的方法是同步的，而 HashMap 中的方法在默认情况下是非同步的。在多线程并发的环境下，可以直接使用 HashTable，但是要使用 HashMap 的话就要自己增加同步处理了。

继承关系： HashTable 是基于陈旧的 Dictionary 类继承来的。HashMap 继承的抽象类 AbstractMap 实现了 Map 接口。

允不允许 null 值： HashTable 中，key 和 value 都不允许出现 null值，否则会抛出NullPointerException 异常。 HashMap 中，null 可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为 null。

默认初始容量和扩容机制： HashTable 中的 hash 数组初始大小是 11，增加的方式是 old*2+1。HashMap 中 hash 数组的默认大小是 16，而且一定是 2 的指数。

哈希值的使用不同 ： HashTable 直接使用对象的 hashCode。HashMap 重新计算 hash 值。

遍历方式的内部实现上不同 ： Hashtable、HashMap 都使用了 Iterator。而由于历史原因，Hashtable 还使用了 Enumeration 的方式

hash是啥?

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。
简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞。