hashmap源码深度解析（深度解析HashMap集合底层原理）
hashmap源码深度解析（深度解析HashMap集合底层原理）时间复杂度为O(n) 从头查询到尾部，查询多次set集合存储的就是不重复的对象，底层就是hashmap，依据equals和hashcode进行判断如果两个对象的HashCode相等，对象的内容至不一定相等；hash碰撞的问题如果使用equals方法比较两个对象内容值相等的情况下，那么hashcode的值也相等因为equals默认情况下Object类采用==比较对象，那么比较的是内存地址是否相等，当数据类型只要不是基本类型，那么比较永远不会相等。
目录
- 前置知识
- ==和equals的区别
- 为什么要重写equals和HashCode
- 时间复杂度
- (不带符号右移) >>>
- ^异或运算
- &（与运算）
- 位移操作：1<<2=4，1左移两位为什么等于4
- HashMap集合特点及源码分析（JDK1.8）
- HashMap重要的五大点
- 1.集合初始化
- HashMap成员变量
- HashMap内部数据结构
- 链表
- 红黑树
- HashMap构造方法
- 指定初始容量
- 指定填充比
- 用来初始化的Map
- 2.数据寻址Get
- 3.数据存储Put
- 4.节点删除
- 5.扩容原理
- JDK1.7 HashMap中扩容机制resize()
- 多线程环境下扩容造成死循环的分析过程
- 解决办法
- JDK1.8 HashMap中扩容机制resize()
- HashMap面试题
- HashMap什么时候会转换为红黑树
- HashMap为什么要引进红黑树，为了解决什么问题？
- HashMap的长度为什么必须是2的次幂？
- 如何避免HashMap内存溢出问题
- HashMap根据key查询的时间复杂度
- HashMapKey为null存放在什么位置
- HashMap底层是采用单链表还是双链表
- HashMap底层是有序存放的吗
- LinkedHashMap 和 TreeMap底层如何实现有序的
- 为什么HashMap不使用取模运算
- 求下标i=(n-1)&hash 为什么（n-1）变成了奇数
- HashMap如何降低Hash冲突
- 加载因子为什么是0.75而不是1
- Hashap存放1W条数据怎么样效率最高
- Hashmap1.7和Hashmap1.8的区别
对于基本类型变量来说，只能使用 == ，因为基本类型的变量没有方法。使用==比较是值比较
对于引用类型的变量来说，==比较的两个引用对象的地址是否相等。所有类都是继承objcet类，而object类是equals方法比较的也是对象的地址是否相等，如果类没有重写equals方法，使用 == 和equals方法效果是一样的
为什么要重写equals和HashCode#HashCode方法：底层采用C语言编写，根据对象地址转换为整数类型
如果两个对象的HashCode相等，对象的内容至不一定相等；hash碰撞的问题
如果使用equals方法比较两个对象内容值相等的情况下，那么hashcode的值也相等
因为equals默认情况下Object类采用==比较对象，那么比较的是内存地址是否相等，当数据类型只要不是基本类型，那么比较永远不会相等。
set集合存储的就是不重复的对象，底层就是hashmap，依据equals和hashcode进行判断
时间复杂度#时间复杂度为O(n) 从头查询到尾部，查询多次
时间复杂度为O(1) 查询一次 比如根据数组下标查询
时间复杂度为O(logn) 平方查询 比如红黑树，
效率：O(1)>O(logn)>O(n)
(不带符号右移) >>>#无符号右移就是右移之后，无论该数为正还是为负，右移之后左边都是补上0
无符号右移运算符和右移运算符的主要区别在于负数的计算，因为无符号右移是高位补0，移多少位补多少个0
15>>>2=0000 1111 右移两位=0000 0011=3
^异或运算#相同为0，不同为1
2^3= 0010^0011=0001=1
&（与运算）#00得0 11得1 01得0
2&3=0010&0011=0010=2
位移操作：1<<2=4，1左移两位为什么等于4#这里的1是十进制，而计算机交流是用二进制，所以先要将1用二进制表示出来。
每一个符号（英文、数字或符号等）都会占用1Bytes的记录，每一个中文占2Byte
而一个1Bytes占8个bit，也就是8个二进制位
8位二进制数：28种不同状态 0000 0000 ~1111 1111=0~255=28=256
1的二进制表示0000 0001，然后进行位移操作。
位移操作向左边位移，后面空出来的补上0，越往左边越大，把0000 0001向左位移2位，变成了0000 0100，二进制0000 0100转化十进制所以为4，也可以说每左移一位是乘以2
8>>2?
0000 1000右移2位0000 0010，转化为10进制等于2
10>>2?
0000 1010右移2位0000 0010，转化为10进制等于2
1<<30?
0000 0001左移30位01000000 00000000 00000000 00000000，转化为10进制等于1073741824，也就是230
HashMap集合特点及源码分析（JDK1.8）#public class HashMap<K V> extends AbstractMap<K V>
implements Map<K V> Cloneable Serializable {
HashMap继承了AbstractMap类，实现了Cloneable克隆接口、Serializable序列化接口、Map接口
特点：数组 链表 红黑树构成
//默认初始化hashmap容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //2的4次幂 16
//hashmap最大容量1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;//2的30次幂
//扩容因子 16*0.75=12 达到12就会进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表中存储元素的数量 > 8 时，会自动转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//删除元素时，如果一个红黑树中中存储元素数量 < 6 后，会自动转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
//数组容量>64&链表长度>8 转为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
//阙值，用于判断是否扩容，threshold=容量*扩容因子=16*0.75=12
int threshold;
//扩容因子实际大小
final float loadFactor;
//HashMap中元素的数量 transient表示不能被序列化
transient int size;
//集合修改次数 防止多线程篡改数据
transient int modCount;
//存储元素的数组 单向链表
transient Node<K V>[] table;
HashMap内部数据结构#链表
//单向链表 实现了Entry接口 由上面的数组构成了数组加链表的结构
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 V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//比较两个Node是否相等
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;
}
}
红黑树
//红黑树结构概览
static final class TreeNode<K V> extends LinkedHashMap.Entry<K V> {
TreeNode<K V> parent; // red-black tree links
TreeNode<K V> left;//左子树
TreeNode<K V> right;//右子树
TreeNode<K V> prev; //
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;
}
}
}
HashMap构造方法#指定初始容量
构造一个具有默认初始容量 (16) 和默认负载因子 (0.75)的空HashMap
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; //扩容因子0.75
}
指定填充比
构造一个具有指定初始容量和默认扩容因子 (0.75)的空HashMap
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;//负载因子
this.threshold = tableSizeFor(initialCapacity);
}
//获得的是大于cap的最小的2的幂，例如10，10的最小的2的幂=16
static final int tableSizeFor(int cap) {
int n = cap - 1;//n=9 0000 1001
n |= n >>> 1;//|= 代表异或运算 先向右位移1位=0000 0100，0000 1001和0000 0100异或运算得到0000 1101
n |= n >>> 2;//....以此类推
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//n<0返回1，否则n大于MAXIMUM_CAPACITY的话返回最大值，小于最大值返回n 1，全1的情况 1一定变成1后面跟一堆0的情况，这样就确定了最终的值，当HashMap的size到达threshold这个阈值时会扩容
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}
用来初始化的Map
使用与指定Map相同的映射构造一个新的HashMap
public HashMap(Map<? extends K ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//默认负载因子0.75
putMapEntries(m false);
}
//将集合元素put到HashMap中
final void putMapEntries(Map<? extends K ? extends V> m boolean evict) {
//获取元素大小
int s = m.size();
if (s > 0) {
//如果存储元素的数组为空 说明这是刚构造的HashMap 那么就要为它指定最大容量
if (table == null) {
//根据阈值和Map大小 推算出最大容量，向上取整为了取整数
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(); //先扩容
// 循环put
for (Map.Entry<? extends K ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//可能会触发resize
putVal(hash(key) key value false evict);
}
}
}
2.数据寻址Get#
根据key获取元素
public V get(Object key) {
Node<K V> e;
//key的hash值
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;
//如果table不等于null 数组不等于null first=赋值计算当前节点的hash值所在的数组下标位置
if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
//如果比较当前节点的和第一个节点
if (first.hash == hash &&((k = first.key) == key || (key != null && key.equals(k))))
//返回第一个结点
return first;
//如果第一个节点的下一个节点不为null
if ((e = first.next) != null) {
//判断是否为红黑树
if (first instanceof TreeNode)
//处理getTreeNode()方法搜索key
return ((TreeNode<K V>)first).getTreeNode(hash key);
//是链表
do {
//遍历比较直到找到节点或者节点为null退出循环
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
3.数据存储Put#
将元素添加进HashMap
public V put(K key V value) {
return putVal(hash(key) key value false true);
}
详细方法
final V putVal(int hash K key V value boolean onlyIfAbsent
boolean evict) {
Node<K V>[] tab;
Node<K V> p;
//n表示table数组的长度 i表示key存放在哪个数组下标
int n i;
//将全局table=tab判断是否为空 或者 tab长度为0情况下 对table进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
//扩容 n=16
n = (tab = resize()).length;
//i = (n - 1) & hash 计算key对应的index值 tab[i]key在数组中是否存在
if ((p = tab[i = (n - 1) & hash]) == null)
//如果key的index值没有发生冲突
tab[i] = newNode(hash key value null);
//key的index发生冲突了
else {
Node<K V> e; K k;
//如果hash和equals比较都相同 直接覆盖
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果当前是红黑树
else if (p instanceof TreeNode)
//追加到红黑树后面
e = ((TreeNode<K V>)p).putTreeVal(this tab hash key value);
//当前是链表
else {
//循环遍历链表
for (int binCount = 0; ; binCount) {
//如果链表为空 直接追加在next后面
if ((e = p.next) == null) {
p.next = newNode(hash key value null);
//如果链表长度binCount大于8 数组容量大于64
if (binCount >= TREEIFY_THRESHOLD - 1)
//把链表转换为红黑树
treeifyBin(tab hash);
break;
}
//查询链表中是否存在该key，如果存在直接修改value值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//真正给e赋值 将新的value覆盖为oldvalue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//只有新增才会使modCount 修改不会 fastclass机制防止在做遍历的时候有集合修改类
modCount;
//如果size>12 就会提前去扩容
if ( size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
4.节点删除#
public V remove(Object key) {
Node<K V> e;
return (e = removeNode(hash(key) key null false true)) == null ?null : e.value;
}
详细方法
//hash:key的hash值 key:要删除的键值对的key value:要删除的键值对的value
//matchValue 如果为true，则当key对应的键值对的值equals(value)为true时才删除；否则不关心value的值
//movable 删除后是否移动节点，如果为false，则不移动
final Node<K V> removeNode(int hash Object key Object value boolean matchValue boolean movable) {
Node<K V>[] tab; Node<K V> p; int n index;
//节点数组tab不为空、数组长度n大于0、根据hash定位到的节点对象p
if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {
Node<K V> node = null e; K k; V v;
//如果当前节点的键和key相等，那么当前节点就是要删除的节点，赋值给node
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//获取当前节点的下一个节点
else if ((e = p.next) != null) {
//如果是一个红黑树，那么调用getTreeNode方法从树结构中查找满足条件的节点
if (p instanceof TreeNode)
node = ((TreeNode<K V>)p).getTreeNode(hash key);
//如果是链表
else {
//从头到尾逐个节点比对
do {
//e节点的键是否和key相等，e节点就是要删除的节点，赋值给node变量
if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;//p指向e，让p存储的永远下一次循环里e的父节点
} while ((e = e.next) != null);
}
}
//node不为空 找到了删除的节点 如果不需要对比value值或者需要对比value值但是value值也相等
if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {
//如果是红黑树上的节点
if (node instanceof TreeNode)
//删除
((TreeNode<K V>)node).removeTreeNode(this tab movable);
//如果是链表 该node节点就是首节点
else if (node == p)
//删除 把当前节点的下一个赋值给当前表索引
tab[index] = node.next;
//不是首节点，p是node的父节点
else
// 删除 父节点的下一个节点就是node的下一个节点
p.next = node.next;
modCount;//HashMap的修改次数递增
--size;//HashMap的元素个数
afterNodeRemoval(node);//保留的重写方法 无效果
return node;//返回删除结果
}
}
return null;
}
5.扩容原理#JDK1.7 HashMap中扩容机制resize()#
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果旧容量已经达到了最大，将阈值设置为最大值，与1.8相同
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//创建新哈希表
Entry[] newTable = new Entry[newCapacity];
//将旧表的数据转移到新的哈希表
transfer(newTable initHashSeedAsNeeded(newCapacity));
table = newTable;
//更新阈值
threshold = (int)Math.min(newCapacity * loadFactor MAXIMUM_CAPACITY 1);
}
void transfer(Entry[] newTable boolean rehash) {
int newCapacity = newTable.length;
//遍历原来数组中所有的链表
for (Entry<K V> e : table) {
//判断每个下标对应的链表存放是否为空
while(null != e) {
//这里两个多线程环境下都拿到 e.next可能会有死循环问题
Entry<K V> next = e.next;
//是否需要重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//得到新表中的索引
int i = indexFor(e.hash newCapacity);
//将新节点作为头节点添加到桶中
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
多线程环境下扩容造成死循环的分析过程
for (Entry<K V> e : table) {
while(null != e) {
Entry<K V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
因为是采用头插法，会导致整个链表顺序颠倒，多线程环境下遍历table这就容易导致死循环，因为操纵的同一个e对象
在多线程同时扩容的情况下，线程一抢先获得CPU资源，而线程二被挂起，此时它们拿到的数据都是e=a；next=c；线程一率先执行把key计算好了并放入newTable了
这时候线程二又被唤醒，因为线程之间不是共享的，所以此时newTable也为空，需要重新给里面赋值，但是e变量是可以被共享的。
1、线程二第一次循环还是之前拿到的数据e=a；next=c，此时newTable还为空
// e=a e.next=c
Entry<K V> next = e.next;
//1
int i = indexFor(e.hash newCapacity);
//e.next=null
e.next = newTable[i];
//数组1位置第一个元素赋值为 a
newTable[i] = e;
//e=c
e = next;
2、线程二第二次循环
第二次循环获取e的数据，因为e的之前被线程一修改过变为d->c->
// e=c e.next=a
Entry<K V> next = e.next;
//1
int i = indexFor(e.hash newCapacity);
//e.next=null
e.next = newTable[i];
//数组1位置赋值为 c
newTable[i] = e;
//e=a
e = next;
因为e的之前被线程一修改过变为d->c->a，所以c.next等于线程一里面的值，c.next=a
3、线程二第三次循环
//e=a； e.next=a.next=null
Entry<K V> next = e.next;
//1
int i = indexFor(e.hash newCapacity);
//此时newTable[i]=a->c e.next=a.next a.next=c->a 出现死循环
e.next = newTable[i];
//数组1位置赋值为 a
newTable[i] = e;
//e=null
e = next;
此时进入环形引用，无限循环中导致CPU使用率飙升
解决办法单线程下没有不会有问题，多线程下采用ConCurrentHashMap
JDK1.8 HashMap中扩容机制resize()# final Node<K V>[] resize() {
Node<K V>[] oldTab = table;
//如果原来的table=null 则为HashMap的初始化 生成空table返回即可
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//hashmap下一次扩容的阈值
int oldThr = threshold;
//记录新的容量和新的下一次扩容大小
int newCap newThr = 0;
//大于0说明之前HashMap的数组不是空的
if (oldCap > 0) {
// 再对数组进行检测 如果大于最大容量2的30次幂 直接返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//否者进行扩容为之前的二倍基于右移 newCap是oldCap长度的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//下一次提前扩容的数量
newThr = oldThr << 1;
}
//阈值大于0 说明集合已存在 赋值给newCap
else if (oldThr > 0)
newCap = oldThr;
//如果等于0 说明刚初始化 newCap=0.75 newThr=新扩容的阈值=0.75*默认容量大小
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果下一次提前扩容的数量==0
if (newThr == 0) {
//新阈值=新容量*负载因子
float ft = (float)newCap * loadFactor;
//新数组小于最大容量 并且阈值小于最大容量
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//下一次扩容的阈值
threshold = newThr;
@SuppressWarnings({"rawtypes" "unchecked"})
//HashMap里面新的扩容容量
Node<K V>[] newTab = (Node<K V>[])new Node[newCap];
table = newTab;
//如果原表不为空，把原表中数据移动到新表中
if (oldTab != null) {
//遍历原来的列表
for (int j = 0; j < oldCap; j) {
Node<K V> e;
//判断每个数组里面是否有链表 有的话用一个链表e存起来
if ((e = oldTab[j]) != null) {
//然后将原来的链表赋值为null 能避免死循环
oldTab[j] = null;
//下一个节点为空 说明只包含一个元素
if (e.next == null)
//计算e在新table中的位置 放入其中
newTab[e.hash & (newCap - 1)] = e;
//判断当前node是否是红黑树
else if (e instanceof TreeNode)
((TreeNode<K V>)e).split(this newTab j oldCap);
//链表情况下
else {
//hashmap扩容会把原来的链表拆分成 两个链表
//低位链表的头尾
Node<K V> loHead = null loTail = null;
//高位链表的头尾
Node<K V> hiHead = null hiTail = null;
Node<K V> next;
//循环把链表拆分 放到两个链表里面
do {
next = e.next;
//散列下标不变的情况 oldCap=16
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;
}
//放在新表j oldCap位置
if (hiTail != null) {
hiTail.next = null;
newTab[j oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap1.8将链表通过运算拆封成两个链表存放到新的table中
HashMap面试题#HashMap什么时候会转换为红黑树#数组容量大于64并且链表长度大于8时
HashMap为什么要引进红黑树，为了解决什么问题？#链表查询时间复杂度为O(n) 查询效率太低了，引用红黑树查询效率可以变为O(logN)
HashMap的长度为什么必须是2的次幂？#这样长度一定是偶数，在计算index下标的时候(n-1)&hash，这样（n-1）就会是奇数，奇数&hash值才会减小冲突。n区 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列
如何避免HashMap内存溢出问题#因为没有重写hashcode和equals和方法，底层默认用==比较内存地址，就会导致new出多个对象，重写之后每次比较都会是同一个对象，会做覆盖。
HashMap根据key查询的时间复杂度#如果key没有产生冲突，时间复杂度为O(1)，一次就能查到
如果key产生冲突链表存放为O(n)，红黑树存放为O(logn)
HashMapKey为null存放在什么位置#第0个位置
int index = k == null ? 0 : k.hashCode() % objects.length;
HashMap底层是采用单链表还是双链表#
单向链表
HashMap底层是有序存放的吗#单向链表存放无序散列，会将所有链表和红黑树都遍历，效率非常低
LinkedHashMap 和 TreeMap底层如何实现有序的#原理：将每个index中的链表实现关联，效率比HashMap要低
缓存淘汰算法底层实现原理LinkedHashMap
Redis如果缓存满的情况下如何清理？
LUR算法:清理最近少用的key
方案1：对每个key记录使用次数，然后排序再删除 效率非常低
方案2：基于LinkedHashMap有序集合实现 访问key的时候就会将key存到链表最后的位置
插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序
执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。
其中参数accessOrder就是用来指定是否按访问顺序，如果为true，就是访问顺序。
为什么HashMap不使用取模运算#k.hashcode()%entrys.length取模会导致key冲突概率非常大
就会导致变为链表O(n)或者红黑树O(logn) 需要降低Hash冲突概率，均匀的放在数组的每个下标的位置
求下标i=(n-1)&hash 为什么（n-1）变成了奇数#扩容默认是偶数，2的n次幂。如果是偶数&（与运算）hash，index冲突概率非常大，会使数据分布不均
所以需要变成奇数
HashMap如何降低Hash冲突#hash函数计算i=(n-1)&hash 通过奇数余hash值能够降低hash值发生冲突的概率
加载因子为什么是0.75而不是1#如果加载因子越大（1），空间利用率比较高16个位置都填满了，这样index冲突概率比较大
如果加载因子越小（0.1），达到0.1就扩容那么空间利用率越小，能存放的位置更多，这样index冲突概率越小
空间和时间上的平衡点：0.75
统计学概率：泊松分布是统计学和概率学常见的离散概率分布
Hashap存放1W条数据怎么样效率最高#hashmap容量=（需要存储的元素个数/扩容因子） 1=（10000/0.75） 1=13334
目的是减少底层扩容的次数，如果没有设置初始容量大小，hashmap需要进行7次扩容，严重影响性能
Hashmap1.7和Hashmap1.8的区别#Hashmap1.7基于数组 链表实现头插法，写法简单 但是有多线程死循环问题
Hashmap1.8基于数组 链表 红黑树实现尾插法，解决了多线程死循环问题
能够降低key对应的index的冲突概率，提高查询率
原来的链表使用与运算hash&原来table长度，拆分成两个链表放到新数组中，能够将链表长度缩短，提高查询效率
