什么是哈希？

Hash也称散列、哈希，对应的英文都是Hash。基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出。这个映射规则就是对应的Hash算法。

Hash的特点：
1、从hash值不能反向推导出原始的数据
2、输入的微小变化会得到完全不同的hash值，相同的数据会得到相同的值

好的hash算法要保证：

• hash算法的执行效率要高效，长文本也能快速地计算出哈希值
• hash算法的冲突概率要小

为什么会出现hash冲突？哈希冲突可以避免吗？

由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间，根据抽屉原理，一定会存在不同的输入被映射成相同的情况

抽屉原理： 桌子上有10个苹果，要把这10个苹果放到9个抽屉里，无论怎样，我们会发现至少会有一个抽屉里放不少于2个苹果。这一现象就是我们所说的"抽屉原理"

hashMap中的一些专业名词

capacity 容量
load 负载，加载
factor 因素，因子
threshold 阈值
默认容量大小

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

DEFAULT_INITIAL_CAPACITY： 默认初始容量 16

默认负载因子

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

DEFAULT_LOAD_FACTOR： 默认负载因子 0.75

树化阈值（链表 - > 红黑树的阈值）

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

TREEIFY_THRESHOLD：由链表变成红黑树的阈值为8（还有一个条件是，数组的长度至少达到64）

树退化阈值（红黑树 -> 链表）

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

UNTREEIFY_THRESHOLD：由红黑树退化为链表的阈值为6

最小树化容量

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

MIN_TREEIFY_CAPACITY：链表变成红黑树的必要前提条件是 数组的长度达到64

扩容阈值

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

扩容阈值：当hashMap中key-value键值对个数超过阈值时，就会触发扩容

threshold = capacity * load factor （扩容阈值 = 容量 * 负载因子）

请解释一下hashMap的参数loadFactor，它的作用是什么？

loadFactor表示HashMap的拥挤程度，影响hash操作到同一个数组位置的概率。默认loadFactor等于0.75，当HashMap里面容纳的元素已经达到HashMap数组长度的75%时，表示HashMap太挤了，需要扩容，在HashMap的构造器中可以定制loadFactor。

谈一下hashMap的特性？

• HashMap存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。
• 非同步，线程不安全。
• 底层是hash表，不保证有序(比如插入的顺序)

谈一下hashMap的底层原理？

他的实现分不同版本，如果是jdk1.7的版本那么它底层的数据结构是数组 + 链表的形式；如果是jdk1.8，则数据结构是数组 + 链表 + 红黑树。
那么为什么要引入红黑树呢？ 最主要的原因是链表的查询效率是非常低的。比如在1.7的情况下，当我们的多个key插入到map中，寻址的index 值相同、发生冲突的情况下就会存入到一个链表中，当我们查询的时候，就需要从头节点到尾结点一个一个遍历，效率非常低，时间复杂度为O(n)， 而红黑树是一种自平衡的二叉排序树，可以使查询的时间复杂度优化成O(logn)

谈一下HashMap的扩容机制？

为了方便说明，这里明确几个名词：

• capacity 即容量，默认16
• loadFactor 加载因子，默认是0.75
• threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。

什么时候触发扩容？
一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。
HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长。
迁移的巧妙设计：
扩容会将老数组里的数据迁移到新数组，jdk8中迁移的代码设计的很巧妙：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图：

数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash然后寻址计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“原长度+原坐标”。如下图：

因此，在扩容时，不需要重新计算元素的hash了，只需要判断最高位是1还是0就好了
源码中用 e.hash & oldCap 这段代码来判断高位是1还是0

谈一下hashMap中put函数是如何实现的？

总结：

1.计算关于key的hash值（与Key.hashCode的高16位做异或运算）

2.如果散列表为空时，调用resize()初始化散列表

3.根据当前key的hash值找到它在数组中的下标，若当前下标不存在元素，则直接添加元素到该位置

4.若当前下标已存在元素，进行三种判断
4.1:若当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，则新值覆盖替换旧值
4.2:如果是红黑树结构，就调用树的插入方法
4.3：链表结构，循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表个数是否到达变成红黑树的阙值8；若遍历到有节点与插入元素的key相同，则进行覆盖。

5.如果桶满了大于阀值，则resize进行扩容
上源码：

//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;
}

容量为什么必须是2的幂？

容量为什么必须是2的幂？

这点就不得不提起HashMap中为节点寻址代码了（寻找合适下标）i = (n - 1) & hash
就是 数组的长度-1 与 hash值做与运算

为什么这样处理？
我们知道，如果给定某个数值，去找它在某个数组中的下标位置时，直接用模运算就可以了。
而HashMap的寻址代码是 n-1 & hash，只有n为2幂次方，n-1对应的二进制为才是类似与1111这种格式，这时再与hash值做与运算 就能达到求模的效果。因此这个运算就可以实现取模运算，而且与运算还有一个好处，就是速度比较快。

