• 集合是一个放置数据的容器准确地说是放数据对象引用的容器
• 集合存储是对象的引用，而不是对象本身
• 主要有三种集合类型：set(集）、list(列表）和map(映射)。

• 集合的特点主要有以下两点：
  • 集合用于存储对象的容器用于包装数据，对象较多也需要存储集中管理。
  • 与数组对比对象的大小不确定。因为集合是可变长度。数组需要提前定义大小

• 数组是固定长度的；集合可变长度的。
• 数组可以存储基本数据类型或引用数据类型；集合只能存储引用数据类型。
• 数组存储的元素必须是相同类型的数据；集合存储的对象可以是不同类型的数据。

1. 容量自增长；
2. 提供高性能的数据结构和算法，使编码更容易，提高程序速度和质量；
3. 可以方便地扩展或重写集合，提高代码的再利用性和可操作性。
4. 通过使用JDK自带集合类可以减少代码维护和学习API成本。

• Map接口和Collection接口是所有集合框架的父接口：
  1. Collection接口的子接口包括：Set接口和List接口
  2. Map接口实现类主要包括：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
  3. Set接口实现类主要包括：HashSet、TreeSet、LinkedHashSet等
  4. List接口实现类主要包括：ArrayList、LinkedList、Stack以及Vector等

• Java 容器分为 Collection 和 Map 两大类，Collection集合子接口有Set、List、Queue三种子接 口。我们常用的是口。Set、List，Map接口不是collection的子接口。
• Collection集合主要有List和Set两大接口
  • List：一个有序的容器(元素存储和集合的顺序与取出的顺序一致)，元素可以重复并插入更多 个null元素，元素都有索引。常用的实现类 ArrayList、LinkedList 和 Vector。
  • Set：无序容器(存储和取出的顺序可能不一致)不能存储重复元素，只允许存储一个 个null元素，必须保证元素的唯一性。Set 常用的接口实现类是 HashSet、LinkedHashSet 以及TreeSet。
• Map是键值对集，存储键，值与之间的映射。 Key无序，唯一；value 不要求有序，允许重 复。Map没有继承于Collection接口，从Map集中检索元素时，只需给予键对象，就会返回对应 的值对象。
  • Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

• Collection
  1. List * Arraylist： Object数组 * Vector： Object数组 * LinkedList： 双向循环链表
  2. Set * HashSet（无序，唯一）：基于 HashMap 实现的，底层采用 HashMap 来保存元素 * LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。 * TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)
• Map
  • HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是 主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较 大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
  • LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散 列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加 了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的 操作，实现了访问顺序相关逻辑。
  • HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突 而存在的
  • TreeMap： 红黑树（自平衡的排序二叉树）

• 是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。
• 例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时 候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这 个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
• 原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集 合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next() 遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍 历；否则抛出异常，终止遍历。
• 解决办法：

1. 在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
2. 使用CopyOnWriteArrayList来替换ArrayList

• 可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变 集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。
• 示例代码如下：

List<String> list = new ArrayList<>();
list. add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
clist. add("y"); // 运行时此行报错
System. out. println(list. size());

• Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来 获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程 中移除元素。
• 因为所有Collection接继承了Iterator迭代器

public interface Collection<E> extends Iterable<E>{ 
        
	// Query Operations
}

• Iterator 使用代码如下：

	List<String> list = new ArrayList<>();
	Iterator<String> it = list. iterator();
	while(it. hasNext()){ 
        
		String obj = it. next();
		System. out. println(obj);
	}

• Iterator 的特点是只能单向遍历，但是更加安全，因为它可以确保，在当前遍历的集合元素被更改 的时候，就会抛出 ConcurrentModificationException 异常。

边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法，如下：

	Iterator<Integer> it = list.iterator();
	while(it.hasNext()){ 
        
		*// do something*
		it.remove();
	}

一种最常见的错误代码如下：

	for(Integer i : list){ 
        
		list.remove(i)
	}

• 运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integer i : list)) 语句时，会自动生成一个iterator 来遍历该 list，但同时该 list 正在被 Iterator.remove() 修改。Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它。

• Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List。
• Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前/后遍历）。
• ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元 素、获取前面或后面元素的索引位置。

• 遍历方式有以下几种：
  1. for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。
  2. 迭代器遍历，Iterator。Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。
  3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明Iterator 或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。
• 最佳实践：Java Collections 框架中提供了一个 RandomAccess 接口，用来标记 List 实现是否支 持 Random Access。
  • 如果一个数据集合实现了该接口，就意味着它支持 Random Access，按位置读取元素的平均 时间复杂度为 O(1)，如ArrayList。
  • 如果没有实现该接口，表示不支持 Random Access，如LinkedList。
  • 推荐的做法就是，支持 Random Access 的列表可用 for 循环遍历，否则建议用 Iterator 或foreach 遍历。

• ArrayList的优点如下：
  • ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快。
  • ArrayList 在顺序添加一个元素的时候非常方便。
• ArrayList 的缺点如下：
  • 删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
  • 插入元素的时候，也需要做一次元素复制操作，缺点同上。
• ArrayList 比较适合顺序添加、随机访问的场景。

• 数组转 List：使用 Arrays. asList(array) 进行转换。
• List 转数组：使用 List 自带的 toArray() 方法。
• 代码示例：

	// list to array
	List<String> list = new ArrayList<String>();
	list.add("123");
	list.add("456");
	list.toArray();
	// array to list
	String[] array = new String[]{ 
        "123","456"};
	Arrays.asList(array);

