数组和链表分别适用于什么场景，为什么？

数组和链表都是数据结构中常见的数据类型，它们各自适用于不同的场景。

数组

数组是一种基本的数据类型，它是一个有序的、固定大小的数据集合，其中每个元素都有一个唯一的索引。数组的优点在于它的随机访问速度非常快，因为它的元素在内存中是连续存储的，可以通过索引快速访问。

适用场景：

数组适合查询多，增删少的场景；

链表

链表是一种基于指针的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的优点在于它可以动态地添加、删除元素，不需要像数组一样预先分配固定大小的空间。

适用场景：

(1) 需要频繁插入或删除元素，因为链表的插入和删除操作只需要修改节点之间的指针，效率较高；

List和Set的区别

List：有序按对象进入的顺序保存对象可重复允许多个Null元素可以使用迭代器取出所有的元素然后再逐一遍历各个元素还可以使用get获取指定下标的元素

Set：无序不可重复最多允许一个Null元素只能使用迭代器取出所有的元素然后在逐一遍历

List和Map、Set的区别

List和Set是存储单列数据集合，Map是存储键值对这样的双列数据的集合

List中存储的数据是有序的，可以为空，并且值允许重复。

Map中存储的数据是无序的它的键不允许重复的但是值是允许重复的；可一个空键、多个空值。

Set中存储的数据是无顺序的，并且不允许重复，只有一个空元素。元素在集合的位置是由元素的hashcode决定即位置是固定的（Set集合是根据hashcode来进行数据存储的所以位置是

固定的但是这个位置不是用户可以控制的所以对于用户来说set中的元素还是无序的）

HashMap 、HashTable 和TreeMap有什么区别？

hashmap的特性

允许空键和空值（但空键只有一个，且放在第一位）
元素是无序的，而且顺序会不定时改变
key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法。
底层实现是链表数组，JDK 8 后又加了红黑树。

HashMap和HashTable有什么区别？（必会）

区别：

（1）HashMap是非线程安全的，HashTable是线程安全的，内部的方法基本都经过synchronized修饰。

（2）因为同步、哈希性能等原因，HashMap的性能优于HashTable

（3） HashMap允许有null值的存在,在HashTable不允许有null值

（4）HashMap默认初始化数组的大小为16，HashTable为11。前者扩容时乘2，使用位运算取得哈希，效率高于取模。而后者为乘2加1，都是素数和奇数，这样取模哈希结果更均匀。

JDK1.7到1.8HashMap发生了什么变化(底层)

1.7底层是数组+链表 1.8底层是数组+链表+红黑树加入红黑树的目的是提高HashMap插入和查询的整体效率

1.7链表插入使用的是头插法 1.8链表插入使用的是尾插法因为1.8插入key和value需要判断链表元素个数所以需要遍历链表统计元素个数正好使用尾插法

1.7的哈希算法比较复杂存在各种右移和与运算 1.8进行了简化因为复杂的哈希算法的目的是提高散列性来提供HashMap的整体效率而1.8中新增了红黑树所以可以适当简化哈希算法节省CPU资源。

谈谈ConcurrentHashMap的扩容机制

1.7版本

1.7版本的ConcurrentHashMap是基于Segment分段实现的
每个Segment相当于一个小型的HashMap
每个Segment内部会进行扩容和HashMap扩容逻辑类似
先生产新的数组然后转移元素到新数组中
扩容的判读也是每个Segment内部单独判断的判断是否超过阈值

1.8版本

1.8版本的ConcurrentHashMap不再基于Segment实现
当某个线程进行put时如果发现ConcurrentHashMap正在进行扩容那么该线程一起进行扩容
如果某个线程put时发现没有正在进行扩容则将key-value添加到ConcurrentHashMap中然后判断是否超过阈值超过了则进行扩容
扩容之前先生成一个新的数组
在转移元素时先将原数组分组将每组分给不同的线程进行元素的转移每个线程负责一组或多组元素转移工作

hashMap 中什么时候需要进行扩容，扩容方法 resize()又是如何实现的？

调用场景：

1.初始化数组 table

2.当数组 table 的 size 达到阙值时进行扩容

实现过程：

通过判断旧数组的容量是否大于0来判断数组是否初始化过。

l如果小于0：进行初始化,判断是否调用无参构造器。

l如果大于0: 进行扩容，扩容成两倍(小于最大值的情况下)，之后在进行将元素重新进行与运算复制到新的散列表中。

概括的讲：

扩容需要重新分配一个新数组，新数组是老数组的2倍长，然后遍历整个老结构，把所有的元素挨个重新hash分配到新结构中去。

PS：可见底层数据结构用到了数组，到最后会因为容量问题都需要进行扩容操作。

HashMap的扩容机制原理

当new HashMap():底层没有创建数组，首次调用 put()方法示时，底层创建长度为 16 的数组，jdk8 底层的数组是：Node[],而非 Entry[]，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用 rehash() 方法将数组容量增加到原来的两倍，专业术语叫做扩容。在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能. 默认的负载因子大小为 0.75，数组大小为 16。也就是说，默认情况下，那么当 HashMap中元素个数超过 16*0.75=12 的时候，就把数组的大小扩展为 2*16=32，即扩大一倍。

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

HashMap的put方法

HashMap是Java中常用的散列表数据结构，是基于 Hash 算法实现的。们通过 put(key,value)存储，get(key)来获取。当传入 key 时，HashMap 会根据 key.hashCode() 计算出 hash 值，根据 hash 值将 value 保存在 bucket里。当计算出的 hash 值相同时，我们称之为 hash 冲突，HashMap 的做法是用链表和红黑树存储相同 hash 值的 value。当 hash 冲突的个数比较少时，使用链表否则使用红黑树。

如果添加新节点后，桶中节点的数量超过了阈值（默认为0.75），则需要进行扩容操作。扩容操作会将桶的数量翻倍，并将原来的节点重新分配到新的桶中。