Java 集合
集合是对象的容器，定义了多个对象进行操作的常用方法，可实现数组的功能。
Java集合类库所处位置：java.util.*。
与现代的数据结构类库的常见做法一样，Java集合类库也将接口与实现分离开。
集合和数组的区别：
1.数组长度固定，集合长度不固定。
2.数组可以存储基本类型和引用类型，集合只能存储引用类型。
Java 集合框架中的接口体系
Java集合框架中的重要接口
Java集合框架中，集合有两个基本接口：Collection 和 Map。
Collection 接口
Collection 接口实现了Iterable 接口，我们来看看Iterable 接口的定义：
public interface Iterable<T> {
// 返回一个T元素类型的迭代器
Iterator<T> iterator();
// 其他接口方法...
}
}
在Java 1.8帮助文档中对Iterable 接口的说明是：实现此接口允许对象成为“for-each loop”语句的目标。
Collection 接口扩展了Iterable 接口。因此，对于标准类库中的任何实现Collection 接口的集合都可以使用“for each”循环来遍历元素。
Iterable 接口中只定义了一个抽象方法iterator()，该方法用于返回一个实现了Iterator 接口的（迭代器）对象，可以使用这个迭代器对象依次访问集合中的元素。
Iterator 接口
我们来看看这个Iterator（迭代器）接口：
public interface Iterator<E> {
// 如果迭代具有更多元素，则返回 true 。
boolean hasNext();
// 返回迭代中的下一个元素。
E next();
// 从底层集合中删除此迭代器返回的最后一个元素（可选操作）。
default void remove() {
throw new UnsupportedOperationException("remove");
}
// 对每个剩余元素执行给定的操作，直到所有元素都被处理或动作引发异常。
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
通过反复调用next方法，可以逐个访问集合中的每个元素。但是，如果到达了集合的末尾，next方法将抛出一个NoSuchElementException。因此，需要在调用next之前调用hasNext方法。如果迭代器对象还有多个供访问的元素，这个方法就返回true。如果想要查看集合中的所有元素，就请求一个迭代器，并在hasNext返回true时反复地调用next方法。
我们来看一看案例：
public class TestList {
public static void main(String[] args) {
// 1.创建对象
List list = new ArrayList();
// 2.遍历元素
// 方法一：迭代器
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
// 方法二：for-each
for (Object object : list) {
System.out.println(object);
}
}
}
我们创建了一个扩展了Collection 接口的接口List 的实现类ArrayList的对象，并没有添加元素，因为我们此刻的重点是看迭代器的具体使用。上面提到过，Collection 接口 扩展了 Iterable 接口，所以此集合也可以使用“for-each”循环来遍历。
元素被访问的顺序取决于集合类型。如果对ArrayList进行迭代，迭代器将从索引0开始，每迭代一次，索引值加1。然而，如果访问HashSet中的元素，每个元素将会按照某种随机的次序出现。虽然可以确定在迭代过程中能够遍历到集合中的所有元素，但却无法预知元素被访问的次序。
Java集合类库中的迭代器与其他类库中的迭代器的区别
在传统的集合类库中，例如，C++的标准模版库，迭代器是根据数组索引建模的。如果给定这样一个迭代器，就可以查看指定位置上的元素，就像知道数组索引i就可以查看数组元素a[i]一样。不需要查找元素，就可以将迭代器向前移动一个位置。这与不需要执行查找操作就可以通过i++将数组索引向前移动一样。
但是，Java迭代器并不是这样操作的。查找操作与位置变更是紧密相连的。查找一个元素的唯一方法是调用next，而在执行查找操作的同时，迭代器的位置随之向前移动。因此，应该将Java迭代器认为是位于两个元素之间。当调用next时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。
Collection 接口中的方法
|
方法 |
描述 |
|
boolean add(E e) |
确保此集合包含指定的元素。 |
|
boolean addAll(Collection<? extends E> c) |
将指定集合中的所有元素添加到此集合。 |
|
void clear() |
从此集合中删除所有元素。 |
|
boolean contains(Object o) |
如果此集合包含指定的元素，则返回 true 。 |
|
boolean containsAll(Collection<?> c) |
如果此集合包含指定 集合中的所有元素，则返回true。 |
|
boolean equals(Object o) |
将指定的对象与此集合进行比较以获得相等性。 |
|
int hashCode() |
返回此集合的哈希码值。 |
|
boolean isEmpty() |
如果此集合不包含元素，则返回 true 。 |
|
Iterator<E> iterator() |
返回此集合中的元素的迭代器。 |
|
boolean remove(Object o) |
从该集合中删除指定元素的单个实例（如果存在）。 |
|
int size() |
返回此集合中的元素数。 |
Collection 接口常用方法
这儿只列出来了一些常用的方法，这些方法被Collection 下属的三个集合接口List、Set、Queue所继承，它们又继承给自己打下属接口。注意，此时并没有实现这些方法，因为Java集合类库是将接口和实现分离的，后续我们会讲到方法的实现。
Map 接口
Map集合用于保存具有映射关系的数据，存储键(key)值(value)对，一对一对往里存，保证键(key)的唯一性。
Map 接口中的方法
|
方法 |
描述 |
|
boolean containsKey(Object key) |
如果此映射包含指定键的映射，则返回 true 。 |
|
void clear() |
从该地图中删除所有的映射。 |
|
boolean containsValue(Object value) |
如果此地图将一个或多个键映射到指定的值，则返回 true 。 |
|
Set<Map.Entry<K,V>> entrySet() |
返回此地图中包含的映射的Set视图。 |
|
boolean equals(Object o) |
将指定的对象与此映射进行比较以获得相等性。 |
|
V get(Object key) |
返回到指定键所映射的值，或 null如果此映射包含该键的映射。 |
|
int hashCode() |
返回此地图的哈希码值。 |
|
boolean isEmpty() |
如果此地图不包含键值映射，则返回 true 。 |
|
Set<K> keySet() |
返回此地图中包含的键的Set视图。 |
|
V put(K key, V value) |
将指定的值与该映射中的指定键相关联。 |
|
V remove(Object key) |
如果存在，从该地图中删除一个键的映射。 |
|
int size() |
size()返回此地图中键值映射的数量。 |
|
Collection<V> values() |
返回此地图中包含的值的Collection视图。 |
Map接口常用方法
ListIterator 接口
ListIterator是一个功能更加强大的迭代器, 它继承于Iterator接口,只能用于各种List类型的访问。可以通过调用listIterator()方法产生一个指向List开始处的ListIterator, 除此以外还可以调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator。
ListIterator的特点:
(1) 双向移动（向前/向后遍历）。
(2) 可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引。
(3) 可以使用set()方法替换它访问过的最后一个元素。
(4) 可以使用add()方法在next()方法返回的元素之前或previous()方法返回的元素之后插入一个元素。
Iterator和ListIterator区别
集合List和Set都有iterator()方法来取得其迭代器。对List来说，你也可以通过listIterator()取得其迭代器，两种迭代器在有些时候是不能通用的，Iterator和ListIterator主要区别在以下方面：
① ListIterator有add()方法，可以向List中添加对象，而Iterator不能。
② ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历；Iterator就不可以。
③ ListIterator可以定位当前的索引位置，用nextIndex()和previousIndex()来实现，但是Iterator没有此功能。
④ 都可实现删除对象，但是ListIterator可以实现对象的修改，使用set()方法实现，但是Iierator仅能遍历，不能修改。
RandomAccess 接口
实际中有两种有序集合，其性能开销有很大差异。由数组支持的有序集合可以快速地随机访问，因此适合使用List方法并提供一个整数索引来访问。与之不同，链表尽管也是有序的，但是随机访问很慢，所以最好使用迭代器来遍历。
为了避免对链表完成随机访问操作，Java SE 1.4引入了一个标记接口RandomAccess。这个接口不包含任何方法，不过可以用它来测试一个特定的集合是否支持高效的随机访问。
我们来看一看如何应用它：
if (o instanceof RandomAccess) {
System.out.println("o支持随机访问");
}else {
System.out.println("o不至此随机访问");
}
Java集合框架中的实现类体系
与现代的数据结构类库的常见做法一样，Java集合类库也将接口与实现分离开。我们来看看有哪些实现类：
Java 集合框架中的实现类
我们在上节看到的集合的几种接口在上图中都有其对应的抽象类，这些抽象类中实现了其子类共有的方法，继承了接口中的其他方法。抽象类下面有各自具体的实现子类，在其中定义了各自特有的方法和实现。
我们来梳理一下集合具体实现类：
★ 集合中有两大基本的接口：Collection 和 Map。
★ Collection 接口下有两个重要集合：List 和 Set。
☆ List 集合的实现类有ArrayList、Vector 和 LinkedList。
☆ Set 集合的常用实现类有HashSet、TreeSet 和 LinkedHashSet。
★ Map 接口下只有Map集合，Map集合重要的实现类有：HashMap、TreeMap 和 LinkedHashMap。
List 集合
List 是用于存放多个元素的容器，它允许有重复的元素，并保证元素之间的先后顺序。List 有3个主要的实现类：ArrayList、Vector 和 LinkedList。
ArrayList
ArrayList 类又称为动态数组，该容器类实现了列表的相关操作。ArrayList的内部数据结构由数组实现，因此可对容器内元素实现快速随机访问。但因为在ArrayList 中插入或删除一个元素需要移动其他元素，所以不适合在插入和删除操作频繁的场景下使用 ArrayList。与此同时，ArrayList的容量可以随着元素的增加而自动增加，所以不用担心ArrayList容量不足的问题。另外 ArrayList是非线程安全的。
ArrayList的常用方法总结如下:
添加元素
boolean add(E e)：将指定的元素e添加到此列表的尾部。
void add(int index,E element)：将指定的元素 element 插入此列表中的指定位置index.
boolean addAll(Collection<? extends E> c)：将该Collection 中的所有元素添加到此列表的尾部。
boolean addAll(int index,Collection<?extends E> c)：从指定的位置index开始，将指定Collection 中的所有元素插入此列表中。
删除元素
E remove(int index)：移除此列表中指定位置index上的元素。
boolean remove(Object o)：移除此列表中首次出现的指定元素。（如果存在的话）。
void clear()：移除此列表中的所有元素。
查找元素
boolean contains(Object o)：如果此列表中包含指定的元素o,则返回true.
E get(int index)：返回此列表中指定位置index上的元素。
int indexOf(Object o)：返回此列表中首次出现的指定元素o的索引，或如果此列表不包含元素o,则返回-1.
boolean isEmpty()：如果此列表中没有元素，则返回true,否则返回 false.
int lastIndexOf(Object o)：返回此列表中最后一次出现指定元素o的索引，如果此列表不包含则返回-1.
其他方法
E set(int index,E element)：用指定的元素element 替代此列表中指定位置index上的元素。注意它与 void add (int index,E element)方法的区别：add方法是添加一个元素，原来index 位置上的元素要向后移动；而set方法是将原来index 位置上的元素替换为element.
int size()：返回此列表中的元素数。
Object[] toArray()：按适当顺序（从第一个元素到最后一个元素）返回包含此列表中所有元素构成的数组。
重点：ArrayList 的扩容机制
问题描述：
ArrayList list= new ArrayList(20);
在创建 list 时扩充容量几次？
问题分析：
ArrayList 类又称为动态数组，内部数据结构由数组实现，数组的容量可以自动增长，当数组容量不足以存放新增元素时，需要进行数组的扩容，扩容的基本策略如下：
每次向数组中添加元素时，要检查添加元素后的容量是否超过当前数组的长度，如果没有超过，则添加该元素，不做其他操作；如果超过，则数组就会进行自动扩容，每次扩充原容量的1.5倍。另外 ArrayList 提供了3个构造函数，在初始扩容时有略微不同，因为篇幅问题，在这不做过多阐述，具体请看这篇文章：浅谈ArrayList的扩容机制。
问题结果：
扩容0次。
Vector
Vector类又称为向量类，也实现了类似动态数组的功能，内部数据结构也由数组实现。与ArrayList 不同的是，Vector是线程安全的，它的方法都是同步方法，所以访问效率低于ArrayList。另外 Vector 是非泛型集合，可以往其中随意插入不同类的对象，不需要考虑类型和预先选定向量的容量，可方便地进行查找等操作。当然也可以使用Vector 的泛型取代非泛型类型（例如 Vectort<String>)。
Vector 的常用方法总结如下：
添加元素
public synchronized boolean add(E e)：在最后位置新增元素e.
public void add(int index, E element)：在具体的索引位置index 上添加元素 element,因为该函数内部调用了同步方法synchronized void insertElementAt(),所以该方法依然是同步的。
public synchronized boolean addAll(Collection<?extends E>c)：将一个容器c的所有元素添加到向量的尾部。
删除元素
public boolean remove(Object o)：删除元素o,方法内部调用了另一个同步方法 public synchronized boolean removeElement(Object obj),所以该方法依然是同步的。
public synchronized void removeElementAt(int index)：删除指定位置的元素。
查找元素
public synchronized E elementAt(int index)：查找指定位置的元素。
其他方法
public synchronized E get(int index)：获取指定位置index的元素。
public synchronized E set(int index,E element)：用指定的元素element 替代 Vector 中指定位置index上的元素。
对比Vector 和 ArrayList 的主要方法，可以发现：Vector的方法与ArrayList 的方法的主要差异是增加了 synchronized 关键字，这样保证了执行的线程安全，但也势必会影响Vector的性能。
所以在不要求线程安全的场景中，推荐使用性能更好的 ArrayList。
LinkedList
LinkedList 也是List 的一个重要实现类。它的内部数据结构由链表结构实现，并且是非线程安全的，适合数据的动态插入和删除，插入和删除元素时不需要对数据进行移动、所以插入、删除效率较高，但随机访问速度较慢。
Set 集合
HashSet 和 TreeSet 是Set接口的两个最重要的实现类，在Set容器类中得到广泛使用。其中 TreeSet是 Set的子接口 SortedSet的实现类。
HashSet
HashSet 是java.util包中的类，实现了Set接口，封装了HashMap,元素是通过HashMap来保存的。
关于 HashSet 有以下几点需要说明：
① HashSet 中的元素可以是null,但只能有一个null(因为实现了Set接口，所以不允许有重复的值）。
② HashSet 是非线程安全的。
③ 插入HashSet 中的对象不保证与插入的顺序一致，元素的排列顺序可能改变。
④ 向HashSet 中添加新的对象时，HashSet类会进行重复对象元素判断：判断添加对象和容器内已有对象是否重复，如果重复则不添加，如果不重复则添加。
HashSet 是怎么区分重复元素的？
在上面已经说过，HashSet实现了Set接口，所以不能存储重复元素。在向 HashSet 中添加元素时会调用 HashSet的boolean add(E e)方法，在该方法中，HashSet 会首先判断所要添加的元素是否与容器内已存在的元素有重复，如果没有重复则添该元索并返回true,否则不添加元素并返回 false。
那么如何判断所要添加的元素是否与容器内已存在的元素有重复呢？在 HashSet 内部，HashSet 封装了 HashMap,在调用add()方法时，实际上是调用了HashMap 的 put()方法添加元素，源码如下：
public boolean add(E e){
return map.put(e,PRESENT)==null;
}
我们来看上面的代码，其中添加的元素e就是HashMap的key(put方法的第一个参数）。HashMap 的 put()方法首先会调用元素e的hashCode()得到其在 HashMap 中的索引，如果在该索引位置上已存在其他元素（即两个元素的hashCode()返回值相等），则再调用e的equals()方法判断该索引位置上的元素是否与要添加的元素e相等。只有上述两个条件都满足，才能确认该HashMap 中已经包含元素e.
总结一下，要准确判断HashSet 中两个对象重复与否，需要hashCode()和 equals()这两个方法共同来确定，即如果 hashCode()返回值相等并且 equals()返回true,则判定两个对象重复，只要任一条件不满足，则判定两个对象不重复。
如果大家还对此过程有疑惑，我们可以进一步了解HashSet 中的 HashMap.put()方法，看看它是如何实现添加元素功能的，源代码如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
进一步来看putVal 方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 如果存储元素的table为空，则进行必要字段的初始化
if ((tab = table) == null || (n = tab.length) == 0)
// 获取长度（默认初始容量：16）
n = (tab = resize()).length;
// 如果根据hash值获取的结点为空，则新建一个结点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果该节点不为空，则进行进一步判断
else {
Node<K,V> e;
K k;
// 1.找到与插入节点相映射的节点，如果没有则创建
// 这里的p结点是根据hash值算出来对应在数组中的元素
// 如果新插入的结点和table中p结点的hash值，key值相同的话，将节点p赋值给节点e
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是红黑树结点的话，进行红黑树插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果是单链表的话，遍历链表，查找对应节点
else {
for (int binCount = 0; ; ++binCount) {
// 如果遍历完了单链表，直接新增节点到链表末尾，并退出循环
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度大于8时，将链表转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果需要插入的结点和table中p结点的hash值，key值相同的话，直接退出循环
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
// 遍历下一个节点
p = e;
}
}
// 2.如果存在这个映射就覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 回调以允许LinkedHashMap后置操作
afterNodeAccess(e);
return oldValue;
}
}
// 更改操作次数
++modCount;
// 如果长度大于临界值
if (++size > threshold)
// 将数组大小设置为原来的2倍，并将原先的数组中的元素放到新数组中
// 因为有链表，红黑树之类，因此还要调整他们
resize();
// 回调以允许LinkedHashMap后置操作
afterNodeInsertion(evict);
return null;
}
通过代码的描述能够看出，这里向HashSet中添加的元素实际上就是HashMap 中的key,而不是value。代码中首先获取对象key的hash值，然后以此hash值得到key 在HashMap 中的索引。因为HashMap 本质上是一个数组＋链表＋红黑树的数据结构，所以在同一个索引i下可能存在多个元素，因此这里通过一个循环遍历该索引i下的每一个元素。如果发现要添加到HashMap 中的元素key与该索引上的某个元素重复（hash值相等并且equals 返回值为true),则用新的value覆盖掉旧的value,并返回oldValue,这样调用它的HashSet.add()方法则返回false,表示添加元素不成功；如果发现要添加到HashMap 中的元素key与该索引上的任何元素都不重复，则把（key,value)键值对插入该索引下，然后返回null,这样调用它的HashSet.add()方法则返回true,表示添加元素成功。
类型转换问题
我们来看一段代码：
public static void main(String[] args) {
Set<Short> set = new HashSet<Short>();
for (short i = 0; i < 10; i++) {
set.add(i);
set.remove(i - 1);
}
System.out.println(set.size());
}
大家可以看一下上面的代码，然后算一下输出的结果应该是多少？下面我们来一一分析：
HashSet 的常用方法总结如下：
① add(Ee):返回boolean型值，其功能是在HashSet 中添加指定元素e.
说明：添加元素e时HashSet类先进行重复元素判断：如果要添加的元素和已有元素重复，则添加不成功，返回false;否则添加元素e,返回true.
② remove(Object o):返回boolean 型值，其功能是从HashSet 中移除指定元素o.
说明：如果元素o不包含在HashSet中，则未删除任何元素，返回false;否则，删除元素o,返回true.
下面我们来分析代码的执行情况：
先创建了一个 Short类型的 HashSet 对象。然后调用add()方法向HashSet中插入元素。因为这里插入的是short类型的值，而add()方法的参数是引用类型Short,所以 short类型的参数会自动装箱成其包装类Short类型。调用remove(i-1),i为short型，1为int类型，因为short、byte 型在进行数字运算时，会自动转换为int,所以i-1返回一个int类型值。
执行 set.remove(i-1)时，i-1会自动装箱为Integer对象。虽然一个Short类型对象和一个Integer类型对象的值可能相等，但是它们的类型不同，所以比较时认为对象不相等，因此这里的remove操作其实都不成功，因为set中不存在元素i-1,所以没有删除任何对象，同时编译器不报错。
综上所述，该段代码的实质是，set中加入了10个元素，每一个都成功添加没有被删除，所以输出大小结果为10。
特别提示：
对于泛型集合HashSet<E>的add和remove方法，add()方法传递的参数类型一定要和Set中定义的类型一致，否则会报编译错误；但是remove()方法的参数类型是Objeet，所以可以接受任何类型，不会报编译错误。
TreeSet
TreeSet 是java.util 包中的类，也实现了Set接口，因此TreeSet中同样不能有重复元素。TreeSet 封装了TreeMap,所以是一个有序的容器，容器内的元素是排好序的。
关于TreeSet,有以下几点需要说明：
① TreeSet 中的元素是一个有序的集合（在插入元素时会进行排序），不允许放入null值。
② TreeSet 是非线程安全的。
③ 向TreeSet 中添加新的对象时，TreeSet 会将添加对象和已有对象进行比较，存在重复对象则不进行添加，不存在重复对象的情况下，新插入对象和已有对象根据比较结果排序再进行存储。
TreeSet 是如何保证元素有序的？
TreeSet 底层数据结构是一种自平衡的二叉搜索树，即红黑树。红黑树保证了元素的有序性，TreeSet 是按照红黑树的结点进行存储和取出数据的。
注意：
HashSet中元素的无序和LinkedHashSet中元素按照插入的顺序有序是指向容器中插入元素的顺序是否与遍历顺序一致。例如，向一个HashSet中顺序插入元素a、b、c,而遍历 HashSet时访问元素的顺序就不一定是a、b、c了，这叫作不保证遍历顺序和插入顺序一致。而TreeSet 中元素的有序是指元素按照CompareTo(Object obj)方法来比较元素之间大小关系后的顺序进行的排序，它与按照插入的顺序有序不是一个概念。
LinkedHashSet
LinkedHashSet 类是HashSet 的子类，它的元素也是唯一的，LinkedHashSet 是基于 HashMap和双向链表的实现类。LinkedHashSet 与HashSet 相比，它底层是用双向链表实现，用链表记录数据，实现了按照插入的顺序有序，也就是说，遍历顺序和插人顺序是一致的。LinkedHashSet在迭代访问Set 中全部元素时性能会比HashSet好，但插人元素时性能不如 HashSet.
Map 集合
HashMap 和 Hashtable 是Map接口的主要实现类。
HashMap
HashMap 又称为哈希表，它是根据键key的 hashCode值来存储数据的它存储的是键值对（key-value)映射，具有快速定位的特点。HashMap 继承于 AbstractMap,实现了Map等接口。它的实现是不同步的，因此不是线程安全的。它的key、value 都可以为null,而key最多只能出现一个 null。同时 HashMap 中的映射不是有序的（存储序不等于插入序）。
HashMap 的主要方法总结：
添加元素
public V put(K key,V value)：向 HashMap 中插入结点＜key,value>,若key已经存在，则覆盖相同key的结点。
public void putAll(Map<?extends K,?extends V>m)：将指定的map m中的＜key,value>插入HashMap 中。
删除元素
public V remove(Object key)：移除key指定的键值对＜key,value>。
查找元素
public V get(Object key)：返回键key对应的值 value。
final Entry<K,V> getEntry(Object key)：根据键key查找键值对。
public boolean containsKey(Object key)：判断是否包含键key指定的键值对。
public boolean contains Value(Object value)：判断是否包含 value 对应的键值对。
其他方法
public int size()：返回哈希表中键值对个数。
public Set<Map.Entry<K,V>>entrySet()：返回一个键值对集合。
HashMap 的数据结构：
HashMap 的数据结构是由数组＋链表＋红黑树来实现的。HashMap 底层是一个数组Entry[] table,数组中的每个元素Entry都是一个单项链表的引用，从JDK1.8开始，当链表长度大于8时，链表会调整为红黑树结构。
从JDK1.8开始，HashMap 为什么要引入红黑树结构？
HashMap 采用数组和链表相结合的数据结构，底层是一个数组，每个数组元素都是一个链表结构，链表的每个结点就是HashMap 中的每个元素（键值对）。当要向 HashMap 中添加一个键值对时，会先调用该键值对的key的 hashCode()方法计算出 hashCode值，从而得到该元素在数组中的下标。如果数组在该位置上已保存有元素（已存在一个链表），则说明发生了冲突（不同的key值对应了同一个hash值，所以映射的数组下标也相同），接下来就要按照HashMap 冲突管理算法进行处理。
HashMap 采用链地址法，即用单链表将所有冲突的元素链接起来，通过这种方法来进行冲突管理。但是这个链表并不会无限地增长，当链表中元素个数大于8时，这个链表会自动转为红黑树结构。之所以引入红黑树结构是因为在链表中查找每个元素的时间复杂度都是O(n),而在红黑树中查找元素的时间复杂度为O(logn),这样当HashMap 中元素量较多并产生了大量Hash 冲突时，红黑树的快速增删改查的特点能提高 HashMap 的性能。
红黑树（Red Black Tree)是一种自平衡二叉查找树，它是在1972年由 Rudolf Bayer 发明的。红黑树用红色和黑色来标记结点，并且有以下三个特点：
① 根和叶子结点都是黑色的。
② 从每个叶子到根的所有路径上不能有两个连续的红色结点。
③ 从任一结点到它所能到达的叶子结点的所有简单路径都包含相同数目的黑色结点。
以上三个特性保证了红黑树比其他的二叉查找树有更好的结点查找稳定性、查找效率和增删结点时的效率。鉴于以上原因，引入了红黑树来解决HashMap 的哈希冲突效率等问题。
红黑树结构这么好，为什么在元素个数小于8时还要用链表，而不直接使用红黑树？
当元素数目较少时，链表的效率更高，而红黑树的实现和调整都更复杂，反而会影响整体性能。
HashMap 对象的两个重要属性和扩容：
HashMap 对象的两个重要属性：初始容量和加载因子。初始容量是指 HashMap 在创建时的容量，加载因子是 HashMap 在其容量自动增加之前可以达到多满的一种尺度。HashMap的初始容量默认值为16,默认加载因子是0.75,当 HashMap 中的元素数目超出加载因子与当前容量的乘积时，则要对该 HashMap 进行扩容操作，扩容后数组大小为当前的2倍。
HashMap 的冲突管理：
HashMap 采用“hash 算法”来决定每个元素的存储位置，当添加新的元素时，系统会调用 hashCode()方法得到一个 hashCode值，再根据这个hashCode值决定这个元素在 HashMap 中的存储位置。当不同的对象的hashCode值相同时，就出现了冲突，HashMap 采用链地址法，即用单链表将所有冲突的元素链接起来，通过这种方法来进行冲突管理。当链表的元素个数大于8时，会自动转为红黑树结构，这样会提升查询性能，把顺序搜索链表记录的时间复杂度从O(n)提高到O(logn)。
HashTable
Hashtable 类与 HashMap 类似，不同的是Hashtable是线程安全的，而且属于遗留类。需要注意的是，如果对同步性和遗留代码的兼容性没有特殊要求，建议使用HashMap类，这是因为 Hashtable 虽然有线程安全的优点，但是效率较低。Hashtable 的方法类似于HashMap。在实际应用中如果需要线程安全的场景，推荐使用 ConcurrentHashMap 代替 Hashtable。
ConcurrentHashMap
ConcurrentHashMap 和 HashMap 的定义类似，但它是线程安全的，和Hashtable相比更加细化，而且性能优势更大。学习时需要掌握ConcurrentHashMap 的加锁原理。
HashMap 和 Hashtable 的主要区别：
① HashMap 和Hashtable 是Map 接口的两个重要实现类，HashMap是Hashtable的轻量级实现。
② HashMap 是非线程安全的，Hashtable是线程安全的。
③ HashMap的键（key)和值（value)都支持null，Hashtable 键（key)和值（value)都不支持null。
④ 关于 fail-fast(快速失败）机制，HashMap 使用 Iterator 进行遍历，Iterator 迭代器支持fail-fast(快速失败）机制；而 Hashtable 用Iterator 遍历时支持 fail-fast,但是用 Enumerationr 遍历时不支持 fail-fast。
注意：
快速失效机制（fail-fast):快速失效机制fail-fast是Java容器中的一种错误检测机制。当使用迭代器迭代容器类的过程中，如果同时该容器在结构上发生改变，就有可能触发fail-fast,抛出 ConcurrentModificationException 异常。这种机制一般仅用于检测bug。
例如：当使用Iterator迭代容器类 ArrayList 时，在循环送代过程中每次调用 ArrayList的remove()方法删除元素，让容器结构发生了改变，就可能引起快速失效机制，从而抛出 ConcurrentModificationException 异常。