2、集合

2.1常见的数据结构（了解）

常用的数据结构有：数组，栈，队列，链表，树，散列，堆，图等

数组是最常用的数据结构，数组的特点是长度固定，数组的大小固定后就无法扩容了 ，数组只能存储一种类型的数据 ，添加，删除的操作慢，因为要移动其他的元素。
栈是一种基于先进后出（FILO）的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
队列是一种基于先进先出（FIFO）的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先被读取出来。
链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结节（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构等等。有二叉树、平衡树、红黑树、B树、B+树。
散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
堆是计算机学科中一类特殊的数据结构的统称，堆通常可以被看作是一棵完全二叉树的数组对象。
图的定义：图是由一组顶点和一组能够将两个顶点相连的边组成的

2.2集合和数组的区别（了解）

区别：数组长度固定 集合长度可变
数组中存储的是同一种数据类型的元素，可以存储基本数据类型，也可以存储引用数据类型；
集合存储的都是对象，而且对象的数据类型可以不一致。在开发当中一般当对象较多的时候，使用集合来存储对象。

2.3List 和 Map、Set 的区别（必会）

List和Set是存储单列数据的集合，Map是存储键值对这样的双列数据的集合；
List中存储的数据是有顺序的，并且值允许重复；
Map中存储的数据是无序的，它的键是不允许重复的，但是值是允许重复的；
Set中存储的数据是无顺序的，并且不允许重复，但元素在集合中的位置是由元素的hashcode决定，即位置是固定的（Set集合是根据hashcode来进行数据存储的，所以位置是固定的，但是这个位置不是用户可以控制的，所以对于用户来说set中的元素还是无序的）。

2.4 List 和 Map、Set 的实现类（必会）

(1)Connection接口:
List 有序,可重复
ArrayList
优点: 底层数据结构是数组，查询快，增删慢。
缺点: 线程不安全，效率高
Vector
优点: 底层数据结构是数组，查询快，增删慢。
缺点: 线程安全，效率低, 已给舍弃了
LinkedList
优点: 底层数据结构是链表，查询慢，增删快。
缺点: 线程不安全，效率高Set 无序,唯一
HashSet
底层数据结构是哈希表。(无序,唯一)
如何来保证元素唯一性?
依赖两个方法：hashCode()和equals()
LinkedHashSet
底层数据结构是链表和哈希表。(FIFO插入有序,唯一)
1.由链表保证元素有序
2.由哈希表保证元素唯一
TreeSet
底层数据结构是红黑树。(唯一，有序)
1. 如何保证元素排序的呢?
自然排序
比较器排序
2.如何保证元素唯一性的呢?
根据比较的返回值是否是0来决定
(2)Map接口有四个实现类：
HashMap
基于 hash 表的 Map 接口实现，非线程安全，高效，支持 null 值和 null 键， 线程不安全。
HashTable
线程安全，低效，不支持 null 值和 null 键；
LinkedHashMap
线程不安全，是 HashMap 的一个子类，保存了记录的插入顺序；
TreeMap
能够把它保存的记录根据键排序，默认是键值的升序排序，线程不安全。

2.5Hashmap的底层原理（高薪常问）

HashMap在JDK1.8之前的实现方式 数组+链表,
但是在JDK1.8后对HashMap进行了底层优化,改为了由 数组+链表或者数值+红黑树实现,主要的目的是提高查找效率

1. Jdk8数组+链表或者数组+红黑树实现，当链表中的元素超过了 8 个以后， 会将链表转换为红黑树，当红黑树节点 小于 等于6 时又会退化为链表。
2. 当new HashMap():底层没有创建数组，首次调用put()方法示时，底层创建长度为16的数组，jdk8底层的数组是：Node[],而非Entry[]，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍，专业术语叫做扩容，在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能.

默认的负载因子大小为0.75，数组大小为16。也就是说，默认情况下，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为216=32，即扩大一倍。

1. 在我们Java中任何对象都有hashcode，hash算法就是通过hashcode与自己进行向右位移16的异或运算。这样做是为了计算出来的hash值足够随机，足够分散，还有产生的数组下标足够随机

map.put(k,v)实现原理
（1）首先将k,v封装到Node对象当中（节点）。
（2）先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
（3）下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
map.get(k)实现原理
(1)、先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
(2)、在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。