03-15 09:57 阅读 112

Java集合知识总结（持续更新和修改）

集合

我们都知道数组可以用来存放多个数据，但数组的长度一经初始化后就不可变，不适合在数据量未知的情况下使用。

而集合就是Java中用来存储对象的长度可变的容器，可以在大多数情况下使用。

Connection

Connection接口是是类集中保存单值的最基本的接口，里面每次操作的时候都只能保存一个对象的数据。

其定义了15个抽象方法，用以提供规范。较常用的有

boolean add(E e); \\向集合中插入元素

Iterator<E> iterator(); \\为 Iterator 接口实例化

void clear(); \\清空集合中的元素

int size(); \\求出集合中元素的个数

boolean contains(Object o); \\查找一个元素是否存在

boolean isEmpty(); \\判断集合是否为空

remove(Object o); \\从集合中删除一个元素

int size(); \\求出集合中元素的个数

Object[] toArray(); \\以对象数组的形式返回集合中的全部内容

T[] toArray(T[] a); \\按适当顺序返回包含此列表中所有元素的数组，返回数组的运行时类型

List

List接口继承了Connection接口，并对Connection进行了扩充；List代表了一个内容有序，可重复的集合。

扩充的常用方法有

void add(int index,E element); \\在指定位置处增加元素

boolean addAll(int index,Collection<? extends E> c); \\在指定位置处，将Connection中所有的元素插入到此列表中

E get(int index); \\返回此列表指定位置上的元素

int indexOf(Object o); \\返回此列表首次出现指定对象的索引，如果此列表不包含该对象，则返回-1

int lastIndexOf(Object o); \\返回此列表最后一次出现指定对象的索引，如果此列表不包含该对象，则返回-1

ListIterator<E> listIterator(); \\返回 ListIterator 接口的实例

E remove(int index); \\删除列表中指定位置的内容

E set(int index,E element);\\根据指定位置取内容，只有 List 接口才有定义，其他的任何接口都没有任何的定义。

List<E> subList(int fromIndex,int toIndex); \\返回子列表

ArrayList

ArrayList 是一个动态数组容器，继承了 AbstractList 类，实现List接口和Connection接口。

其存储内容在内存是连续存放的，对于增加删除的操作速度慢，查找快，线程不安全，相比于List接口，增加的方法有

String toStirng();

Protected void removeRange(int fromIndex, int toindex); \\移除列表中索引在fromIndex（包括）和toIndex（不包括）之间所有的元素

void trimToSize(); \\将此ArrayList实例的容量调整为列表的当前大小

Object clone(); \\返回此 ArrayList实例的浅表副本

void ensureCapacity(int minCapacity); \\如有必要增加此ArrayList实例的容量，以确保它至少可以容纳由最小容量参数指定的元素数

1.7和1.8版本Arraylist初始区别？

1.7及以前初始化时，要调用this(10)才是真正的容量为10；

1.8后，通过无参构造器初始化时，底层默认赋值一个空数组，长度为0，只有真正对数据进行add时，才分配默认初始容量10。

增删慢的原因？

新增和删除都是在copy一个新数组。

新增一个元素和删除一个元素都需要复制在其后面的所有元素，如果再涉及到扩容（新增时），效率就更低了。

如果插入或删除的元素离数组末端比较近，执行速度就比较快。

ArrayList (int intialCapacity) 会不会初始化数组大小?

1.会初始化数组大小，但是List的大小没有变，因为list的大小是返回size的。

2.在调用add()之前，list的size值为0，调用set()方法，会抛出数组下标越界的异常。

ArrayList适合做什么数据结构？

由于ArrayList的增删操作会涉及到数组数据的搬迁，所以ArrayList比较适合做堆栈，不适合做队列。

Vector

Vector和ArrayList在用法上几乎完全相同,但它是线程安全的。其默认容量增量为0，需指定扩容增量，否则翻一番。

Vector 属于 Java 元老级的操作类，是最早的提供了动态对象数组的操作类，在 JDK 1.0 的时候就已经推出了此类的使用，只是后来在 JDK 1.2 之后引入了 Java 类集合框架

LinkedList

LinkedList底层是双向链表结构，对于增加删除速度快，查找慢，可以用来模拟队列，线程不安全。

ArrayList的遍历和LinkedList遍历性能比较？

ArrayList的遍历效率大于LinkedList。ArrayList中的元素在内存里是连续存放的，而LinkedList的元素在内存中的存放不是连续的；CPU的内部缓存结构会缓存连续的内存片段，从而可以大幅降低内存的性能开销，因此ArrayList的遍历速度更快。

Set

Set接口也是Connection的子接口，与List接口最大的不同在于，Set接口里面的内容是不可重复的。Set接口下有三个重要的实现类，分别是HashSet，LinkedHashSet 和 TreeSet，它们都是线程不安全的。Set接口中所使用的方法都是Connection接口定义而来的。

