文章目录
1. 常见的数据结构有三种结构
1.1 各自数据结构的特点
2. HashMap
2.1 概述
2.2 底层结构
2.2.1 HashMa实现原理：
2.2.1.1 map.put(k,v)实现原理
2.2.1.2 map.get(k)实现原理
2.2.1.3 resize源码
2.2.2 HashMap常用的变量
2.2.3 HashMap构造函数
2.3 JDK1.8之前存在的问题
2.4 HashMap红黑树原理
3. 哈希表(散列)
3.1 什么是哈希表
3.2 什么是哈希冲突(面试题)
3.3 解决哈希冲突的方法(面试题)
(1) 开放地址法
① 线性探查
②二次探查
③随机探查
(2) 再哈希法
(3) 链地址法
(4)建立公共溢出区
4. HashMap
4.1 HashMap的hash()算法(面试)
(1)为什么不是h = key.hashCode()直接返回，而要 h = key.hashCode() ^ (h >>> 16)来计算哈希值呢？
(2)为什么HashMap的初始容量和扩容都是2的次幂
(3)如果指定了不是2的次幂的容量会发生什么？
4.2 HashMap为什么线程不安全(面试题)
(1) 多线程下扩容造成的死循环和数据丢失(jdk1.7)
(2)数据覆盖(jdk1.8)
4.3 HashMap解决线程不安全(面试题)
(1) 使用HashTable解决线程不安全问题(弃用)
(2)HashMap和HashTable的区别
(3)Collections.synchronizedMap(不常用)
(4)ConcurrentHashMap(常用)
4.4 为什么使用synchronized替换ReentrantLock锁呢？
4.5 HashMap底层 数组 + 链表 / 红黑树(面试题)
(1)HashMap为什么引入链表
(2)HashMap为什么引入红黑树
(3)为什么不一开始就使用红黑树
(4)说说你对红黑树的理解
(5) 红黑树为什么要变色、左旋和右旋操作
4.6 HashMap链表和红黑树转换(面试题)
(1) 为什么链表长度大于8，并且表的长度大于64的时候，链表会转换成红黑树？
(2) 为什么转成红黑树是8呢？而重新转为链表阈值是6呢？
(3) 为什么负载因子是0.75？
4.6 HashMap扩容(面试题)
(1)什么时候会发生扩容？
(2)为什么不是满了扩容？
(3)扩容过程
数组结构
链表结构
哈希表结构
1.1 各自数据结构的特点
数组结构： 存储区间连续、内存占用严重、空间复杂度大
优点：随机读取和修改效率高，原因是数组是连续的（随机访问性强，查找速度快）
缺点：插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中都要往后移动，且大小固定不易动态扩展。
链表结构：存储区间离散、占用内存宽松、空间复杂度小
优点：插入删除速度快，内存利用率高，没有固定大小，扩展灵活
缺点：不能随机查找，每次都是从第一个开始遍历（查询效率低）
哈希表结构：结合数组结构和链表结构的优点，从而实现了查询和修改效率高，插入和删除效率也高的一种数据结构
2.1 概述
HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用NULL建和NULL值，因为key允许重复，因此只能有一个建为null，另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的。
2.2 底层结构
HashMap底层采用哈希表结构（JDK1.8之前为数组+链表、JDK1.8之后为数组+链表+红黑树）实现，结合了数组和链表的优点：数组优点： 通过数组下标可以快速实现对数组元素的访问，效率极高；链表优点： 插入或删除数据不需要移动元素，只需修改节点引用，效率极高。HashMap内部使用数组存储数据，数组中的每个元素类型为Node<K,V>：
//Node包含了四个字段：hash、key、value、next，其中next表示链表的下一个节点。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<k,V> next; //链表的下一个节点
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey()
{ return key; }
public final V getValue()
{ return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry< , > e = (Map.Entry< , >)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
2.2.1 HashMa实现原理：
2.2.1.1 map.put(k,v)实现原理
（1）首先将k,v封装到Node对象当中（节点）。（2）然后它的底层会调用k的hashCode()方法得出hash值。（3）通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
put方法源码如下：
//put方法，会先调用一个hash()方法，得到当前key的一个hash值，
//用于确定当前key应该存放在数组的哪个下标位置
//这里的 hash方法，我们姑且先认为是key.hashCode()，其实不是的，一会儿细讲
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//把hash值和当前的key，value传入进来
//这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false
//evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一个空实现，因此不用关注这个参数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断table是否为空，如果空的话，会先调用resize扩容
if ((tab = table) == null
(n = tab.length) == 0)
n = (tab = resize()).length;
//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，
//若没有，则把key、value包装成Node节点，直接添加到此位置。
// i = (n - 1) & hash 是计算下标位置的，为什么这样算，后边讲
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果当前位置已经有元素了，分为三种情况。
Node<K,V> e; K k;
//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，
//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理
if (p.hash == hash &&
((k = p.key) == key
(key != null && key.equals(k))))
e = p;
//2.如果当前是红黑树结构，则把它加入到红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//如果头结点的下一个节点为空，则插入新节点
p.next = newNode(hash, key, value, null);
//如果在插入的过程中，链表长度超过了8，则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//插入成功之后，跳出循环，跳转到①处
break;
}
//若在链表中找到了相同key的话，直接退出循环，跳转到①处
if (e.hash == hash &&
((k = e.key) == key
(key != null && key.equals(k))))
break;
p = e;
}
}
//①
//说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值
if (e != null) { // existing mapping for key
V oldValue = e.value;
//用新值替换旧值，并返回旧值。
if (!onlyIfAbsent
oldValue == null)
e.value = value;
//看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，
//只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能
// Callbacks to allow LinkedHashMap post-actions
//void afterNodeAccess(Node<K,V> p) { }
afterNodeAccess(e);
return oldValue;
}
}
//fail-fast机制
++modCount;
//如果当前数组中的元素个数超过阈值，则扩容
if (++size > threshold)
resize();
//同样的空实现
afterNodeInsertion(evict);
return null;
}
put方法通过hash函数计算key对应的哈希值，hash函数源码如下：
static final int hash(Object key) {
int h;
return (key == null)
0 : (h = key.hashCode()) ^ (h >>> 16);
}
2.2.1.2 map.get(k)实现原理
(1)先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。(2)通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。
get操作源码：
public V get(Object key) {
Node<K,V> e;
//如果节点为空，则返回null，否则返回节点的value。这也说明，hashMap是支持value为null的。
//因此，我们就明白了，为什么hashMap支持Key和value都为null
return (e = getNode(hash(key), key)) == null
null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//首先要确保数组不能为空，然后取到当前hash值计算出来的下标位置的第一个元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//若hash值和key都相等，则说明我们要找的就是第一个元素，直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key
(key != null && key.equals(k))))
return first;
//如果不是的话，就遍历当前链表（或红黑树）
if ((e = first.next) != null) {
//如果是红黑树结构，则找到当前key所在的节点位置
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果是普通链表，则向后遍历查找，直到找到或者遍历到链表末尾为止。
do {
if (e.hash == hash &&
((k = e.key) == key
(key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//否则，说明没有找到，返回null
return null;
}
2.2.1.3 resize源码
通过put源码分析我们知道，数组的初始化和扩容都是通过调用resize方法完成的：
final Node<K,V>[] resize() {
//旧数组
Node<K,V>[] oldTab = table;
//旧数组的容量
int oldCap = (oldTab == null)
0 : oldTab.length;
//旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到。
int oldThr = threshold;
//初始化新数组的容量和阈值，分三种情况讨论。
int newCap, newThr = 0;
//1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0。
//为什么这样说呢，之前我在 tableSizeFor 卖了个关子，需要注意的是，它返回的值是赋给了 threshold 而不是 capacity。
//我们在这之前，压根就没有在任何地方看到过，它给 capacity 赋初始值。
if (oldCap > 0) {
//容量达到了最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新数组的容量和阈值都扩大原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//2.到这里，说明 oldCap <= 0，并且 oldThr(threshold) > 0，这就是 map 初始化的时候，第一次调用 resize的情况
//而 oldThr的值等于 threshold，此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例)。
//因此，需要把 oldThr 的值，也就是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2的n次幂。
//所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值（2的n次幂)
//但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对。别着急，这个会在③处理。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//3.到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的，
//于是，数组的容量和阈值都取默认值就可以了，即 16 和 12。
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//③ 这里就是处理第2种情况，因为只有这种情况 newThr 才为0，
//因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12） ，并把它赋值给 threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY
(int)ft : Integer.MAX_VALUE);
}
//赋予 threshold 正确的值，表示数组下次需要扩容的阈值（此时就把原来的 16 修正为了 12）。
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//我们可以发现，在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候，才会把数组创建出来。这是为了延迟加载，提高效率。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果原来的数组不为空，那么我们就需要把原来数组中的元素重新分配到新的数组中
//如果是第2种情况，由于是第一次调用resize，此时数组肯定是空的，因此也就不需要重新分配元素。
if (oldTab != null) {
//遍历旧数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//取到当前下标的第一个元素，如果存在，则分三种情况重新分配位置
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//1.如果当前元素的下一个元素为空，则说明此处只有一个元素
//则直接用它的hash()值和新数组的容量取模就可以了，得到新的下标位置。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//2.如果是红黑树结构，则拆分红黑树，必要时有可能退化为链表
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//3.到这里说明，这是一个长度大于 1 的普通链表，则需要计算并
//判断当前位置的链表是否需要移动到新的位置
else { // preserve order
// loHead 和 loTail 分别代表链表旧位置的头尾节点
Node<K,V> loHead = null, loTail = null;
// hiHead 和 hiTail 分别代表链表移动到新位置的头尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//如果当前元素的hash值和oldCap做与运算为0，则原位置不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//否则，需要移动到新的位置
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//原位置不变的一条链表，数组下标不变
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//移动到新位置的一条链表，数组下标为原下标加上旧数组的容量
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
2.2.2 HashMap常用的变量
//默认的初始化容量为16，必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。
//为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。
//若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，
//若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
//当红黑树上的元素个数，减少到6个时，就退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。
//这是为了避免，数组扩容和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;
//存放所有Node节点的数组
transient Node<K,V>[] table;
//存放所有的键值对
transient Set<Map.Entry<K,V>> entrySet;
//map中的实际键值对个数，即数组中元素个数
transient int size;
//每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。
//当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。
transient int modCount;
//数组扩容阈值
int threshold;
//加载因子
final float loadFactor;
//普通单向链表节点类
static class Node<K,V> implements Map.Entry<K,V> {
//key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置
final int hash;
final K key;
V value;
//指向单链表的下一个节点
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
//转化为红黑树的节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//当前节点的父节点
TreeNode<K,V> parent;
//左孩子节点
TreeNode<K,V> left;
//右孩子节点
TreeNode<K,V> right;
//指向前一个节点
TreeNode<K,V> prev;
// needed to unlink next upon deletion
//当前节点是红色或者黑色的标识
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//返回当前节点的根节点
final TreeNode<k,v> root() {
for (TreeNode<k,v> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
2.2.3 HashMap构造函数
HashMap有四个构造函数可供我们使用：
//默认无参构造，指定一个默认的加载因子
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//可指定容量的有参构造，但是需要注意当前我们指定的容量并不一定就是实际的容量，下面会说
public HashMap(int initialCapacity) {
//同样使用默认加载因子
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//可指定容量和加载因子，但是笔者不建议自己手动指定非0.75的加载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0
Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//这里就是把我们指定的容量改为一个大于它的的最小的2次幂值，如传过来的容量是14，则返回16
//注意这里，按理说返回的值应该赋值给 capacity，即保证数组容量总是2的n次幂，为什么这里赋值给了 threshold 呢？
//先卖个关子，等到 resize 的时候再说
this.threshold = tableSizeFor(initialCapacity);
}
//可传入一个已有的map
public HashMap(Map<
extends K,
extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//把传入的map里边的元素都加载到当前map
final void putMapEntries(Map<
extends K,
extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY)
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<
extends K,
extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//put方法的具体实现，后边讲
putVal(hash(key), key, value, false, evict);
}
}
}
tableSizeFor()上边的第三个构造函数中，调用了 tableSizeFor 方法，这个方法是怎么实现的呢？
static final int tableSizeFor(int cap) {
int n = cap - 1;
n
= n >>> 1;
n
= n >>> 2;
n
= n >>> 4;
n
= n >>> 8;
n
= n >>> 16;
return (n < 0)
1 : (n >= MAXIMUM_CAPACITY)
MAXIMUM_CAPACITY : n + 1;
}
可以看到这个方法是针对整型数据进行的操作！int n = cap - 1;不知道为什么要减去1，实际上这只是针对二的整数幂进行的退位操作
先单独看这段代码：
假设 n = 5时
n
= n >>> 1;
0000 0101
0000 0010
0000 0111
n
= n >>> 2;
0000 0111
0000 0001
0000 0111
n
= n >>> 4;
0000 0111
0000 0000
0000 0111
...
最后无符号右移再或等结果都是
0000 0111
这样就得到了5最高非0位下的最大值
即 0000 0111
对其加一的结果就是 0000 1000
即大于5的最小二的整数幂 8
其实这个算法的思路就是将该数字的最高非0位后面全置为1！其利用了“拷贝”的方式：
n=
;
1000 0000
0000 0000
0000 0000
0000 0000
n
= n >>> 1;
1100 0000
0000 0000
0000 0000
0000 0000
将最高位拷贝到下1位
n
= n >>> 2;
1111 0000
0000 0000
0000 0000
0000 0000
将上述2位拷贝到紧接着的2位
n
= n >>> 4;
1111 1111
0000 0000
0000 0000
0000 0000
将上述4位拷贝到紧接着的4位
n
= n >>> 8;
1111 1111
1111 1111
0000 0000
0000 0000
将上述8位拷贝到紧接着的8位
n
= n >>> 16; 1111 1111
1111 1111
1111 1111
1111 1111
将上述16位拷贝到紧接着的16位
由上面可以看出其通过这五次的计算，最后的结果刚好可以填满32位的空间，也就是一个int类型的空间，这就是为什么必须是int类型，且最多只无符号右移16位！
return (n < 0)
1 : (n >= MAXIMUM_CAPACITY)
MAXIMUM_CAPACITY : n + 1;
其中的MAXIMUM_CAPACITY 是HashMap的最大空间为1 << 30，即2^30刚好一个G，所以HashMap大小不是取决于堆内存！
为什么要减一：
以 n = 8为例
0000 1000
最后的结果为：
0000 1111
对其加一得到的是16，显然没有把自身包含进去
若减一
n = 7
0000 0111
最后的结果为：
0000 0111
对其加一得到的是8
所以在一开始进行减一的操作是为了防止出现二的整数幂时，没有把自身包含进范围！
2.3 JDK1.8之前存在的问题
JDK1.8之前，HashMap底层实现用的是数组+链表。（JDK1.8以后用数组+链表+红黑树）。
HashMap通过hash方法计算key的哈希码，然后通过（n-1）&hash 公式（n为数组长度,初始化数组默认长度为16），得到key在数组中存放的下标。
当两个key在数组中存在的下标一致时（哈希冲突，哈希碰撞），数据将以链表的方式存储。
在链表中查找数据必须从第一个元素开始一层一层往下找，直到找到为止，时间复杂度为O(N)，所以当链表长度越来越长时，HashMap的效率越来越低。
2.4 HashMap红黑树原理
红黑树除了插入操作慢，其他操作都比链表快，当hash表的单一链表长度超过 8 个的时候，数组长度大于64，链表结构就会转为红黑树结构。当红黑树上的节点数量小于6个，会重新把红黑树变成单向链表数据结构。为什么要这样设计呢？好处就是避免在最极端的情况下链表变得很长很长，在查询的时候，效率会非常慢。红黑树查询：其访问性能近似于折半查找，时间复杂度 O(logn)；
链表查询：这种情况下，需要遍历全部元素才行，时间复杂度 O(n)；
简单的说，红黑树是一种近似平衡的二叉查找树，其主要的优点就是“平衡“，即左右子树高度几乎一致，以此来防止树退化为链表，通过这种方式来保障查找的时间复杂度为 log(n)。关于红黑树的内容，网上给出的内容非常多，主要有以下几个特性：1、每个节点要么是红色，要么是黑色，但根节点永远是黑色的；2、每个红色节点的两个子节点一定都是黑色；3、红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）；4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；5、所有的叶子节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件 3 或条件 4，需要通过调整使得查找树重新满足红黑树的条件。
3.1 什么是哈希表
根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数H(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash)表，函数H(key)为哈希(Hash)函数。
3.2 什么是哈希冲突(面试题)
根据一定的规则放进存放哈希值的数组中，然后下标为1的数组已经有值了，后面根据规则，判定某个数也需要放到下标为1的数组中，这样就导致了只有一个位置两个人都要坐，就引起了冲突。(不同的key值产生的H(key)是一样的)。
3.3 解决哈希冲突的方法(面试题)
(1) 开放地址法
插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。
Hi=(H(key)+di)%m
//开放地址法计算下标公式
Hi：下标(储存的地址)
H(key)：哈希函数(计算哈希值)
di：增量
%：取模
m：哈希表的长度
探查方法如下
① 线性探查
di=1,2,3,…m-1；冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
②二次探查
di=1^2, -1^2, 2^2, -2^2 …k^2, -k^2,(k<=m/2)； 冲突发生时，在表的左右进行跳跃式探测，比较灵活。
③随机探查
di=伪随机数序列；冲突发生时，建立一个伪随机数发生器（如i=(i+p) % m），p是质数(在m范围取得质数)，生成一个伪随机序列，并给定一个随机数做起点，每次加上伪随机数++就行。
为了更好的理解，我们举一个例子
设哈希表长为14，哈希函数为H(key)=key%11。表中现有数据15、38、61和84，其余位置为空，如果用二次探测再散列处理冲突，则49的位置是？使用线性探测法位置是？
解：因为H(key)=key%11
所以15的位置 = 15 % 11=4; 38的位置 = 38 % 11=5; 61的位置 = 61 % 11=6; 84的位置 = 84 % 11=7;(证明哈希表4,5,6,7已经有元素)
因为计算下标的公式为：Hi=(H(key)+di)mod%m
使用二次探测法
H(1) = (49%11 + 1^1) = 6;冲突
H(-1) = (49%11 + (-1^2)) = 4;冲突
注意 -1^2 = -1; (-1)^2 = 1;
H(2) = (49%11 + 2^2) = 9;不冲突
二次探测法49的位置就是哈希表的9。
使用线性探测
H(1) = (49%11 + 1) = 6;冲突
H(2) = (49%11 + 2) = 7;冲突
H(3) = (49%11 + 3) = 8;不冲突
线性探测法49的位置就是哈希表的8。
(2) 再哈希法
再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
(3) 链地址法
每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。比如 66和88这两个元素哈希值都是1，这就发生了哈希冲突，采用链地址法，可以把 66和88放在同一个链表中。如下图
(4)建立公共溢出区
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
4.1 HashMap的hash()算法(面试)
(1)为什么不是h = key.hashCode()直接返回，而要 h = key.hashCode() ^ (h >>> 16)来计算哈希值呢？
回答：减少哈希冲突
//源码：计算哈希值的方法 H(key)
static final int hash(Object key) {
int h;
return (key == null)
0 : (h = key.hashCode()) ^ (h >>> 16);
}
//^ (异或运算) 相同的二进制数位上，数字相同，结果为0，不同为1。
举例如下：
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 1 = 0
1 ^ 0 = 1
// &(与运算)
相同的二进制数位上，都是1的时候，结果为1，否则为零。 举例如下：
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
h = key.hashCode() ^ (h >>> 16)意思是先获得key的哈希值h，然后 h 和 h右移十六位做异或运算，运算结果再和数组长度 -
1进行与运算，计算出储存下标的位置。具体原理如下：
综下所述 储存下标 = 哈希值 & 数组长度 - 1
//jdk1.7中计算数组下标的HashMap源码
static int indexFor(int h, int length) {
//计算储存元素的数组下标
return h & (length-1);
}
//jdk1.8中去掉了indexFor()函数，改为如下
i = (n - 1) & hash //i就是元素存储的数组下标
某个key的哈希值为 ：1111 1111 1110 1111 0101 0101 0111 0101，数组初始长度也是16，如果没有 ^ h >>> 16，计算下标如下
1111 1111 1110 1111 0101 0101 0111 0101
//h = hashcode()
&
0000 0000 0000 0000 0000 0000 0000 1111
//数组长度 - 1 = 15 (15的二进制就是 1111)
------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101
//key的储存下标为5
由上面可知，只相当于取了后面几位进行运算，所以哈希冲突的可能大大增加。
以上条件不变，加上异或h >>> 16，之后在进行下标计算
1111 1111 1110 1111 0101 0101 0111 0101
//h = hashcode()
^
0000 0000 0000 0000 1111 1111 1110 1111
//h >>> 16
------------------------------------------
1111 1111 1110 1111 1010 1010 1001 1010
//h = key.hashCode() ^ (h >>> 16)
&
0000 0000 0000 0000 0000 0000 0000 1111
//数组长度 - 1 = 15 (15的二进制就是 1111)
------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1010
//key的存储下标为10
重要：由上可知，因为哈希值得高16位和低16位进行异或运算，混合之后的哈希值，低位也可能掺杂了高位的一部分特性(就是变化性增加了)，这样就减少了哈希冲突。
(2)为什么HashMap的初始容量和扩容都是2的次幂
回答：也是为了减少哈希冲突。
原理：因为判断储存位置的下标为 ：i = (n - 1) & hash，n就是数组的长度。2的次幂 - 1，其二进制都是1，比如 2^4 -1= 15(1111)，2^5-1 = 31(11111)。因为n-1和hash进行与运算，只有 1 & 1 ，才为1。因为n-1永远是2的次幂-1，(n - 1) & hash的结果就是 hash的低位的值。
1111 1111 1110 1111 0101 0101 0111 0101
//hash值
&
0000 0000 0000 0000 0000 0000 0000 1111
//数组长度 - 1 = 15 (15的二进制就是 1111)
------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101
//高位全部清零，只保留末四位(就相当于保留了hash的低位)
如果容量不是2次幂会怎么样呢？如下图表
2次幂的时候，数组长度为16，n-1 = 16 -1 = 15(1111)
hash
(n-1) & hash
储存下标
0
1111 & 0000
0
1
1111 & 0001
1
2
1111 & 0010
2
3
1111 & 0011
3
4
1111 & 0100
4
5
1111 & 0101
5
非2次幂的时候，数组长度为10，n-1 = 10 -1 = 9(1001)
hash
(n-1) & hash
储存下标
0
1001 & 0000
0
1
1001 & 0001
1
2
1001 & 0010
0
3
1001 & 0011
1
4
1001 & 0100
0
5
1001 & 0101
1
重要：由上看出，n为2的次幂，哈希冲突会更少，保证元素的均匀插入。
(3)如果指定了不是2的次幂的容量会发生什么？
回答：会获得一个大于指定的初始值的最接近2的次幂的值作为初始容量。比如：输入 9 获得 16，输入 5 获得 8。原理如下：
static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子
static final int MAXIMUM_CAPACITY = 1 << 30;//初始容量最大为 2的30次方
/**
* @param initialCapacity 初始容量
*/
public HashMap(int initialCapacity) {
//此处通过把第二个参数负载因子使用默认值0.75f，然后调用有两个参数的构造方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用函数一
}
/**
* 函数一
* @param initialCapacity 初始容量
* @param loadFactor
负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
//如果初始容量小于0，抛出异常
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
//如果初始容量超过最大容量（1<<30）
initialCapacity = MAXIMUM_CAPACITY;
//则使用最大容量作为初始容量
if (loadFactor <= 0
Float.isNaN(loadFactor))
//如果负载因子小于等于0或者不是数字，则抛出异常
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//把负载因子赋值给成员变量loadFactor
//调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果，并赋给成员变量threshold
this.threshold = tableSizeFor(initialCapacity); //调用函数二
}
/**
* 函数二
* @param cap 初始容量
*/
static final int tableSizeFor(int cap) { //这里我们假设我们初始容量是 10
//容量减1，为了防止初始化容量已经是2的幂的情况，在最后有n+1的操作。
n = 10 - 1 = 9
int n = cap - 1;
//n = (n
n >>> 1) 带入得
n = (1001
0100) = 1101
n
= n >>> 1;
//n = (n
n >>> 2) 带入得
n = (1101
0011) = 1111
n
= n >>> 2;
//n = (n
n >>> 4) 带入得
n = (1111
0000) = 1111
n
= n >>> 4;
//n = (n
n >>> 8) 带入得
n = (1111
0000) = 1111
n
= n >>> 8;
//n = (n
n >>> 16) 带入得
n = (1111
0000) = 1111 = 15
n
= n >>> 16;
/**
如果入参cap为小于或等于0的数，那么经过cap-1之后n为负数，n经过无符号右移和或操作后仍未负数,
所以如果n<0,则返回1;如果n大于或等于最大容量，则返回最大容量;否则返回n+1。
n = 15 + 1 = 16，咱们传进来是初始容量10，会自动转为16容量。
**/
return (n < 0)
1 : (n >= MAXIMUM_CAPACITY)
MAXIMUM_CAPACITY : n + 1;
//return (n < 0)
1 : (n >= MAXIMUM_CAPACITY)
MAXIMUM_CAPACITY : n + 1;相当于下面这段代码
if(n < 0){
return 1;
}else{
if(n >= MAXIMUM_CAPACITY){
return MAXIMUM_CAPACITY;
}else{
return n + 1;
}
}
}
4.2 HashMap为什么线程不安全(面试题)
(1) 多线程下扩容造成的死循环和数据丢失(jdk1.7)
在jdk1.7中，链表采用的是头插法(每次插入节点都是从头插入)。
① 假设这里有两个线程同时执行了put()操作(扩容)，并进入了transfer()方法。线程A先进行操作② 线程A在执行到newTable[i] = e后被挂起，因为newTable[i] = null,又因为 e.next = newTable[i]，所以e.next = null
transfer()方法部分源码：
while(null !=e)
{
Entry<K,V> next =e.next; //next = 3.next = 7
e.next = newTable[i]; //3.next = null
newTable[i] = e;//线程A执行到这里被挂起了
e = next;
}
③ 开始执行线程B，并完成了扩容。这时候 7.next = 3；3.next = null；④ 继续执行线程A，执行newTable[i] = e，因为当时 e = 3，所以将3放到对应位置，此时执行e = next，因为next = 7(第②步)，所以e = 7
while(null !=e)
{
Entry<K,V> next =e.next; //next = 3.next = 7
e.next = newTable[i]; //3.next = null
newTable[i] = e;//继续从这里执行
newTable[i] = 3
e = next; //e = 7
}
⑤ 上轮循环之后e=7，从主内存中读取e.next时发现主内存中7.next=3，此时next=3，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环。
while(null !=e)
{
Entry<K,V> next =e.next; //next = 7.next = 3
e.next = newTable[i]; //7.next = 3
newTable[i] = e;//newTable[i] = 7
e = next; //e = 3
}
⑥上轮循环7.next=3，而e=3，执行下一次循环可以发现，因为3.next=null，所以循环之后 e = null，所以循环会退出。
while(null !=e)
{
Entry<K,V> next =e.next; // next = 3.next = null
e.next = newTable[i];
//3.next = 7 (此处3指向7,同时之前7也指向了3,所以会形成闭环)
newTable[i] = e;
//newTable[i] = 3
e = next;
//e = null(退出循环条件)
}
(2)数据覆盖(jdk1.8)
jdk1.8中已经不再采用头插法，改为尾插法，即直接插入链表尾部，因此不会出现死循环和数据丢失，但是在多线程环境下仍然会有数据覆盖的问题。
当你调用put()方法时，putVal()方法里面有两处代码会产生数据覆盖。
① 假设两个线程都进行put操作，线程A和线程B通过哈希函数算出的储存下标是一致的，当线程A判断完之后，然后挂起，然后线程B判断完进入，把元素放到储存位置，然后线程A继续执行，把元素放到储存位置，因为线程A和线程B存储位置一样，所以线程A会覆盖线程B的元素。②
同样在putVal()方法里。两个线程，假设HashMap的size为15，线程A从主内存获得15，准备进行++的操作的时候，被挂起，然后线程B拿到size并执行++操作，并写回主内存，这时size是16，然后线程A继续执行(这时A线程内存size还是15)++操作，然后写回主内存，即线程A和线程B都进行了put操作，然后size值增加了1，所以数据被覆盖了。
4.3 HashMap解决线程不安全(面试题)
(1) 使用HashTable解决线程不安全问题(弃用)
因为HashTable解决线程不安全就是在其方法加上同步关键字(synchronized)，会导致效率很低下。
(2)HashMap和HashTable的区别
①线程是否安全HashMap线程不安全。HashTable线程安全，但是效率较低。
②是否nullHashMap中key只能有一个null，value可以多个为null。HashTable不允许键或值为null。
③容量HashMap底层数组长度必须为2的幂（16，32，128…），默认为16。HashTable底层数组长度可以为任意值，导致hash算法散射不均匀，容易造成hash冲突，默认为11。
④底层区别HashMap是底层由数组+链表形成，在JDK1.8之后链表长度大于8时转化为红黑树。HashTable一直都是数组+链表。
⑤继承关系HashTable继承自Dictionary类。HashMap继承自AbstractMap类。
(3)Collections.synchronizedMap(不常用)
Map<String,String> map = Collections.synchronizedMap(new HashMap<>());
可以看到SynchronizedMap 是一个实现了Map接口的代理类，该类中对Map接口中的方法使用synchronized同步关键字来保证对Map的操作是线程安全的。
(4)ConcurrentHashMap(常用)
① jdk1.7使用分段锁，底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment(锁角色) 和 HashEntry(存放键值对)。
分段锁：Segment(继承ReentrantLock来加锁)数组中，一个Segment对象就是一把锁,对应n个HashEntry数组,不同HashEntry数组的读写互不干扰。② JDK 1.8抛弃了原有的 Segment 分段锁，来保证采用Node + CAS + Synchronized来保证并发安全性。取消Segment类，直接用数组存储键值对。
4.4 为什么使用synchronized替换ReentrantLock锁呢？
① 减少内存开销。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS(队列同步器)来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。② 获得JVM的支持。可重入锁毕竟是API这个级别的，后续的性能优化空间很小。 synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。③在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
AQS：是一个队列同步器，同步队列是一个双向链表，有一个状态标志位state，如果state为1的时候，表示有线程占用，其他线程会进入同步队列等待，如果有的线程需要等待一个条件，会进入等待队列，当满足这个条件的时候才进入同步队列，ReentrantLock就是基于AQS实现的
锁升级方式：就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为CAS(compare and swap 原子操作) 轻量级锁，如果失败就会短暂自旋(不停的判断比较，看能否将值交换)，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。
偏向锁：减少无竞争且只有一个线程使用锁的情况下，使用轻量级锁产生的性能消耗。轻量级锁每次申请、释放锁都至少需要一次CAS，但偏向锁只有初始化时需要一次CAS。
轻量级锁：当有两个线程，竞争的时候就会升级为轻量级锁。轻量级锁的目标是，减少无实际竞争情况下，使用重量级锁产生的性能消耗，包括系统调用引起的内核态与用户态切换、线程阻塞造成的线程切换等。
重量级锁：大多数情况下，在同一时间点，常常有多个线程竞争同一把锁，悲观锁的方式，竞争失败的线程会不停的在阻塞及被唤醒态之间切换，代价比较大。
4.5 HashMap底层 数组 + 链表 / 红黑树(面试题)
红黑树：平衡二叉查找树
(1)HashMap为什么引入链表
因为HashMap在put()操作时，会进行哈希值得计算，算出储存下标要放在数组那个位置时，当多个元素要放在同一位置时就会出现哈希冲突，然后引进链表，把相同位置的元素放进同一个链表(链地址法)。
(2)HashMap为什么引入红黑树
因为当链表长度大于8时，链表遍历查询速度比较慢，所以引入红黑树。
(3)为什么不一开始就使用红黑树
因为树相对链表维护成本更大，红黑树在插入新数据之后，可能会通过左旋、右旋、变色来保持平衡，造成维护成本过高，故链路较短时，不适合用红黑树。
(4)说说你对红黑树的理解
红黑树是一种平衡二叉查找树，是一种数据结构。除了具备二叉查找树特性以外，还具备以下特性
1.根节点是黑色
2.节点是黑色或红色
3.每个叶子节点是黑色
4.红色节点的子节点都是黑色
5.从任意节点到其叶子节点的所有路径都包含相同数目的黑色节点补充：以上性质强制了红黑树的关键性质从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。保证了红黑树的高效。
(5) 红黑树为什么要变色、左旋和右旋操作
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。过程：先变色如果变色还不满足红黑树的性质，那就进行左旋或者右旋，然后继续变色，以此循环直至符合红黑树的性质。
4.6 HashMap链表和红黑树转换(面试题)
链表长度大于8，并且表的长度大于64 数组 + 红黑树
链表长度大于8，并且表的长度不大于64 数组 + 链表 会扩容
当数的节点小于6 数组 + 链表
(1) 为什么链表长度大于8，并且表的长度大于64的时候，链表会转换成红黑树？
因为链表长度符合泊松分布，长度越长哈希冲突概率就越小，当链表长度为8时，概率仅为 0.00000006，这时是一个千万分之一的概率，然后我们map也不会存储那么多的数据，所以链表长度不超过8没有必要转换成红黑树。如果出现这种大量数据的话，转为红黑树可以增加查询和插入效率。长度大于64，只是注释写了 最低要在 4*8，我也没弄懂，请大佬指导。原理如下：
In usages with well-distributed user hashCodes, tree bins
are rarely used.
Ideally, under random hashCodes, the
frequency of nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because
of resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:
0:
0.60653066
1:
0.30326533
2:
0.07581633
3:
0.01263606
4:
0.00157952
5:
0.00015795
6:
0.00001316
7:
0.00000094
8:
0.00000006
more: less than 1 in ten million
//翻译：更多：少于千万分之一
负载因子是0.75和长度为8转为红黑树的原理：由上面我们可以看出 当负载因子为0.75时，哈希冲突出现的频率遵循参数为0.5的泊松分布。
常数0.5是作为参数代入泊松分布来计算的，而加载因子0.75是作为一个条件。
泊松分布是一种离散概率分布，泊松分布的概率质量函数：
x=(0,1,2,...)。
λ：单位时间内随机事件的平均发生率。因为我们从上面知道平均发生率是0.5
e^(-0.5) = 0.60653065971264
//e的负0.5次方
阶乘：指从1乘以2乘以3乘以4一直乘到所要求的数。比如 3！ = 1 * 2 * 3
P(0) = (0.50 * e-0.5) / 0! ≈ 0.60653066
P(1) = (0.51 * e-0.5) / 1! ≈ 0.30326533
P(2) = (0.52 * e-0.5) / 2! ≈ 0.07581633
(2) 为什么转成红黑树是8呢？而重新转为链表阈值是6呢？
如果转为链表也是8，那如果在8这个位置发生哈希冲突，那红黑树和链表就会频繁切换，就会浪费资源。
(3) 为什么负载因子是0.75？
根据上面的泊松分布来看，表长度达到8个元素的时候，概率为0.00000006，几乎是一个不可能事件，减少了哈希冲突。
加载因子 = 填入表中的元素个数 / 散列表的长度
加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大；
加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费更多，而且还会提高扩容rehash操作的次数。
“冲突的机会”与“空间利用率”之间，寻找一种平衡与折中。
4.6 HashMap扩容(面试题)
(1)什么时候会发生扩容？
元素个数 > 数组长度 * 负载因子 例如 16 * 0.75 = 12,当元素超过12个时就会扩容。链表长度大于8并且表长小于64，也会扩容
(2)为什么不是满了扩容？
因为元素越接近数组长度，哈希冲突概率就越大，所以不是满了扩容。
(3)扩容过程
jdk1.7创建一个新的table，并调用transfer()方法把旧数组中的数据迁移到新数组中，使用的是头插法，也就是说，新table中链表的顺序和旧列表中是相反的，在HashMap线程不安全的情况下，这种头插法可能会导致死链和数据丢失现象。
jdk1.8①在resize()方法中，定义了oldCap参数，记录了原table的长度，定义了newCap参数，记录新table长度，newCap是oldCap长度的2倍，然后循环原table，把原table中的每个链表中的每个元素放入新table。②计算索引做了优化：hash（原始hash） & oldCap（原始容量） == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap（原始容量）。
注意
扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
HashMap的容量达到2的30次方，就不会在进行扩容了。

转载链接：https://blog.csdn.net/qq_54753561/article/details/122149197
使用面向对象编程时,new关键字做了什么？
新建了一个Object对象
修改构造函数this的指向，是其指向新建的Object对象，并且执行构造函数
为Object对象添加了一个proto属性，是其指向构造函数的prototype属性
将这个Object对象返回出去
es6和es5的继承（继承不用搞那么麻烦，项目中还是用 class）
原型链继承
父类的实例作为子类的原型,易于实现，父类的新增实例与属性子类都能访问，创建子类实例，不能向父类构造函数中传参数。
原型链继承
实现：
父类的实例作为子类的原型
可以在子类中增加实例属性，如果要新增加原型属性和方法需要在new 父类构造函数的后面
优点：
简单，易实现 父类的新增实例与属性子类都能访问
缺点：
无法实现多继承 创建子类实例时，不能向父类构造函数中传参数
function Person() {
this.a = true
}
Person.prototype.fn = function () {
console.log('我是父类')
}
function Son() {
this.b = false
}
这里是关键 创建 Person 的实例 然后赋值给 Son 的原型
Son.prototype = new Person()
let xiaoming = new Son()
xiaoming.fn()
console.log(xiaoming.a)
构造函数继承（伪造对象、经典继承）
不能继承原型属性/方法,可以实现多继承，可以传参，无法复用，
构造函数继承
实现：
在子类内,使用call()调用父类方法,并将父类的this修改为子类
的this.相当于是把父类的实例属性复制了一份放到子类的函数内.
优点：
解决了子类构造函数向父类构造函数中传递参数
可以实现多继承（call或者apply多个父类）
缺点：
方法都在构造函数中定义，无法复用
不能继承原型属性/方法，只能继承父类的实例属性和方法
function Father(age, name) {
this.a = '22'
}
function Children() {
Father.call(this)
}
let Class = new Children()
console.log(Class.a);
组合继承
通过call 对实例属性的继承，原型链对原型方法的继承， 调用多次
组合继承
实现：
组合上述两种方法就是组合继承。用原型链实现对原型属性和方法的继承，
借用构造函数技术来实现实例属性的继承。
缺点：
由于调用了两次父类，所以产生了两份实例
优点：
函数可以复用
不存在引用属性问题
可以继承属性和方法，并且可以继承原型的属性和方法
function Father(name) { // 这里的name 就是 Son 传过来的
this.name = name
this.colors = [1, 2]
}
Father.prototype.sayName = function () {
alert(this.name)
}
function Son(name, age) {
//继承实例属性，第一次调用Father()
Father.call(this, name) // 这里通过 call 传过去 name 继承实例属性
this.age = age
}
Son.prototype = new Father() // 继承父类方法，第二次调用 Father
Son.prototype.ff = function () { // 子类的方法
console.log('666');
}
var aa = new Son('小明', 5)
aa.colors.push(3)
console.log(aa); // 打印了 父类的属性 和方法 以及子类的方法
var bb = new Son('小红', 50)
aa.colors.push(999999)
console.log(bb); // 打印了 父类的属性 和方法 以及子类的方法
Es6有class继承:
首先利用class构造一个父类，然后利用extends与super实现子类继承
ES6类继承extends
extends关键字主要用于类声明或者类表达式中，以创建一个类，该类是另一个类的子类。其中constructor表示构造函数，一个类中只能有一个构造函数，有多个会报出SyntaxError错误,如果没有显式指定构造方法，则会添加默认的 constructor方法，使用例子如下。
class Rectangle {
// constructor
constructor(height, width) {
this.height = height;
this.width = width;
}
// Getter
get area() {
return this.calcArea()
}
// Method
calcArea() {
return this.height * this.width;
}
}
const rectangle = new Rectangle(10, 20);
console.log(rectangle.area);
// 输出 200
-----------------------------------------------------------------
// 继承
class Square extends Rectangle {
constructor(length) {
super(length, length);
// 如果子类中存在构造函数，则需要在使用“this”之前首先调用 super()。
this.name = 'Square';
}
get area() {
return this.height * this.width;
}
}
const square = new Square(10);
console.log(square.area);
// 输出 100
ES5继承和ES6继承的区别：
es5继承首先是在子类中创建自己的this指向，最后将方法添加到this中 Child.prototype=new Parent()
Parent.apply(this)
Parent.call(this) es6继承是使用class关键字先创建父类的实例对象this，最后在子类class中修改this
javascript原型与原型链
每个函数都有一个prototype属性，被称为显示原型
每个实例对象都会有_ _proto_ _属性,其被称为隐式原型
每一个实例对象的隐式原型_ _proto_ _属性指向自身构造函数的显式原型prototype
每个prototype原型都有一个constructor属性，指向它关联的构造函数。
原型链
获取对象属性时，如果对象本身没有这个属性，那就会去他的原型__proto__上去找，如果还查不到，就去找原型的原型，一直找到最 顶层(Object.prototype)为止。Object.prototype对象也有proto属性值为null。链式查找机制叫原型链。
javascript 创建对象的几种方式
1、我们一般使用字面量的形式直接创建对象 （1）第一种是工厂模式，工厂模式的主要工作原理是用函数来封装创建对象的细节，从而通过调用函数来达到复用的目的。 （2）第二种是构造函数模式。js 中每一个函数都可以作为构造函数，只要一个函数是通过 new
来调用的，那么我们就可以把它称为构造函数。 （3）第三种模式是原型模式，因为每一个函数都有一个 prototype 属性，这个属性是一个对象，它包含了通过构造函数创建的所有实例都能共享的属性和方法。 （4）第四种模式是组合使用构造函数模式和原型模式，这是创建自定义类型的最常见方式。
（5）第五种模式是动态原型模式，这一种模式将原型方法赋值的创建过程移动到了构造函数的内部，通过对属性是否存在的判断，可以实现仅在第一次调用函数时对原型对象赋值一次的效果。 （6）第六种模式是寄生构造函数模式，这一种模式和工厂模式的实现基本相同，
什么是设计模式？
概念：
设计模式是一套被反复使用的代码，设计经验的总结。使用设计模式是为了重用代码、让代码更容易被他人理解、保证代码可靠性。设计模式让代码变得工程化，设计模式是软件工程的基石。
1、js工厂模式,去做同样的事情，实现同样的效果,解决多个相似的问题这时候需要使用工厂模式 2、发布订阅模式,通过Object.defineProperty()来劫持各个属性的setter，getter，在数据变动时发布消息给订阅者，触发相应的监听回调。 3、单例模式 单例模式 保证一个类仅有一个实例，并提供一个访问它的全局访问点
constructor，proto，prototype的三角关系。
构造函数的prototype指向原型对象 实例对象的proto指向构造函数的prototype所指向原型对象 原型对象的constructor指向构造函数
面向过程，面向对象，面向过程和面向对象的优缺点
一、面向过程：面向过程就是分析出实现需求所需要的步骤，通过函数一步一步实现这些步骤，接着依次调用即可。 二、面向对象：将数据与函数绑定到一起，进行封装，这样能够更快速的开发程序，减少了重复代码的重写过程面向过程： 优点：性能上它是优于面向对象的，因为类在调用的时候需要实例化，开销过大。
缺点：不易维护、复用、扩展 用途：单片机、嵌入式开发、Linux/Unix等对性能要求较高的地方 面向对象: 面向对象有三大特性：封装，继承，多态。 优点：易维护、易复用、易扩展，由于面向对象有封装、继承、多态性的特性，可以设计出低耦合的系统，使系统更加灵活、更加易于维护 。 缺点：性能比面向过程低
spa
spa 就是我们的单页面应用，spa 应用就是只有一个html页面，在vue中可以通过vue-router 来进行页面的切换的，而非刷新整个页面，可以实现无刷新切换页面的技术 SPA的原理? 通过这一点可以用js监听url中hash值的变化 onhashchange 事件在当前 URL 的锚部分(以 '#' 号为开始) 发生改变时触发
。哈希值的变换并不会引发页面的刷新和跳转,当监听到hash变化,就可以动态的切换组件,就可以实现无刷新切换页面技术 spa 的优点？ 页面切换快： 页面每次切换跳转时，并不需要做`html`文件的请求，这样就节约了很多`http`发送时延，我们在切换页面的时候速度很快。
用户体验好： 页面片段间的切换快，在网络环境差的时候, 因为组件已经预先加载好了, 并不需要发送网络请求, 所以用户体验好 转场动画 spa 的缺点？ 首屏加载比较慢因为要请求一次html同时还要发送一次js请求，两次请求回来了首屏才会显示
不利于SEO seo 效果较差 因为搜索引擎只识别html里面的内容，并不识别js里的内容，因为单页面就是js渲染出来的，影响网站的排名
mpa
MPA多页面应用程序 指的就是有多个独立的html页面，每个页面必须重复加载html js css 资源，多页面跳转需要整个页面资源刷新。 优点 1、首屏加载速度快 当我们访问页面的时候，服务器只返回了一个html，页面就展示出来了，只发了一次http请求，所以页面显示非常快. 2、SEO效果好
因为搜索引擎在做网站排名的时候，要根据网页的内容给网页排名，搜素引擎只可以识别html内容，多页面就是将内容放在html中，所以排名要好一点。 缺点 因为每跳转一个页面都要发送一次http请求，如果网络情况不好的情况下，页面之间来回跳转就会发生明显的卡顿，有的时候半天还加载不出来，影响用户体验。 转场动画也不好实现
4、git命令
1. git init 初始化git仓库 (mac中Command+Shift+. 可以显示隐藏文件) 2. git status 查看文件状态 3. git add 文件列表 追踪文件 4. git commit -m 提交信息 向仓库中提交代码 5. git log 查看提交记录
1.分支明细 （1）主分支（master）：第一次向 git 仓库中提交更新记录时自动产生的一个分支。 （2）开发分支（develop）：作为开发的分支，基于 master 分支创建。 （3）功能分支（feature）：作为开发具体功能的分支，基于开发分支创建 2.分支命令
（1）git branch 查看分支 （2）git branch 分支名称 创建分支 （3）git checkout 分支名称 切换分支 （4）git merge 来源分支 合并分支 (备注：必须在master分支上才能合并develop分支) （5）git branch -d 分支名称 删除分支（分支被合并后才允许删除）（-D 强制删除）
3.暂时保存更改 （1）存储临时改动：git stash （2）恢复改动：git stash pop 更加详细请看git常用命令
git怎么解决多人冲突？：
是当前修改是左箭头方向，传入的是右箭头的方向， 中间用等于号分割，等号上边是当前修改（本地），下边是传入的修改（线上的代码）。 两人同时提交可能会出现冲突，解决办法是手动修改冲突
5、前端有哪些页面优化方法?
- 减少 HTTP请求数
- 从设计实现层面简化页面
- 合理设置 HTTP缓存
- 资源合并与压缩
- 合并 CSS图片，减少请求数的又一个好办法。
- 将外部脚本置底（将脚本内容在页面信息内容加载后再加载）
- 多图片网页使用图片懒加载。
- 在js中尽量减少闭包的使用
- 尽量合并css和js文件
- 尽量使用字体图标或者SVG图标，来代替传统的PNG等格式的图片
- 减少对DOM的操作
- 在JS中避免“嵌套循环”和 “死循环”
- 尽可能使用事件委托（事件代理）来处理事件绑定的操作
- 浏览器缓存
- 防抖、节流
- 资源懒加载、预加载
- 开启Nginx gzip压缩
三个方面来说明前端性能优化
一：webapck优化与开启gzip压缩
1.babel-loader用 include 或 exclude 来帮我们避免不必要的转译，不转译node_moudules中的js文件
其次在缓存当前转译的js文件，设置loader: 'babel-loader?cacheDirectory=true'
2.文件采用按需加载等等
3.具体的做法非常简单，只需要你在你的 request headers 中加上这么一句：
accept-encoding:gzip
4.图片优化，采用svg图片或者字体图标
5.浏览器缓存机制，它又分为强缓存和协商缓存
二：本地存储——从 Cookie 到 Web Storage、IndexedDB
说明一下SessionStorage和localStorage还有cookie的区别和优缺点
三：代码优化
1.事件代理
2.事件的节流和防抖
3.页面的回流和重绘
4.EventLoop事件循环机制
5.代码优化等等
1、什么是axios
基于promise的http库，可以用在浏览器和node.js，支持promiseAPI，客户端支持防御xsrf
2、Node是什么（别看这么简单，有的人一问就懵）
Node是一个基于Chrome V8引擎的JavaScript代码运行环境。 浏览器（软件）能够运行JavaScript代码，浏览器就是JavaScript代码的运行环境
Node（软件）能够运行JavaScript代码，Node就是JavaScript代码的运行环境
3、模块化的意义
一句话：降低软件的复杂性。使其可控，可维护，可扩展。 一个功能就是一个模板，多个模板可以组成完整应用，抽离一个模板不会影响其他功能的运行
4、网站的组成
网站应用程序主要分为两大部分：客户端和服务器端。客户端：在浏览器中运行的部分，就是用户看到并与之交互的界面程序。使用HTML、CSS、JavaScript构建。服务器端：在服务器中运行的部分，负责存储数据和处理应用逻辑。
5、为什么要用node
简单强大，轻量可扩展。
简单体现在node使用的是javascript,json来进行编码，强大体现在非阻塞IO,可以适应分块传输数据，较慢的网络环境，尤其擅长高并发访问，轻量体现在node本身既是代码，又是服务器，前后端使用统一语言;可扩展体现在可以轻松应对多实例，多服务器架构，同时有海量的第三方应用组件。
6、node中的异步和同步怎么理解?
node是单线程的，异步是通过一次次的循环事件队列来实现的．同步则是说阻塞式的IO,这在高并发环境会是一个很大的性能问题，所以同步一般只在基础框架的启动时使用，用来加载配置文件，初始化程序什么的．
7、什么是npm？Npm的使用场景？
NPM是随同NodeJS一起安装的包管理工具，能解决NodeJS代码部署上的很多问题。 使用场景： a. 允许用户从NPM服务器下载别人编写的第三方包到本地使用。 b. 允许用户从NPM服务器下载并安装别人编写的命令行程序到本地使用。 c. 允许用户将自己编写的包或命令行程序上传到NPM服务器供别人使用。
8、get与post请求有什么区别
get是从服务器上获取数据，post是向服务器传送数据。
POST比GET安全，因为数据在地址栏上不可见。
get方式提交的数据最多只能有1024字节，而post则没有此限制。
GET使用URL或Cookie传参。而POST将数据放在request BODY中。
GET与POST都有自己的语义，不能随便混用。
据研究，在网络环境好的情况下，发一次包的时间和发两次包的时间差别基，本可以无视。而在网 络环境差的情况下，两次包的TCP在验证数据包完整 性上，有非常大的优点。post 发送两次，get 只发送一次。
并不是所有浏览器都会在POST中发送两次包，Firefox就只发送一次。
ajax
什么是ajax？ajax有什么优缺点？
ajax不是语言，ajax是一种在无需重新加载整个网页的情况下，能够更新部分网页的技术 优点 1、最大的一点是页面无刷新，用户的体验非常好。 2、使用异步方式与服务器通信，具有更加迅速的响应能力。 缺点 1、ajax不支持浏览器back按钮。 2、安全问题 AJAX暴露了与服务器交互的细节。 3、对搜索引擎的支持比较弱。 4、破坏了程序的异常机制。
5、不容易调试
原生Ajax的创建过程
1.创建xhr 核心对象
var xhr=new XMLHttpRequest();
2.调用open 准备发送
参数一：请求方式
参数二: 请求地址
参数三：true异步，false 同步
xhr.open('post','http://www.baidu.com/api/search',true)
3.如果是post请求，必须设置请求头。
xhr.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded')
4.调用send 发送请求 （如果不需要参数，就写null）
xhr.send('user=tom&age=10&sex=女')
5.监听异步回调 onreadystatechange
判断readyState 为4 表示请求完成
判断status 状态码 为 200 表示接口请求成功
responeseText 为相应数据。字符串类型。
xhr.onreadystatechange=function(){
if(xhr.readyState==4){
if(xhr.status==200){
console.log(xhr.responseText);
var res=JSON.parse(xhr.responseText);
console.log(res);
if(res.code==1){
modal.modal('hide');
location.reload();
}
}
备注：如果是post请求，想要传json格式数据。
设置请求头
1.xhr.setRequestHeader('Content-Type', 'application/json')
open发送数据
2.xhr.open({_id:xxx,user:xxxx,age:xxxx})
web安全及防护
1.XSS攻击原理：
XSS(Cross-Site Scripting，跨站脚本攻击)是一种代码注入攻击。攻击者在目标网站上注入恶意代码，当被攻击者登陆网站时就会执行这些恶意代码，这些脚本可以读取 cookie，session
tokens，或者其它敏感的网站信息，对用户进行钓鱼欺诈，甚至发起蠕虫攻击等。 XSS避免方式：
url参数使用encodeURIComponent方法转义
尽量不是有InnerHtml插入HTML内容
使用特殊符号、标签转义符。
2.CSRF攻击（跨站请求伪造）：
CSRF（Cross-site request forgery）跨站请求伪造：攻击者诱导受害者进入第三方网站，在第三方网站中，向被攻击网站发送跨站请求。利用受害者在被攻击网站已经获取的注册凭证，绕过后台的用户验证，达到冒充用户对被攻击的网站执行某项操作的目的。
CSRF避免方式：
添加验证码
使用token
服务端给用户生成一个token，加密后传递给用户
用户在提交请求时，需要携带这个token
服务端验证token是否正确
3.SQL注入攻击
就是通过吧SQL命令插入到Web表单递交或输入域名，最终达到欺骗服务器执行恶意的SQL命令。 解决：表单输入时通过正则表达式将一些特殊字符进行转换
4、DDoS攻击
DDoS又叫分布式拒绝服务，全称 Distributed Denial of Service，其原理就是利用大量的请求造成资源过载，导致服务不可用。 解决：
限制单IP请求频率。
防火墙等防护设置禁止ICMP包等
检查特权端口的开放
使用基于token的登录流程
1. 客户端使用用户名跟密码请求登录 2. 服务端收到请求，去验证用户名与密码 3. 验证成功后，服务端会签发一个 Token，再把这个 Token 发送给客户端 4. 客户端收到 Token 以后可以把它存储起来，比如放在 Cookie 里或者 Local Storage 里 5. 客户端每次向服务端请求资源的时候需要带着服务端签发的 Token
6. 服务端收到请求，然后去验证客户端请求里面带着的 Token，如果验证成功，就向客户端返回请求的数据
状态码
常见http状态码分类：
200响应成功
301永久重定向
302临时重定向
304资源缓存
403服务器禁止访问
404服务器资源未找到
500 502服务器内部错误
504 服务器繁忙
1xx Informational（信息状态码） 接受请求正在处理
2xx Success（成功状态码） 请求正常处理完毕
3xx Redirection（重定向状态码） 需要附加操作已完成请求
4xx Client Error（客户端错误状态码） 服务器无法处理请求
5xx Server Error（服务器错误状态码） 服务器处理请求出错
浏览器从输入url到渲染页面，发生了什么？
这玩意一定要说全了装逼 用户输入阶段 合成 URL：浏览区会判断用户输入是合法 URL，比如用户输入的是搜索的关键词，默认的搜索引擎会合成新的，如果符合url规则会根据url协议，在这段内容加上协议合成合法的url 查找缓存 网络进程获取到
URL，先去本地缓存中查找是否有缓存资源，如果有则拦截请求，直接将缓存资源返回给浏览器进程；否则，进入网络请请求阶段； DNS 解析： DNS 查找数据缓存服务中是否缓存过当前域名信息，有则直接返回；否则，会进行 DNS 解析返回域名对应的 IP 和端口号，如果没有指定端口号，http 默认 80 端口，https
默认 443。如果是 https 请求，还需要建立 TLS 连接； 建立 TCP 连接： TCP 三次握手与服务器建立连接，然后进行数据的传输；（三次握手开喷） 发送 HTTP 请求： 浏览器首先会向服务器发送请求行，它包含了请求方法、请求 URI 和 HTTP
协议的版本；另外还会发送请求头，告诉服务器一些浏览器的相关信息，比如浏览器内核，请求域名； 服务器处理请求： 服务器首先返回响应行，包括协议版本和状态码，比如状态码 200 表示继续处理该请求；如果是 301，则表示重定向，服务器也会向浏览器发送响应头，包含了一些信息； 页面渲染:
查看响应头的信息，做不同的处理，比如重定向，存储cookie 看看content-type的值，根据不同的资源类型来用不同的解析方式 浏览器渲染原理直接开干..... 浏览器将获取的HTML文档解析成DOM树。 处理CSS标记，构成层叠样式表模型CSSOM(CSS Object Model)。
将DOM和CSSOM合并为渲染树(rendering tree)，代表一系列将被渲染的对象。 渲染树的每个元素包含的内容都是计算过的，它被称之为布局layout。浏览器使用一种流式处理的方法，只需要一次绘制操作就可以布局所有的元素。 将渲染树的各个节点绘制到屏幕上，这一步被称为绘制painting。 断开 TCP
连接： 数据传输完成，正常情况下 TCP 将四次挥手断开连接。但是如果浏览器或者服务器在HTTP头部加上 Connection: keep-alive，TCP 就会一直保持连接。
网络安全、HTTP协议
TCP UDP 区别
1.`TCP`向上层提供面向连接的可靠服务 ，`UDP`向上层提供无连接不可靠服务。 2.虽然 `UDP` 并没有 `TCP` 传输来的准确，但是也能在很多实时性要求高的地方有所作为 3.对数据准确性要求高，速度可以相对较慢的，可以选用`TCP`
是否连接
无连接
面向连接
是否可靠
不可靠传输，不使用流量控制和拥塞控制
可靠传输，使用流量控制和拥塞控制
连接对象个数
支持一对一，一对多，多对一和多对多交互通信
只能是一对一通信
传输方式
面向报文
面向字节流
首部开销
首部开销小，仅8字节
首部最小20字节，最大60字节
适用场景
适用于实时应用（IP电话、视频会议、直播等）
适用于要求可靠传输的应用，例如文件传输
Http和Https区别（高频）
1.`HTTP` 的URL 以http:// 开头，而HTTPS 的URL 以https:// 开头
2.`HTTP` 是不安全的，而 HTTPS 是安全的
3.`HTTP` 标准端口是80 ，而 HTTPS 的标准端口是443
4.`在OSI` 网络模型中，HTTP工作于应用层，而HTTPS 的安全传输机制工作在传输层
5.`HTTP` 无法加密，而HTTPS 对传输的数据进行加密，证的网络协议，安全性高于HTTP协议。
6.`HTTP`无需证书，而HTTPS 需要CA机构wosign的颁发的SSL证书，一般免费证书少，因而需要一定费用。
GET和POST区别（高频）
1.GET在浏览器回退不会再次请求，POST会再次提交请求
2.GET请求会被浏览器主动缓存，POST不会，要手动设置
3.GET请求参数会被完整保留在浏览器历史记录里，POST中的参数不会
4.GET请求在URL中传送的参数是有长度限制的，而POST没有限制
5.GET参数通过URL传递，POST放在Request body中
6.GET参数暴露在地址栏不安全，POST放在报文内部更安全
7.GET一般用于查询信息，POST一般用于提交某种信息进行某些修改操作
8.GET产生一个TCP数据包；POST产生两个TCP数据包
Ge和post的选择：
1.私密性的信息请求使用post（如注册、登陆）。
2.查询信息使用get。
三次握手和四次挥手
三次握手：
第一次：建立连接时，客户端发送syn包到服务器，等待服务端确认 第二次：服务器收到syn包，必须确认客户的syn，同时也发送一个syn包，即syn+ACK包 第三次：客户端收到服务器的syn和ack包，向服务器发送确认包ack，发送完毕，客户端和服务端连接成功，完成三次握手
四次挥手：
第一次：浏览器发送完数据后，发送fin请求断开连接 第二次：服务器发送ack到客户端，确认客户端的断开请求 第三次：服务器请求断开fin的请求 第四次：客户端确认服务器的断开ack
POST的content-type几种方式
POST 方法中对发送数据编码的方式，也就是 Content-Type 有四种方式，其中默认是 application/x-www-form-urlencoded，最方便的是 application/json 。 四种方式包括：
application/x-www-form-urlencoded （URL encoded）
multipart/form-data （键值对型数据）
application/json (Json 类型数据)
text/xml （xml）
传统的ajax请求时候，Content-Type默认为"文本"类型。 传统的form提交的时候，Content-Type默认为"Form"类型。 axios传递字符串的时候，Content-Type默认为"Form"类型。
axios传递对象的时候，Content-Type默认为"JSON"类型
http1.0、http1.1、http2.0的区别
1和1.0相比，1.1可以一次传输多个文件
http1.x解析基于文本，
http2.0采用二进制格式，新增特性 多路复用、header压缩、服务端推送(静态html资源)
浏览器缓存的作用
浏览器缓存的作用：减少冗余的数据传输，节省网络带宽，更快加载页面，缓存降低了服务器的要求，有更快的响应
http如何实现缓存
个人理解： 强制缓存：浏览器在加载资源的时候，会根据本地缓存中的headers中的信息(expires,cache-control)是否要强缓存，如果命中的话，则会使用缓存中的资源，否则继续发送请求。
协商缓存：客户端向服务端发送请求，服务端检测是否有对应的标识，如果没有服务端会返回客户端对应的标识，客户端在下次请求把标识带过去服务器会验证标识，如果通过了，则会响应304，告诉浏览器读取缓存，如果没有通过则返回请求的资源。
两类缓存规则可以同时存在，强制缓存优先级高于对比缓存，也就是说，当执行强制缓存的规则时，如果缓存生效，直接使用缓存，不再执行对比缓存规则。 基于对比缓存，不管是否使用缓存都需要向服务器发送请求，那么还用缓存干什么？ 服务端在进行标识比较后，只返回header部分，通过状态码通知客户端使用缓存，不再需要将报文主体部分返回给客户端。
缓存的资源去哪里了
memory cache 将资源文件缓存到内存中，下次请求读取的是内存中的 disk cache 将资源存到硬盘中，下次请求从硬盘中读取
http报文
HTTP报文就是浏览器和服务器间通信时发送及响应的数据块。 浏览器向服务器请求数据，发送请求(request)报文； 服务器向浏览器返回数据，返回响应(response)报文。 报文信息主要分为两部分：header,数据主体部分(body)
能不能说一说浏览器的本地存储？各自优劣如何？
浏览器的本地存储主要分为Cookie、WebStorage和IndexDB, 其中WebStorage又可以分为localStorage和sessionStorage。 共同点: 都是保存在浏览器端、且同源的
不同点：
cookie数据始终在同源的http请求中携带（即使不需要），即cookie在浏览器和服务器间来回传递。cookie数据还有路径（path）的概念，可以限制cookie只属于某个路径下sessionStorage和localStorage不会自动把数据发送给服务器，仅在本地保存。
存储大小限制也不同，
cookie数据不能超过4K，sessionStorage和localStorage可以达到5M
sessionStorage：仅在当前浏览器窗口关闭之前有效；
localStorage：始终有效，窗口或浏览器关闭也一直保存，本地存储，因此用作持久数据；
cookie：只在设置的cookie过期时间之前有效，即使窗口关闭或浏览器关闭
作用域不同
sessionStorage：不在不同的浏览器窗口中共享，即使是同一个页面；
localstorage：在所有同源窗口中都是共享的；也就是说只要浏览器不关闭，数据仍然存在
cookie: 也是在所有同源窗口中都是共享的.也就是说只要浏览器不关闭，数据仍然存在
第一期：前端面试题---JS部分
第二期：前端面试题 ---Vue部分
以上就是本期内容了！！！
文章分享自微信公众号：
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！
作者：程序员XR原始发表时间：2022-07-03如有侵权，请联系 cloudcommunity@tencent.com 删除。