说说List,Set,Map三者的区别？
- List(对付顺序的好帮手)： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象
- Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。
- Map(用Key来搜索的专家): 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。
Arraylist
Java的动态数组
以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10
每次扩容大概是之前容量的1.5倍左右
//我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//右移一位相当于/2，是奇数的化会丢掉小数
Arraylist 与 LinkedList 区别?
1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全
2. 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构
3. 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以对于add(�E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O（1），如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
5. 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。
ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢？
Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。（其实就是加个Synchronized）
Arraylist不是同步的，所以在不需要保证线程安全时建议使用Arraylist。
HashMap
-
HashMap结构
hashmap.put("1","2") // entry--->key--->--->hash--->index会把key, value包装成一个entry对象，entry里面还需next属性。
-
为什么HashMap里数组的容量必须是2的幂次方
求数组下标： hashcode 与数组length-1 与操作
eg： length=16
0000 1111 与hashcode与操作后，得到的值会从0-15,符合我们的要求。
但如果数组容量是17
0001 0000 与hashcode与操作后，得到的值要么是0，要么是16，其它空间都浪费了。
- JDK1.8为什么不用链表了
链表查询（get）效率太低
其实还是用的，当链表长度增加大于等于8时，将采用红黑树。
当链表长度（删除） 小于6时，改回链表。
- 为什么用红黑树，不用完全平衡二叉树
AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树。
但平衡AVL树可能需要O（log n）旋转，而红黑树将需要最多两次旋转使其达到平衡(所以AVL插入复杂度更高)
- JDK1.7是头插法，1.8是尾插法
主要原因在于并发执行put操作时，可能会造成元素之间会形成一个循环链表，导致死循环。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。
HashSet
HashSet 底层就是基于 HashMap 实现的.
| HashMap | HashSet |
|---|---|
| 实现了Map接口 | 实现Set接口 |
| 存储键值对 | 仅存储对象 |
调用 put（）向map中添加元素 | 调用 add（）方法向Set中添加元素 |
| HashMap使用键（Key）计算Hashcode | HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性， |
HashSet如何检查重复
当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。
HashSet使用不当会导致内存泄漏
修改hashset中对象的属性值，且属性值是计算哈希值的字段，这时会引起内存泄漏
即：当一个对象被存储进HashSet集合中以后，就不能修改该对象的参与计算哈希值的属性值了
，否则对象修改后的哈希值与最初存储进HashSet集合中时的哈希值就不同了，在这种情况下，即使在contains方法使用该对象的当前引用作为参数去HashSet集合中检索对象，也将返回找不到对象的结果，这也会导致无法从HashSet集合中删除当前对象，造成内存泄露。
hashCode（）与equals（）的相关规定：
- 如果两个对象相等，则hashcode一定也是相同的
- 两个对象相等,对两个equals方法返回true
- 两个对象有相同的hashcode值，它们也不一定是相等的
- 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
- hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。
自己理解：equls返回为true,则两者的hashcode一定相等，意即相等的对象必须具有相等的哈希码。每当equals方法被覆写，通常需要重写hashCode方法。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//hashcode如果不同，短路，就会直接加入到hashset,hashmap
/*如果没有重写Person类的hashcode方法，那么
Set<Person> set = new HashSet<>();可能会出现同一个Person
*/
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
hashcode有啥用
hashcode是用来快速查找的，如果你学过数据结构就应该知道，在查找和排序这一章有例如内存中有这样的位置0 1 2 3 4 5 6 7 而我有个类，这个类有个字段叫ID,我要把这个类存放在以上8个位置之一，如果不用hashcode而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。但如果用hashcode那就会使效率提高很多。我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID％8，然后把我们的类存放在取得得余数那个位置。比如我们的ID为9，9除8的余数为1，那么我们就把该类存在1这个位置，如果ID是13，求得的余数是5，那么我们就把该类放在5这个位置。这样，以后在查找该类时就可以通过ID除 8求余数直接找到存放的位置了。2.但是如果两个类有相同的hashcode怎么办那（我们假设上面的类的ID不是唯一的），例如9除以8和17除以8的余数都是1，那么这是不是合法的，回答是：可以这样。那么如何判断呢？在这个时候就需要定义 equals了。也就是说，我们先通过 hashcode来判断两个类是否存放某个桶里，但这个桶里可能有很多类，那么我们就需要再通过 equals 来在这个桶里找到我们要的类。
==与equals
- ==既可以比较基本类型(比较值是否相等)， 也可以比较引用类型(比较地址是否相等)
- equals本身是object类的方法，如果没有被重写，比较的是地址；被重写后，有可能比较的是值(String)
为什么HashSet里value不是null?
value是一个final修饰的、值为null的Object对象。
private static final Object PRESENT = new Object();
如果value是null,而HashSet的remove是使用HashMap实现,则是map.remove
而map的移除会返回value,如果底层value都是存null,显然将无法分辨是否移除成功.因为没找到也返回null
TreeMap && LinkedHashMap(有序的map)
红黑树,继承自map,有序
| 名称 | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| 共同点 | 线程不安全 | 线程不安全 | 线程不安全 |
| 不同点 | 数据无序 | 数据有序（存储顺序） | 数据有序还可以对数据进行排序 |
| 数据结构 | 数组+链表+红黑树 | 双向链表+HashMap | 红黑树 |
HashTable是线程安全的，HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）另外，HashTable 基本被淘汰，不要在代码中使用它。
HashMap 和 Hashtable 的区别
- 线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过
synchronized修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）； - 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
- 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。
- 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。
- 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
ConcurrentHashMap 和 Hashtable 的区别
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
-
底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
-
实现线程安全的方式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
HashTable:
JDK1.7的ConcurrentHashMap：
JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）：
ConcurrentHashMap线程安全的具体实现方式/底层具体实现
JDK1.7（上面有示意图）
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。
JDK1.8 （上面有示意图）
ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))）
synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
JDK 提供的并发容器总结
JDK 提供的这些容器大部分在 java.util.concurrent 包中。
- ConcurrentHashMap: 线程安全的 HashMap
- CopyOnWriteArrayList: 线程安全的 List，在读多写少的场合性能非常好，远远好于 Vector.
- ConcurrentLinkedQueue: 高效的并发队列，使用链表实现。可以看做一个线程安全的 LinkedList，这是一个非阻塞队列。
- BlockingQueue: 这是一个接口，JDK 内部通过链表、数组等方式实现了这个接口。表示阻塞队列，非常适合用于作为数据共享的通道。
- ConcurrentSkipListMap: 跳表的实现。这是一个 Map，使用跳表的数据结构进行快速查找。
常见面试题总结
1.ArrayList和HashMap扩容机制
ArrayList: 初始容量为10，不够用的时候扩容约1.5倍。NewLength=OldLength+OldLength>>1
HashMap: 初始容量为16，添加元素时，如果超过加载因子，则先扩容（新建）一个2倍大小的新hashmap
2.为什么HashMap加载因子是0.75？
因为加载因子太小，会浪费空间，rehash次数变多。
加载因子太大，碰撞次数会变多。所以0.75是一个提高空间利用率和减少查询成本的折中。
评论区