HashSet

HashSet底层是通过哈希表实现的，即通过哈希算法来存储，并通过hashCode方法和equals方法（判断两个元素是否相等）来实现元素的唯一性（去重）。因此HashSet里面的元素是无序的，但HashSet有良好的存取和查找性能（查找时，直接通过计算对象哈希值，找对匹配项取出即可）

注意： HashSet里的对象不能通过“==”判等，必须通过equals方法判断相等。且当向HashSet中添加可变对象时，必须十分小心，因为修改HashSet集合中的对象，有可能导致该对象与集合中其他对象相等，从而导致HashSet无法准确访问该对象。

LinkedHashSet

LinkedHashSet继承自HashSet类，底层是通过链表加哈希表实现的，由链表来保证元素添加的有序（FIFO插入有序），由哈希表来去重，保证元素的唯一性。LinkedHashSet和HashSet允许存在null的数据。

TreeSet

TreeSet底层是通过红黑树实现的，故TreeSet中的元素是有序排列的。这种排序是先通过自然排序或比较器排序，然后调用内部排序规则。TreeSet是允许存入null数据的。

自然排序：1.存入TreeSet中的对象的类要实现Comparable接口。

2.重写Comparable接口中的compareTo(T o)方法

比较器排序：1.自定义比较类实现Comparator接口

2.重写Comparator接口的compare(T o1,T o2)方法

常用方法：

Object first(); //返回集合中的第一个元素。

Object last(); //返回集合中的最后一个元素。

Object lower(Object e); //返回集合中位于指定元素之前的元素

Object higher(Object e); //返回集合中位于指定元素之后的元素

SortedSet<E> subSet(E fromElement，E toElement)；//返回此Set的子集，范围从fromElement(包含大于等于）到toElement(不包含小于）

SortedSet<E> headSet(E toElement); //返回此Set的子集，由小于toElement的元素组成。

SortedSet<E> tailSet(E fromElement); //返回此Set的子集，由大于或等于fromElement的元素组成。

三者比较中，HashSet插入数据的速度快，LinkedHashSet其次，TreeSet最慢。

Iterator

只要是碰到了集合，则输出的时候想都不想就使用 Iterator 进行输出。

Iterator属于迭代输出接口，其基本原理是不断判断是否有下一个元素，有的话，则直接输出。想要使用此接口，就必须先使用Collection接口。此接口下定义了3个方法：

boolean hashNext(); //判断是否有下一个元素

E next(); //取出下一个元素的内容

void Remove(); //删除当前内容

/**

*通过 Collection 接口为其进行实例化之后，一定要记住，Iterator 中的操作指针是在第一条元素之上，当调用 next()方

*法的时候，将当前指针向下移动并获取指针的值，使用 hasNext()可以检查序列中是否还有元素。

*在进行迭代输出时，不能使用集合的remove()方法，否则可能出现未知错误

**/

ListIterator

ListIterator是Iterator的子接口，可以进行双向输出的迭代接口；要想使用ListIterator接口，就必须先将List接口实例化。

此接口定义了以下操作方法：

void add(E e); //增加元素

boolean hasPrevious(); //判断是否有前一个元素

E previous(); //取出前一个元素

void set(E e); //修改元素的内容

int previousIndex(); //前一个索引位置

int nextIndex(); //获取后一个位置的索引

//注意：如果想要进行由后向前的输出，首先必须进行由前往后的输出。

Map

Map接口是操作键值对对象的接口，即里面的内容是以key->value的形式保存的。其重要实现类有：HashMap，TreeMap，HashTable，ConcurrentHashMap。此接口定义了以下常用方法

void clear(); //清空Map集合中的内容

boolean containsKey(Object key);//判断Map中是否存在指定的key

boolean containsValue(Object value);//判断Map中是否存在指定的value

Set<Map.Entry<K,V>> entrySet(); //将 Map 接口变为 Set 集合

V get(Object key); //根据 key 找到其对应的 value

boolean isEmpty(); //判断是否为空

Set<K> keySet(); //将全部的 key 变为 Set 集合

Collection<V> values(); // 将全部的value 变为 Collection 集合

V put(K key,V value); // 向Map集合增加内容

void putAll(Map<? extends K,? extends V> m); //增加一组集合

V remove(Object key); //根据key删除内容

HashMap

HashMap是一个无序存放键值对的集合。

HashMap的底层数据结构？

1.7: 数组 + 链表

1.8：数组 + 链表 + 红黑树

注意：当哈希桶数据量（链表长度）大于等于8时，会从链表转为红黑树；当哈希桶中的数据量减少到6时，会从红黑树转为链表。