• 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
• 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
• 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为ArrayList 增删操作要影响数组内的其他数据的下标。
• 内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
• 线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
• 综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。
• LinkedList 的双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

• 这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合
  • 线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
  • 性能：ArrayList 在性能方面要优于 Vector。
  • 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。
• Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
• Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。

• ArrayList、Vector、LinkedList 的存储性能和特性？ ArrayList和Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。
• Vector 中的方法由于加了 synchronized 修饰，因此 Vector 是线程安全容器，但性能上较ArrayList差。
• LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以 LinkedList 插入速度较快。

ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样：

	List<String> synchronizedList = Collections.synchronizedList(list);
	synchronizedList.add("aaa");
	synchronizedList.add("bbb");
	for (int i = 0; i < synchronizedList.size(); i++) { 
        
		System.out.println(synchronizedList.get(i));
	}

• ArrayList 中的数组定义如下： private transient Object[] elementData;
• 再看一下 ArrayList 的定义：

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

• 可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化，重写了 writeObject 实现：

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ 
        
	// Write out element count, and any hidden stuff
	int expectedModCount = modCount;
	s.defaultWriteObject();
	// Write out array length
	s.writeInt(elementData.length);
	// Write out all elements in the proper order.
	for (int i=0; i<size; i++)
		s.writeObject(elementData[i]);
	if (modCount != expectedModCount) { 
        
		throw new ConcurrentModificationException();
}

• 每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。

• List , Set 都是继承自Collection 接口
• List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
• Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及TreeSet。
• 另外 List 支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。
• Set和List对比
  • Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
  • List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变

• HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为present，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层HashMap 的相关方法来完成，HashSet 不允许重复的值。

• 向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles 方法比较。
• HashSet 中的add ()方法会使用HashMap 的put()方法。
• HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。所以不会重复（HashMap 比较key是否相等是先比较hashcode 再比较equals ）。
• 以下是HashSet 部分源码：

	private static final Object PRESENT = new Object();
	private transient HashMap<E,Object> map;
	public HashSet() { 
        
		map = new HashMap<>();
	}
	public boolean add(E e) { 
        
		// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
		return map.put(e, PRESENT)==null;
	}

hashCode（）与equals（）的相关规定：

1. 如果两个对象相等，则hashcode一定也是相同的 * hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值
2. 两个对象相等,对两个equals方法返回true
3. 两个对象有相同的hashcode值，它们也不一定是相等的
4. 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个 对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与equals的区别

1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较

• 哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值。

• 链表是可以将物理地址上不连续的数据连接起来，通过指针来对物理地址进行操作，实现增删改查 等功能。
• 链表大致分为单链表和双向链表
  1. 单链表:每个节点包含两部分,一部分存放数据变量的data,另一部分是指向下一节点的next指针
  2. 双向链表:除了包含单链表的部分,还增加的pre前一个节点的指针
• 链表的优点
  • 插入删除速度快（因为有next指针指向其下一个节点，通过改变指针的指向可以方便的增加删除元素）
  • 内存利用率高，不会浪费内存（可以使用内存中细小的不连续空间（大于node节点的大小），并且在需要空间的时候才创建空间）
  • 大小没有固定，拓展很灵活。
• 链表的缺点
  • 不能随机查找，必须从第一个开始遍历，查找效率低

• HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

• HashMap的数据结构： 在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

• HashMap 基于 Hash 算法实现的

  1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
  2. 存储时，如果出现hash值相同的key，此时有两种情况。 (1)如果key相同，则覆盖原始值； (2)如果key不同（出现冲突），则将当前的key-value放入链表中
  3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
  4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

• 需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)

• 在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突。

HashMap JDK1.8之前

• JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组 中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。 HashMap JDK1.8之后
• 相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8） 时，将链表转化为红黑树，以减少搜索时间。

JDK1.7 VS JDK1.8 比较

• JDK1.8主要解决或优化了一下问题：
  1. resize 扩容优化
  2. 引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考
  3. 解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。

说道红黑树先讲什么是二叉树

• 二叉树简单来说就是 每一个节上可以关联俩个子节点

大概就是这样子：
		     a
		/         \
	   b           c
	 /   \       /   \
	d     e     f     g
   / \   / \   / \   / \
  h   i j   k l   m n   o

红黑树

• 红黑树是一种特殊的二叉查找树。红黑树的每个结点上都有存储位表示结点的颜色，可以是红(Red)或黑(Black)。
• 红黑树的每个结点是黑色或者红色。当是不管怎么样他的根结点是黑色。每个叶子结点（叶子结点代表终结、结尾的节点）也是黑色 [注意：这里叶子结点，是指为空(NIL或NULL)的叶子结点！]。
• 如果一个结点是红色的，则它的子结点必须是黑色的。
• 每个结点到叶子结点NIL所经过的黑色结点的个数一样的。[确保没有一条路径会比其他路径长出俩倍，所以红黑树是相对接近平衡的二叉树的！]
• 红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的结点之后，红黑树的结构就发生了变化，可能不满足上面三条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转和变色，可以使这颗树重新成为红黑树。简单点说，旋转和变色的目的是让树保持红黑树的特性。

• 当我们put的时候，首先计算 key 的 hash 值，这里调用了 hash 方法， hash 方法实际是让key.hashCode() 与 key.hashCode()>>>16 进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标 index = (table.length - 1) & hash ，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。
• putVal方法执行流程图