一、HashMap的顶部注释
既然是从头剖析HashMap那么就研究的更加的深入和彻底一些，我们不放过任何细小的地方进行源码的解析，所以首先我们先来看看HashMap的顶部注释，看看官方是如何对于HashMap做的注解
/* Hash table based implementation of the <tt>Map</tt> interface. This* implementation provides all of the optional map operations, and permits* <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>* class is roughly equivalent to <tt>Hashtable</tt>, except that it is* unsynchronized and permits nulls.) This class makes no guarantees as to* the order of the map; in particular, it does not guarantee that the order* will remain constant over time./
- 基于哈希表的Map接口实现。 该实现提供了所有的可选的映射操作，并且允许key和value为空
- HashMap对象的key、value值均可为null ， HahTable对象的key、value值均不可为null。 且两者的的key值均不能重复，若添加key相同的键值对，后面的value会自动覆盖前面的value，但不会报错 ；
- 还有一个不同点就是在同步上，HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的
1.1 为什么HashMap的key值允许为空？但是HashTable的Key值不允许为空？
HashMap从源码分析，HashMap的put方法是实现如下：
HashMap在put的时候会调用hash()方法来计算key的hashcode值，可以从hash算法中看出当key==null时返回的值为0。因此key为null时，hash算法返回值为0，不会调用key的hashcode方法。
HashTable从源码分析：
上面可以看出当Hashtable存入的value为null时，抛出NullPointerException异常。如果value不为null，而key为空，在执行到int hash = key.hashCode()时同样会抛出NullPointerException异常
**
总结：
- HashMap在put的时候会调用hash()方法来计算key的hashcode值，可以从hash算法中看出当key==null时返回的值为0。因此key为null时，hash算法返回值为0，不会调用key的hashcode方法。
- 当Hashtable存入的value为null时，抛出NullPointerException异常。如果value不为null，而key为空，在执行到int hash = key.hashCode()时同样会抛出NullPointerException异常
1.2 什么Hashtable是线程安全的，而HashMap是线程不安全的？
Hashtable解析
Hashtable在jdk1.1就有了，那么它是怎样实现线程安全的呢？主要看put、remove、get方法猜它肯定进行的同步控制的。于是看源码：
//get它搞成了同步方法，保证了get的安全性public synchronized V get(Object key) {……}//synchronized,同样public synchronized V put(K key, V value) {……}//也是搞成了同步方法public synchronized V remove(Object key) {……}
每个操作数据的方法都进行同步控制之后，由此带来的问题任何一个时刻只能有一个线程可以操纵Hashtable，所以其效率比较低。
二、HashMap的数据结构
JDK1.8之前的HashMap都采用上图的结构，都是基于一个数组和多个单链表，hash值冲突的时候，就将对应节点以链表形式存储。如果在一个链表中查找一个节点时，将会花费O(n)的查找时间，会有很大的性能损失。到了JDK1.8，当同一个Hash值的节点数不小于8时，不再采用单链表形式存储，而是采用红黑树。
三、HashMap成员变量
// 默认 桶（数组） 容量 16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 最大容量 2的31次方static final int MAXIMUM_CAPACITY = 1 << 30;// 默认负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;// 链表转树 大小// 当添加一个元素被添加到有至少TREEIFY_THRESHOLD个结点的桶中，桶中的链表转化为树形结构static final int TREEIFY_THRESHOLD = 8;// 树转链表 大小static final int UNTREEIFY_THRESHOLD = 6;// 最小转红黑树容量static final int MIN_TREEIFY_CAPACITY = 64;// 存储数据节点static class Node<K,V> implements Map.Entry<K,V>// 节点数组transient Node<K,V>[] table;// 数据容量transient int size;// 操作次数transient int modCount;// 在HashMap中，threshold = loadFactor * capacity。int threshold;
对比于JDK8之前的HashMap ，成员变量主要的区别在于多了红黑树的相关变量，用于标示我们在什么时候进行 list -> Tree 的转换。
再来看一下HashMap的一个内部类Node:
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;}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;}}
四、HashMap 构造函数
HashMap 提供了四种构造函数：
- HashMap（）：默认构造函数，参数均使用默认大小
- HashMap（int initialCapacity）：指定初始数组大小
- HashMap（int initialCapacity, float loadFactor）：指定初始数组大小，加载因子
- HashMap(Map<? extends K, ? extends V> m)
其中我们最常用的构造函数看：
public HashMap(int initialCapacity, float loadFactor) {// 初始容量不能小于0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 初始容量不能大于2^31if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 负载因子=表中的记录数/哈希表的长度 不能小于0if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +// 初始化加载因子 loadFactor);this.loadFactor = loadFactor;// 设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行自动扩容操作this.threshold = tableSizeFor(initialCapacity);}/*** Returns a power of two size for the given target capacity.* tableSizeFor的功能（不考虑大于最大容量的情况）是返回大于输入参数且最接近的2的整数次幂的数。比如10，则返回16。*/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;}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}
- 初始容量不能小于0，小于0的时候回跑出异常出来。初始容量不能大于2^31，当初始的容量大于2^31的时候就会设置最大的也是2^31
- tableSizeFor算法返回大于输入参数且最接近的2的整数次幂的数。比如10，则返回16。
4.1 tableSizeFor算法
先来分析有关n位操作部分：先来假设n的二进制为01xxx…xxx。接着
- 对n右移1位：001xx…xxx，再位或：011xx…xxx
- 对n右移2为：00011…xxx，再位或：01111…xxx
- 此时前面已经有四个1了，再右移4位且位或可得8个1
- 同理，有8个1，右移8位肯定会让后八位也为1。
综上可得，该算法让最高位的1后面的位全变为1。最后再让结果n+1，即得到了2的整数次幂的值了。
现在回来看看第一条语句：
int n = cap - 1;
让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。
3、resize 如何实现的， 记住已经没有 rehash 了！！！（答：拉链 entry 根据高位 bit 散列到当前位置 i 和 size+i 位置）
4、为什么获取下标时用按位与 &，而不是取模 %？ （答：不只是 &速度更快哦， 我觉得你能答上来便真正理解 hashmap 了）
五、put()方法
put方法可以说是HashMap的核心，我们来看看一个总的介绍图5、什么时机执行 resize？
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}
上述方法是我们在开发过程中最常使用到的方法，但是却很少人知道，其实内部真正调用的方法是这个putVal(hash(key), key, value, false, true)方法。这里稍微介绍一下这几个参数：
- hash 值，用于确定存储位置
- key：存入键值
- value：存入数据
- onlyIfAbsent：是否覆盖原本数据，如果为true 则不覆盖
- evict：table 是否处于创建模式
5.1 key的hash运算实现原理
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
5.1 HashMap什么时候执行resize，是如何执行resize的
面试题
1、HashMap在使用的时候需要注意什么
需要设置初始化容量的大小，而且最好是2的指数次方幂，需要设置初始化容量的大小是，因为如果默认使用的是初始值16的化，后面map中存放了大量的数据，就需要进行扩容的操作，每一次扩容都是需要进行rehash()的。为什么需要设置的是值是2的指数次方幂的大小呢？因为会在第一次进行put方法操作的时候，把当前的容量capacity设置为2的指数次方幂的大小，如果你自己设置的就是2的指数次方的值，那么就会减少计算的发生。那么为什么需要是2的指数次幂，
2、扩容为什么可能会出现死锁呢
2、为什么加载因子是0.75呢
2、HashMap的工作原理是什么？
HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Node 。
以下是具体的put过程（JDK1.8版）
1、对Key求Hash值，然后再计算下标 2、如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中） 3、如果碰撞了，以链表的方式链接到后面 4、如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表 5、如果节点已经存在就替换旧值 6、如果桶满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排）
以下是具体get过程(考虑特殊情况如果两个键的hashcode相同，你如何获取值对象？)
- 当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，
- 找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。
3、有什么方法可以减少碰撞？
扰动函数可以减少碰撞，原理是如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这就意味着存链表结构减小，这样取值的话就不会频繁调用equal方法，这样就能提高HashMap的性能。（扰动即Hash方法内部的算法实现，目的是让不同对象返回不同hashcode。）
使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。为什么String, Interger这样的wrapper类适合作为键？因为String是final的，而且已经重写了equals()和hashCode()方法了。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。
4、HashMap中hash函数怎么是是实现的?
我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。 所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式，我们来看看JDK1.8的源码是怎么做的：
static final int hash(Object key) {if (key == null){ return 0; } int h; h=key.hashCode()；返回散列值也就是hashcode // ^ ：按位异或 // >>>:无符号右移，忽略符号位，空位都以0补齐 //其中n是数组的长度，即Map的数组部分初始化长度 return (n-1)&(h ^ (h >>> 16));}
简单来说就是
1、高16bt不变，低16bit和高16bit做了一个异或(得到的HASHCODE转化为32位的二进制，前16位和后16位低16bit和高16bit做了一个异或) 2、(n·1)&hash=->得到下标
5、拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？
之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。
而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。
6、说说你对红黑树的见解？
1、每个节点非红即黑 2、根节点总是黑色的 3、如果节点是红色的，则它的子节点必须是黑色的（反之不一定） 4、每个叶子节点都是黑色的空节点（NIL节点） 5、从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
7、解决hash 碰撞还有那些办法？
开放定址法。
当冲突发生时，使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的地址。 按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。 下面给一个线性探查法的例子 问题：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。 解答：为了减少冲突，通常令装填因子α由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。 前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。 当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。 当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。 当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。 类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。
8、如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。
这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置
9：为什么String, Interger这样的wrapper类适合作为键？
String, Interger这样的wrapper类作为HashMap的键是再适合不过了，而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。
若有收获，就点个赞吧
0 人点赞
