1.hash是什么
Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。
2.HashMap基本特性
1.HashMap存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。
2.非同步，线程不安全。
3.底层是hash表，不保证有序(比如插入的顺序)
HashMap
① JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，当一个元素放入集合时，会计算key的Hash值，即hash(key)，然后对数组的大小进行按位与运算计算一个桶下标（索引）。将key放入数组对应的桶下标索引处，将key尽可能的分散在不同的桶下标下面，可以让查找更加快速，时间复杂度为O(1)， 但是不同的key也有可能计算出相同的桶下标（索引），此时需要通过equals()方法来查找key，虽然查找性能会有损失，但是可以解决桶下标冲突。
死链的并发问题会发在扩容的时候，随着数组内元素越来越多，必然导致链表的长度也越来越长，查找性能就会受到影响，jdk7和jdk8都是在数组长度超过一个阈值时就会发生扩容，这个阈值就是数组的长度的四分之三（12）发生扩容，扩容的方式会重新计算桶下标，让容量翻倍。
② JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。
哈希冲突：
两个不同的key经过hash函数计算出相同的桶下标索引
4.基本参数
// 默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 定义一个空数组
static final Entry<?,?>[] EMPTY_TABLE = {};
// 存储键值对的数组，默认为空数组，根据需要进行扩容，长度必须是2的整数幂
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 容量*加载因子，根据此判断是否需要扩容
int threshold;
// map中的键值对个数
transient int size;
// 此 HashMap 已在结构上修改的次数。结构修改是指更改 HashMap 中的映射数量或以其他方式修改其内部结构（例如，重新散列）的那些。该字段用于使 HashMap 的 Collection-views 上的迭代器快速失败。 （请参阅 ConcurrentModificationException）。
// 结构上的修改一般来说就是添加和删除
transient int modCount;5.构造函数
//指定容量大小的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/*
指定“容量大小”和“加载因子”的构造函数
initialCapacity: 指定的容量
loadFactor:指定的加载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//判断初始化容量initialCapacity是否小于0
if (initialCapacity < 0)
//如果小于0，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂
if (initialCapacity > MAXIMUM_CAPACITY)
//如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
//判断负载因子loadFactor是否小于等于0或者是否是一个非数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
//将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
this.loadFactor = loadFactor;
/*
tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次幂。
但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写：
this.threshold = tableSizeFor(initialCapacity) *this.loadFactor;
这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。
但是，请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算
*/
this.threshold = tableSizeFor(initialCapacity);
}
/**
Returns a power of two size for the given target capacity.
返回比指定初始化容量大的最小的2的n次幂
*/
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;
}5.1put方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
// 如果是空数组，根据容量进行初始化，
inflateTable(threshold);
}
if (key == null)
// 有则更新，无则新增，下标为0
return putForNullKey(value);
// 根据key取hash值
int hash = hash(key);
// 根据hash值求取下标
int i = indexFor(hash, table.length);
// 如果存在旧值，就更新并返回旧值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
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;
}
private void inflateTable(int toSize) {
// 容量是2的整数幂
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
// 最后结果是 hashSeed=0
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
// 原理（扰动函数），尽可能使生成的hash值分布均匀，随机，避免冲突
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 当length始终为2的n次方时，h&(length-1)等价于h%length
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // 当size大于容量*负载因子的时候进行扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
// 新增一个entry
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
// 扩容
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
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) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 这里采用了“头插法”，相当于倒序插入
// 假如原来的链表为 a->b->c->d->null
// 转移后的新的链表为 d->c->b->a->null
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}1.首先获取Node数组table对象和长度，若table为null或长度为0，则调用resize()扩容方法获取table最新对象，并通过此对象获取长度大小
2.判定数组中指定索引下的节点是否为Null，若为Null 则new出一个单向链表赋给table中索引下的这个节点
3.若判定不为Null,我们的判断再做分支
3.1 首先对hash和key进行匹配,若判定成功直接赋予e
3.2 若匹配判定失败,则进行类型匹配是否为TreeNode 若判定成功则在红黑树中查找符合条件的节点并将其回传赋给e
3.3 若以上判定全部失败则进行最后操作,向单向链表中添加数据若单向链表的长度大于等于8,则将其转为红黑树保存，记录下一个节点,对e进行判定若成功则返回旧值
4.最后判定数组大小需不需要扩容
5.2resize方法
//重新设置table大小/扩容 并返回扩容的Node数组即HashMap的最新数据
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //table赋予oldTab作为扩充前的table数据
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//判定数组是否已达到极限大小，若判定成功将不再扩容，直接将老表返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//若新表大小(oldCap*2)小于数组极限大小 并且 老表大于等于数组初始化大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr*2当作新数组的大小
newThr = oldThr << 1; // double threshold
}
//若老表中下次扩容大小oldThr大于0
else if (oldThr > 0)
newCap = oldThr; //将oldThr赋予控制新表大小的newCap
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; //将当前表赋予table
if (oldTab != null) { //若oldTab中有值需要通过循环将oldTab中的值保存到新表中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//获取老表中第j个元素 赋予e
oldTab[j] = null; //并将老表中的元素数据置Null
if (e.next == null) //若此判定成立 则代表e的下面没有节点了
newTab[e.hash & (newCap - 1)] = e; //将e直接存于新表的指定位置
else if (e instanceof TreeNode) //若e是TreeNode类型
//分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null; //存储与旧索引的相同的节点
Node<K,V> hiHead = null, hiTail = null; //存储与新索引相同的节点
Node<K,V> next;
//通过Do循环 获取新旧索引的节点
do {
next = e.next;
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;
}1.判定数组是否已达到极限大小，若判定成功将不再扩容，直接将老表返回
2.若新表大小(oldCap2)小于数组极限大小&老表大于等于数组初始化大小 判定成功则 旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr2当作新数组的大小
2.1. 若[2]的判定不成功，则继续判定 oldThr （代表 老表的下一次扩容量）大于0，若判定成功 则将oldThr赋给newCap作为新表的容量
2.2 若 [2] 和[2.1]判定都失败,则走默认赋值 代表 表为初次创建
3.确定下一次表的扩容量, 将新表赋予当前表
4.通过for循环将老表中德值存入扩容后的新表中
4.1 获取旧表中指定索引下的Node对象 赋予e 并将旧表中的索引位置数据置空
4.2 若e的下面没有其他节点则将e直接赋到新表中的索引位置
4.3 若e的类型为TreeNode红黑树类型
4.3.1 分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储
4.3.2 通过Do循环 不断获取新旧索引的节点
4.3.3 通过判定将旧数据和新数据存储到新表指定的位置
6.面试题
1.什么是HashMap
HashMap 是一个散列，哈希，它存储的内容是键值对(key-value)映射。
2.什么是哈希值
哈希值的话通过散列算法变换成固定长度的输出，该输出就是散列值。
3.哈希值有什么特点用法
（1）.哈希值是不可逆，应用可以用在数据库的用户密码，当你不需要知道用户的具体信息，只用判断对错的时候可以用Haxi值来保存，比如把123加密 ，加密后称为456，无法通过456解密成123.
（2）任意长度的输入，得到固定长度的输出
（3）防篡改：密码学里的主要用途，因为只能加密不能解密，所以发送数据时会把原文加密后把原文和密文一起发给对方，对方收到后，先对原文做个加密，如果密文和收到的一样说明内容没被改过。
4.HashMap的数据结构是数组+链表+红黑树
1.7 数组特点：连续存储的空间，查询快增删慢
1.7 链表特点: 不连续的区域，每个节点放值和指向下一个节点的指针查询慢，增删快
1.8引用 红黑树:自平衡的二叉树什么叫平衡，简单理解就是任意节点的左右两个子树高度差都小于等于1，这样便利起来会更均匀
5.什么是哈希碰撞
哈希碰撞就是有有限的值碰到了无限的输出，总会有碰撞。
5.为什么要引入红黑树
为了提高HashMap的性能，之前是链表过长导致索引慢的的问题。
当没有冲突的时候放在数组中，当冲突<8放在链表中，当>8的时候放在红黑树中
时间复杂读从o(n)降到了o（logn）
6. 1.7是头插法可能会存入空指针 1.8是尾插法
HashMap的初始扩容
（1）.初始容量16，0.75
7.什么时候扩容
当达到阈值并不会立即扩容，还要一个条件是存在Hash碰撞才会扩容
8.时间复杂度
没有发生碰撞时间复制度01，只需要查询一次
当时链表的时候0n，
采用红黑树就是0(logn)
Haximap的底层存放没有顺序。
原创文章，作者：，如若转载，请注明出处：https://blog.ytso.com/276021.html