HashMap的存取原理？

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NOFAGqN1-1615619415737)(D:\Desktop\1.png)]

在HashMap的数组的每一个地方都存入了向Key-Value这样的实例，在Java7中叫Entry，在Java8中叫Node。首先，在put的时候，会根据插入的对象的key值通过hash计算一个index值，如果该Index下已经有元素，就会在该索引值下形成链表，将新元素插入到链表中。所以每一个节点都会保存自身的hash、key、value、以及下个节点。

Java7和Java8的区别？

Java7时节点插入链表的时候用的是头插法，Java8后就改为尾部插入了。

因为使用头插法在HashMap扩容的时候，会改变原来链表中节点的引用关系，在多线程操作时可能会引起死循环。

而使用尾插法在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

为啥会线程不安全？

JDK1.7时，多线程环境下，HashMap扩容会造成死循环和数据丢失。

JDK1.8时，多线程环境下，HashMap在进行put操作时，会发生数据覆盖的情况。

有什么线程安全的类可以代替吗？

1.使用Collections.synchronizedMap(Map)创建线程安全的map集合

2.HashTable

3.可以用ConcurrentHashMap代替。

6. 默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？

```java

// 默认初始化大小为16

之所以选择16，是为了服务将Key映射到index的算法；同时也是为了位运算方便（位运算比算术运算计算的效率高很多）。其次我们要尽可能得到一个均匀分布的hash,是我们通过Key的HashCode值与数组长度减1去做位运算。而这样子得到的运算效果与取模一样，性能也提升了不少。

//因为在使用2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，计算的hash结果等同于HashCode后几位的值。

//只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

//这是为了实现均匀分布。

//如果用户制定了初始容量，那么HashMap也会计算出比该数大的第一个2的幂作为初始容量。

HashMap的扩容方式？负载因子是多少？为什么是这么多？

//HashMap的扩容机制有两个步骤：

1. 创建一个新的Entry空数组，长度是原数组的2倍。

2.ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。//数组长度扩大后hash规则也随之改变（进行位运算结果可能不同）

//负载因子：0.75f

eg:比如当前的哈希桶的数量为100个，当你要使用第76个哈希桶的时候，就会判断发现需要进行Resize了。

//为什么是0.75

这是一个经验性结果，通过大量数据测试出来的。负载因子越大，越节省空间，但查找效率也更低；负载因子越小，越浪费空间，但查找效率越高。创建HashMap时，要指定合适的初始容量（最好是2的幂）

HashMap的主要参数都有哪些？

//默认HashMap集合初始容量(必须是2的倍数)

static final int DEFAULT_INITIAL_CAPCITY = 1 << 4;

//默认填充因子

static final int DEFAULT_LOAD_FACTOR = 0.75f;

//当桶（bucket）的节点大于等于这个值时会转成红黑树（JDK1.8新增）

static final int TREEIFY_THRESHOLD = 8;

//当桶（bucket）的节点小于等于这个值时会转链表（JDK1.8新增）

static final int UNTREEIFY_THRESHOLD = 6;

//调整下一个值大小（容量*负载因子）

int threshold;

HashMap是怎么处理hash碰撞的？

HashMap是通过链地址法来处理hash冲突的。

hash的计算规则？

index = HashCode（Key） & （Length- 1）

TreeMap

TreeMap是由红黑树实现的有序的key-value集合。其本身操作的时候按照key进行排序。另外，key 中的内容可以为任意的对象，但是要求对象所在的类必须实现 Comparable 接口。

注意：在添加元素初始化TreeMap构造函数时，没有传递Comparator类，是不允许插入 key==null的键值对，相反，如果实现了Comparator接口，则可以传递key == null的键值对。

排序规则：

1.如果比较器不为空（即构造时传递了Comparator类），那么在插入时按照Comparator实现的类进行排序。

2.否则，按照key实现的Comparable接口排序。

HashTable

HashTable的底层实现和数据操作方法与HashMap类似。接下来简单探讨一下它们的区别：

HashTable是线程安全的，其方式是在对所有数据操作的方法上加synchronized锁，因此效率较低；而HashMap不是线程安全的。

HashTable允许将key和value值设置为null（否则会抛出NullPointerException）,而HashMap允许将key和value值设置为null。

HashTable初始容量为11，扩容：newSize = oldSize2 + 1；HashMap初始容量为16，扩容：newSize = oldSize2 。

HashTable计算index值：index = (hash & 0x7FFFFFFF) % tab.length；HashMap计算index值：index = hash & (tab.length – 1)。

Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类

相同：

二者底层都是数组+链表实现的。

它们的迭代器都是快速失败机制的（fail-fast),即在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

ConcurrentHashMap

————————————————

原文链接：https://blog.csdn.net/qq_45888459/article/details/114747939