数据结构

1、List,Set,Map的区别？

List:  1.可以允许重复的对象。

          2.可以插入多个null元素。

          3.是一个有序的容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。

          4.常用的实现类有ArrayList、LinkedList和Vector。ArrayList是数组实现，可以根据索引随机访问，LinkedList的实现是双向链表，添加和删除的场景比较适合。平常工作中用到ArrayList比较多。

Set: 1.不允许集合中有重复对象，一般我们会用集合过滤重复元素。

          2.无序容器，它是一个集合。但是TreeSet可以是实现排序顺序，其原理主要是通过Comparator或者Comparable来维护其的有序性。

            3.只允许且唯一null元素

Map: 1.Map的每个Entry都持有两个对象，也就是一个键和一个值，Map可能会持有相同的值对象，但键对象必须唯一。

         2.Map有且仅有一个null键，null值可以随意。

List 和Set是collection的子接口，Map则不是。

2、List和Map的实现方式以及存储方式

List: ArrayList 数组 LinkedList双向链表

Map: HashMap 键值存储： 数组 + 链表

3、HashMap的实现原理

HashMap的主干是一个Entry数组，Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对，Entry是HashMap里面的一个静态内部类。HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值，在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组

initialCapacity默认为16，loadFactory默认为0.75

4、Hash的数据结构？

数组+链表

5、HashMap源码的理解

6、HashMap如何put数据（从HashMap源码角度讲解）？

1.如果tables数组为空时先创键属猪，并且设置扩容阈值；

2.如果key为空时，调用putForNullKey方法处理；

3.计算key的哈希值

4.根据第三步计算出来的哈希值和当前数组的长度来计算得到该key在数组中的索引，其实索引最后的值就等于hash % table.length;

5.遍历该数组索引下的整条链表，如果之前已经有一样的key,那么直接覆盖value;

6.如果该key之前没有，那么久进入addEntry方法。

7、HashMap怎样手写实现

第一，HashMap有3个要素：hash函数+数组+单链表

第二，对于hash函数而言，需要考虑些什么？

要快，对于给定的Key，要能够快速计算出在数组中的index。那么什么运算够快呢？显然是位运算！

要均匀分布，要较少碰撞。说白了，我们希望通过hash函数，让数据均匀分布在数组中，不希望大量数据发生碰撞，导致链表过长。那么怎么办到呢？也是利用位运算，通过对数据的二进制的位进行移动，让hash函数得到的数据散列开来，从而减低了碰撞的概率。

如果发生了碰撞怎么办？上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的，就是通过单链表解决的。那么除了这个方法，还有其他思路么？比如说，如果发生冲突，那么记下这个冲突的位置为index，然后在加上固定步长，即index+step，找到这个位置，看一下是否仍然冲突，如果继续冲突，那么按照这个思路，继续加上固定步长。其实这就是所谓的线性探测来解决Hash冲突的方法！

8、ConcurrentHashMap的实现原理

众所周知，哈希表是中非常高效，复杂度为O(1)的数据结构，在Java开发中，我们最常见到最频繁使用的就是HashMap和HashTable，但是在线程竞争激烈的并发场景中使用都不够合理。

HashMap ：先说HashMap，HashMap是线程不安全的，在并发环境下，可能会形成环状链表（扩容时可能造成，具体原因自行百度google或查看源码分析），导致get操作时，cpu空转，所以，在并发环境中使用HashMap是非常危险的。

HashTable ： HashTable和HashMap的实现原理几乎一样，差别无非是1.HashTable不允许key和value为null；2.HashTable是线程安全的。但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

HashTable性能差主要是由于所有操作需要竞争同一把锁，而如果容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这样便可以有效地提高并发效率。这就是ConcurrentHashMap所采用的"分段锁"思想。

9、ArrayMap和HashMap的对比

ArrayMap是一个<key,value>映射的数据结构，它设计上更多的是考虑内存的优化，内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值，它和SparseArray一样，也会对key使用二分法进行从小到大排序，在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作，所以，应用场景和SparseArray的一样，如果在数据量比较大的情况下，那么它的性能将退化至少50%。

HashMap内部是使用一个默认容量为16的数组来存储数据的，而数组中每一个元素却又是一个链表的头结点，所以，更准确的来说，HashMap内部存储结构是使用哈希表的拉链结构（数组+链表），这种存储数据的方法叫做拉链法 。

在此补充一个知识点，处理hash冲突的方法有以下几种：

开放地址法

再哈希法

链地址法

建立公共溢出区

ArrayMap应用场景

1.数据量不大，最好在千级以内

2.数据结构类型为Map类型

10、HashTable实现的原理

Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。

Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。

Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。此外，Hashtable中的映射不是有序的。

HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。