常用的数据结构
数组、队列、链表、散列表、树、栈、堆、图
1.Collection 和Collections 的区别？
java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。
Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。
2.修改对象A的equals方法的签名，那么使用HashMap存放这个对象实例的时候，会调用哪个equals方法？
调用的修改后的equals方法，因为HashCode调用的是对象自己的equals
3.List,Set,Map的区别
List：有序，可重复，每个元素都有一个元素索引
Set:无序，不可重复，无法查询
Map：Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。实现map的集合有：HashMap、HashTable、TreeMap、WeakHashMap。
4.List和Map的实现方式以及存储方式
List：
常用实现方式有：ArrayList和LinkedList
ArrayList 的存储方式：数组，查询快
LinkedList的存储方式：链表，插入，删除快
Set：
常用实现方式有：HashSet和TreeSet
HashSet的存储方式：哈希码算法，加入的对象需要实现hashcode（）方法，快速查找元素
TreeSet的存储方式：按序存放，想要有序就要实现Comparable接口
Map：
常用实现方式有：HashMap和TreeMap
HashMap的存储方式：哈希码算法，快速查找键值
TreeMap存储方式：对键按序存放
5.HashMap的实现原理
数组+链表+红黑树
在实例化一个hashmap后，put时先判断entry数组的大小是不是为0或者为空，如果为空。则初始化数组大小为16；当put的时候，调用判断key是不是null，如果为null则将key放在entry的0索引位置，如果不为null则调用当前类的hashcode（），得到在entry中的存放位置，如果这个位置为空，则直接将键值对直接放进去，如果不为空，则遍历里面的单链表，如果这个key已经存在，则修改value值，如果找不到，则添加在单链表的尾部。如果单链表的长度>8，则将单链表转化为红黑树存储。如果当前键值对的个数大于16*0.75=12时，就将当前数组进行扩容至32；
6.HashMap如何put数据（从HashMap源码角度讲解）？
7.HashMap的扩容操作是怎么实现的？
entry数组的默认大小是16，loadfactor的默认值是0.75，当hashmap中的元素个数超过数组大小loadFactor时，即超过12时，则将数组的大小扩容为162=32，重新计算数组中每个元素的位置。
该函数有2中使用情况：1.初始化哈希表；2.当前数组容量过小，需要扩容
针对情况1：初始化哈希表（采用指定或者使用默认值的方式）
针对情况2：若扩容前的数组容量超过最大值8，则不再扩容
针对情况2：若没有超过最大值8，就扩容为原来的2倍（左移1位）
计算新的resize上限
把每一个bucket都移动到新的bucket中去
8.HashMap在JDK1.7和JDK1.8中有哪些不同？
1.1.7采用的是数组+链表，而1.8采用的是数组+链表+红黑树；
2.1.7中采用头插法，新的节点插入到相应哈希数组的头部，由于后面的节点都需要往后让一位给头结点腾位置，很容易在过程中造成环，所以1.8才用了尾插法，当链表深度超过8时，链表升级为红黑树，避免了环；
3.1.8中resize（）方法可以用来建表和扩容，而1.7建表用inflatetable()，扩容用resize（）；
4.1.8是扩容后插入数据，1.7是先插入数据后扩容。
5.扩容机制也不一样
9.ConcurrentHashMap的实现原理
在并发编程中，hashmap可能会导致死循环，使用hashtable的情况下，给整个的entry数组上了synchronized同步锁，一次put只能一个线程进去，效率十分低下。为了线程安全，使用concurrenthashmap，它的锁分段技术将hashmap分成很多块，线程进入时，每次对相应的块上锁。
由segment数组和hashentry数组组成，Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是上面的提到的锁分离技术，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样。从上Segment的继承体系可以看出，Segment实现了ReentrantLock,也就带有锁的功能，当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进行赋值，然后进行第二次hash操作，找到相应的HashEntry的位置，这里会利用继承过来的锁的特性，在将数据插入指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去获取锁，超过指定次数就挂起，等待唤醒
10.HashTable实现原理
和HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。
Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。
Hashtable中的映射不是有序的。
Hashtable 的实例有两个参数影响其性能：初始容量 和 加载因子。
容量 是哈希表中桶 的数量，初始容量 就是哈希表创建时的容量。
在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。
加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。
通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。
加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间。
1、HashTable
Hashtable 的实例有两个参数影响其性能：初始容量 和 加载因子。
容量 是哈希表中桶 的数量，初始容量 就是哈希表创建时的容量。
在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。
加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。
通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。
加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间。
需注意的点：
1.Hashtable的默认容量为11，默认负载因子为0.75.(HashMap默认容量为16，默认负载因子也是0.75)
2.Hashtable的容量可以为任意整数，最小值为1，而HashMap的容量始终为2的n次方。
3.为避免扩容带来的性能问题，建议指定合理容量。
4.跟HashMap一样，Hashtable内部也有一个静态类叫Entry，其实是个键值对对象，保存了键和值的引用。
5.HashMap和Hashtable存储的是键值对对象，而不是单独的键或值。
1)Hashtable继承于Dictionary类，实现了Map接口。
Map是"key-value键值对"接口，Dictionary是声明了操作"键值对"函数接口的抽象类。
Dictionary是个被废弃的抽象类。
2)Hashtable是通过"拉链法"实现的哈希表。
它包括几个重要的成员变量：table, count, threshold, loadFactor, modCount。
table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。
count是Hashtable的大小，它是Hashtable保存的键值对的数量。
threshold是Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"。
loadFactor就是加载因子。
modCount是用来实现fail-fast机制的
1.Hasbtable并不允许值和键为空（null），若为空，会抛空指针。
2.HashMap计算索引的方式是h&(length-1),而Hashtable用的是模运算，效率上是低于HashMap的。
3.另外Hashtable计算索引时将hash值先与上0x7FFFFFFF,这是为了保证hash值始终为正数。
4.特别需要注意的是这个方法包括下面要讲的若干方法都加了synchronized关键字，也就意味着这个Hashtable是个线程安全的类，这也是它和HashMap最大的不同点.
11.ArrayMap和HashMap的对比
arrayMap中主要存储的数据的是两个数据，
int[] mHashes;
Object[] mArray;
mHashs中存储出的是每个key的hash值，并且在这些key的hash值在数组当中是从小到大排序的。
mArray的数组长度是mHashs的两倍，每两个元素分别是key和value，这两元素对应mHashs中的hash值。mArray的结构如下图所示。
get方法其实就是一个计算index的过程，计算出来之后如果index大于0就代表存在，直接乘以2就是对应的key的值，乘以2加1就是对应的value的值。
、HashMap和ArrayMap各自的优势
1.查找效率
HashMap因为其根据hashcode的值直接算出index，所以其查找效率是随着数组长度增大而增加的。
ArrayMap使用的是二分法查找，所以当数组长度每增加一倍时，就需要多进行一次判断，效率下降。
所以对于Map数量比较大的情况下，推荐使用
2.扩容数量
HashMap初始值16个长度，每次扩容的时候，直接申请双倍的数组空间。
ArrayMap每次扩容的时候，如果size长度大于8时申请size*1.5个长度，大于4小于8时申请8个，小于4时申请4个。
这样比较ArrayMap其实是申请了更少的内存空间，但是扩容的频率会更高。因此，如果当数据量比较大的时候，还是使用HashMap更合适，因为其扩容的次数要比ArrayMap少很多。
3.扩容效率
HashMap每次扩容的时候时重新计算每个数组成员的位置，然后放到新的位置。
ArrayMap则是直接使用System.arraycopy。
所以效率上肯定是ArrayMap更占优势。
这里需要说明一下，网上有一种传闻说因为ArrayMap使用System.arraycopy更省内存空间，这一点我真的没有看出来。arraycopy也是把老的数组的对象一个一个的赋给新的数组。当然效率上肯定arraycopy更高，因为是直接调用的c层的代码。
4.内存耗费
以ArrayMap采用了一种独特的方式，能够重复的利用因为数据扩容而遗留下来的数组空间，方便下一个ArrayMap的使用。而HashMap没有这种设计。
由于ArrayMap只缓存了长度是4和8的时候，所以如果频繁的使用到Map，而且数据量都比较小的时候，ArrayMap无疑是相当的节省内存的。
5.总结
综上所述，
数据量比较小，并且需要频繁的使用Map存储数据的时候，推荐使用ArrayMap。
而数据量比较大的时候，则推荐使用HashMap。
12.HashMap和HashTable的区别
1.hashmap中key/value可以为null，但是hashtable不可以。、
2.hashmap线程不安全，hashtable线程安全
3.hashtable初始容量是11，且hashcode要与。。。保持所有哈希值为正数
13.HashMap与HashSet的区别
14.集合Set实现Hash怎么防止碰撞
1.开放地址法：哈希值相同，根据一个伪随机探测序列，进行重定hash
2.链地址法：哈希值相同用链表存
3.再哈希法：对冲突对象进行多次hash，直到不冲突
15.数组和链表的区别
数组的优点：随机访问性强、查找速度快
数组的缺点：插入和删除效率低、可能浪费内存、内存空间要求高，必须有足够的连续内存空间、数组大小固定，不能动态拓展
链表的优点：插入删除速度快、内存利用率高，不会浪费内存、大小没有固定，拓展很灵活。
链表的缺点：不能随机查找，必须从第一个开始遍历，查找效率低
16.Array和ArrayList有何区别？什么时候更适合用Array
Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。 Array 大小是固定的，ArrayList 的大小是动态变化的。
ArrayList 提供了更多的方法和特性，比如:addAll()，removeAll()，iterator()等等。 对于基本类型数据，集合 使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。
17.EnumSet是什么？
18.Comparable和Comparator接口有何区别？
Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。而Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。
Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。
两种方法各有优劣， 用Comparable 简单， 只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。 用Comparator 的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了。
19.Java集合的快速失败机制 “fail-fast”？
fail-fast(快速失败)，是Java集合的一种错误检测机制。当在遍历集合的过程中该集合在结构(改变集合大小)上发生变化时候，
有可能发生fail-fast，抛出java.util.ConcurrentModificationException异常。
迭代器在使用的时候会对数组的结构状态给一个标志位，如果中途数组的结构改变了，则数组结构的标志位相应改变，迭代器再进行下一次操作前获知标志位改变，直接报错。
20.fail-fast 与 fail-safe 之间的区别？
fail-safe任何对集合结构的修改都会在一个复制的集合上进行修改，因此不会抛出ConcurrentModificationException
fail-safe机制有两个问题
（1）需要复制集合，产生大量的无效对象，开销大
（2）无法保证读取的数据是目前原始数据结构中的数据。
21.BlockingQueue是什么？
阻塞队列，顾名思义，首先它是一个队列，在多线程领域：所谓阻塞，在某些情况下会挂起线程（即阻塞），一旦条件满足，被挂起的线程又会自动被唤醒。
BlockingQueue的两个常见阻塞场景：
当队列中没有数据的情况下，消费者端的所有线程都会被自动阻塞（挂起），直到有数据放入队列。
当队列中填满数据的情况下，生产者端的所有线程都会被自动阻塞（挂起），直到队列中有空的位置，线程被自动唤醒。
22.Iterator类有什么作用
迭代器是迭代的集合内部内容，而不是按照索引迭代
23.poll()方法和remove()方法区别？
poll() 和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。
24.JAVA8的ConcurrentHashMap为什么放弃了分段锁，有什么问题吗，如果你来设计，你如何设计。
通过 JDK 的源码和官方文档看来， 他们认为的弃用分段锁的原因由以下几点：
1.加入多个分段锁浪费内存空间。
2.生产环境中， map 在放入时竞争同一个锁的概率非常小，分段锁反而会造成更新等操作的长时间等待。
3.为了提高 GC 的效率
既然弃用了分段锁， 那么一定由新的线程安全方案， 我们来看看源码是怎么解决线程安全的呢？（源码保留了segment 代码， 但并没有使用）
put
首先通过 hash 找到对应链表过后， 查看是否是第一个object， 如果是， 直接用cas原则插入，无需加锁。
然后， 如果不是链表第一个object， 则直接用链表第一个object加锁，这里加的锁是synchronized，虽然效率不如 ReentrantLock， 但节约了空间，这里会一直用第一个object为锁， 直到重新计算map大小， 比如扩容或者操作了第一个object为止。
为什么是synchronized，而不是ReentranLock
- 减少内存开销
假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。 - 获得JVM的支持
可重入锁毕竟是API这个级别的，后续的性能优化空间很小。
synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。
京公网安备 11010502036488号