总结一下：只有n为2的幂次方，n-1的低位才是1111这种形式，进而n-1 & hash达到取模的效果。
若构造HashMap时传来的initialCapacity（初始化容量）不是2次幂值怎么办？

其实若你传的初始容量不是2次幂，HashMap源码中会调用tableSizeFor方法，把我们指定的容量改为一个大于它的最小2次幂值，例如传来的容量是14，则最终容量设置的是16

源码中处理初始值的方法如下：

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

谈一下hashMap中的hash函数是如何实现的？

HashMap中的hash(key)函数是如何实现的？

直接上源码：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

先获取key的hashCode值，然后拿该值的高16位 与 低16位 进行异或处理

为什么这样处理？

当数组的长度很短时，只有低位数的hashcode值能参与运算。而让高16位 与 低16位 异或处理，使得高16位和低16位的信息都被保留了，可以更好的均匀散列，减少碰撞，进一步降低hash冲突的几率。

什么是异或运算？为什么要用异或运算 而不是 与运算 或者 或运算？

异或运算：参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。

两个值进行与运算，结果会趋向于0；或运算，结果会趋向于1；而只有异或运算，0和1的比例可以达到1:1的平衡状态。
还有哪些hash函数的实现方式？

平方取中法，除留余数法，伪随机数法

为什么不直接将key作为哈希值而是与高16位做异或运算？

当数组的长度很短时，只有低位数的hashcode值能参与运算。而让高16位 与 低16位 异或处理，使得高16位和低16位的信息都被保留了，可以更好的均匀散列，减少碰撞，进一步降低hash冲突的几率。

谈一下当两个对象的hashCode相等时会怎么样？

会产生哈希碰撞，若key值相同则替换旧值，不然链接到链表后面，链表长度超过阙值8就转为红黑树存储

谈一下hashMap中什么时候需要调用resize()?

1.初始化数组table
2.当数组table的size达到阙值时即 负载因子 * 数组容量 时

扩容resize()又是如何实现的？

1 先确定扩容后的容量大小（capacity）和 阈值（threshold）

通过判断旧数组的容量是否大于0来判断数组是否初始化过？

是，capacity 和 threshold 都变为原来的2倍

否，再分有参构造和无参构造两种。
无参构造： 使用默认的大小和阈值
有参构造： 使用构造函数中初始化的容量，当然这个容量是经过tableSizefor计算后的2的次幂数

2 若是初始化，就直接返回初始化的数组

3 若是扩容，那么我们就需要把原来数组中的元素 迁移 到新的数组中

迁移的巧妙设计：
扩容会将老数组里的数据迁移到新数组，jdk8中迁移的代码设计的很巧妙：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图：

数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash然后寻址计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“原长度+原坐标”。如下图：

因此，在扩容时，不需要重新计算元素的hash了，只需要判断最高位是1还是0就好了
源码中用 e.hash & oldCap 这段代码来判断高位是1还是0
看源码：

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;
}

谈一下hashMap中get函数是如何实现的？

总结：

1. 对key的hashCode进行hash运算。
2. 根据hash值进行寻址算出桶的位置。
3. 如果在桶的首位上就可以找到就直接返回。否则在树中找或者链表中遍历找。
4. 如果有hash冲突，则利用equals方法去遍历链表查找节点。
   上源码：

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;
}

谈一下当两个对象的hashCode相等时会怎么样？

会产生哈希碰撞，若key值相同则替换旧值，不然链接到链表后面，链表长度超过阙值8且数组长度超过64就转为红黑树存储

如果两个键的hashcode相同，你如何获取值对象？

HashCode相同，通过equals比较内容获取值对象

平时在使用HashMap时一般使用什么类型的元素作为Key？

选择Integer，String这种不可变的类型，像对String的一切操作都是新建一个String对象，对新的对象进行拼接分割等，这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的，

HashMap和HashTable的区别

相同点：都是存储key-value键值对的
不同点：

• HashMap允许Key-value为null，hashTable不允许；
• hashMap没有考虑同步，是线程不安全的。hashTable是线程安全的，给api套上了一层synchronized修饰;
• HashMap继承于AbstractMap类，hashTable继承与Dictionary类;
• 容量的初始值和增加方式都不一样：HashMap默认的容量大小是16；增加容量时，每次将容量变为"原始容量x2"。Hashtable默认的容量大小是11；增加容量时，每次将容量变为"原始容量x2 + 1"；
• 添加key-value时的hash值算法不同：HashMap添加元素时，是使用自定义的哈希算法。Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。

参考的文章链接：https://blog.csdn.net/qq_26542493/article/details/105482732
B站上视频链接：https://www.bilibili.com/video/BV1LJ411W7dP?p=8&spm_id_from=pageDriver
推荐红黑树学习文章：【红黑树的简单理解】