1.HashMap数据结构
HashMap底层数据结构为hash表，也称散列表。hash表是根据键值key直接访问内存中数据存储位置的数据结构，也就是说通过key值将数据映射到相对应的内存储存位置中，映射函数也被称为散列函数。hash表是典型的空间换时间的数据结构，因为能根据key直接访问到具体的数据存储位置，所以hash表查找的时间复杂度可以到达极致的O(1)。然而，在一段一定长的储存位置中进行key值的映射，不可避免地就会产生不同key值映射的位置相同，即出现冲突，当出现冲突时的解决方案一般有：开放定址法，链表法，再散列等。
2.Java中HashMap源码(jdk 1.8)
先上一段简单的代码
public static void main(String[] args) {
HashMap hashMap=new HashMap();
//存值
hashMap.put("key1",1);
//取值
hashMap.get("key1");
}
put方法即是将key1-1的键值对存入hashmap中，再通过get方法，用key1将相对应的值1取出来。那...put方法调用时具体发生了什么？HashMap是如何解决冲突的？get时又发生了什么？...解决这些问题的最快捷最直接的方式就是查看源码。于是，我就用我的宇宙第一IDE——IntelliJ IDEA 点开了HashMap源码（手动狗头）
public V put(K key, V value) {
//调用了hash方法和putVal方法
return putVal(hash(key), key, value, false, true);
}
//先康康hash方法
//hash方法实际上是一个扰动函数
static final int hash(Object key) {
int h;
//1.若key==null 则返回0
//2.若key!=null 则返回key的hash值与其自身右移16位后的数进行异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看到这里不禁会疑惑为什么要做这一步骚操作，直接返回hash值不行吗？为解决这个问题我们接下来康康putVal方法，康康这个方法到底用hash(key)干了些什么。
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value 是否不允许替换旧值
* @param evict if false, the table is in creation mode. 该参数服务于afterNodeInsertion(evict); 该方法于HashMap中是个空方法，服务于HashMap的子类LinkedHashMap
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//transient Node<K,V>[] table; table为其成员变量 是一个Node键值对数组
//若table为null或者table的数组长度为0
if ((tab = table) == null || (n = tab.length) == 0)
//进行扩容操作 并将扩容之后的数组长度赋给n
n = (tab = resize()).length;
//若 数组下标为[数组长度-1&hash]的元素为空
if ((p = tab[i = (n - 1) & hash]) == null)
//在该数组下标元素处插入一个节点
tab[i] = newNode(hash, key, value, null);
//若 数组下标为[数组长度-1&hash]的元素不为空
else {
Node<K,V> e; K k;
//p = tab[i = (n - 1) & hash]
//若p节点的hash值与key的hash值相同
// 若相同 判断p节点key和传入的key是否为同个对象 或者 p节点key和传入的key是否一致
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//若p为红黑树的树结点
else if (p instanceof TreeNode)
//调用p节点的putTreeVal
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//若不在头节点也不为红黑树
//故为链表
else {
//遍历链表
//binCount记录节点个数
for (int binCount = 0; ; ++binCount) {
//若链表中不含key
if ((e = p.next) == null) {
//创建新节点
p.next = newNode(hash, key, value, null);
//static final int TREEIFY_THRESHOLD = 8;
//若此时链表(包含链表头)大于等于8个节点
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//将该链表转化为红黑树
treeifyBin(tab, hash);
break;
}
//若链表包含key 此时key值节点为e节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//若链表包含key
if (e != null) { // existing mapping for key
V oldValue = e.value;
//若允许替换值或旧值为空
if (!onlyIfAbsent || oldValue == null)
//节点赋新值
e.value = value;
//空方法 服务于HashMap的子类LinkedHashMap
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//修改次数+1 用于迭代器的快速失败
++modCount;
//若容量大于阈值
if (++size > threshold)
//进行扩容操作
resize();
//空方法 服务于HashMap的子类LinkedHashMap
afterNodeInsertion(evict);
return null;
}
源码中，p = tab[i = (n - 1) & hash]操作是通过将key的hash值和数组长度-1相与去获取key值在Node数组上的映射位置，其中数组长度被hashmap强制设置为2的幂。为什么要强制设置为2的幂呢？2的幂有什么好处？
当数组长度为2的幂时，转化为二进制即为只有一位为1的情况，以16举例：1 0000，此时减一就会变成：0 1111
这时候假设有一hash值为1010 1110 1011的key & 15得
1010 1110 1011
&
0000 0000 1111
---------------
0000 0000 1011
我们再举一个例子
1010 1110 1011
&
0000 0000 1101
---------------
0000 0000 1001
===============
1010 1110 1001
&
0000 0000 1101
---------------
0000 0000 1001
我们可以看到hash值&1111后，低位全部得到保留
但如果我们用hash值&1101后，我们发现倒数第二位永远为0，会导致分布不均匀以及冲突的增多
所以采用2的幂作为数组长度能够保证映射的均匀
再回到我们之前的问题：hash方法的作用是什么？
前面我们已经知道，使用2的幂作为数组长度的好处，它能完全保留hash的低位，然而，光靠hash值的低位就能保证映射的均匀吗？答案是否定的，我们如果直接用key的hash值进行&操作就意味着直接抛弃hash值的高位，那能不能将高位的信息保留到低位呢？hash方法就是做的这项工作
//hash方法代码
//1.若key==null 则返回0
//2.若key!=null 则返回key的hash值与其自身右移16位后的数进行异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
image-20200517160759674.png
hash值为int类型，占4个字节(byte)，32位(bit)；右移16位再和自身进行异或运算混合了hash值的高位和低位，由此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
在putVal这个方法中，调用了resize方法，该方法用于数组的扩容，而且在putVal方法最初会检查Node数组是否为空，若为空就进行一次扩容操作，这次扩容就是Node数组的初始化。接下来就让我们康康resize方法
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
/**
* The default initial capacity - MUST be a power of two.
*/
//static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//获取旧数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取旧阈值
int oldThr = threshold;
//初始化新数组长度和新阈值
int newCap, newThr = 0;
//若旧数组长度大于0
if (oldCap > 0) {
//若数组长度大于最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
//将阈值等于Integer的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
//若新数组长度=旧数组长度*2 且 新阈值小于最大容量
// 且旧数组长度大于默认初始值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新阈值等于旧阈值*2(采用位运算是因为位运算更加高效)
newThr = oldThr << 1; // double threshold
}
//此时数组长度不大于0(即为初始化状态) 若旧阈值大于0 代表的是初始设置了容量和阈值的情况
else if (oldThr > 0) // initial capacity was placed in threshold
//这种情况在自定义初始化hashmap时会出现
//将新数组长度等于旧阈值
newCap = oldThr;
//若旧阈值也不大于0 代表的是初始情况
else { // zero initial threshold signifies using defaults
//新数组长度等于DEFAULT_INITIAL_CAPACITY 也就是为16
newCap = DEFAULT_INITIAL_CAPACITY;
//新阈值=16*0.75
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//对应初始设置了容量和阀值的情况
if (newThr == 0) {
//计算新阈值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将新阈值赋给threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//进行rehash操作 新建一个Node数组，将旧数组中的元素转移到新数组中
if (oldTab != null) {
//遍历数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//若旧数组对应元素位置不为空
if ((e = oldTab[j]) != null) {
//将旧数组元素置空
oldTab[j] = null;
//若后续无链
if (e.next == null)
//将该节点置入新数组
newTab[e.hash & (newCap - 1)] = e;
//若该节点为红黑树头节点
else if (e instanceof TreeNode)
//进行红黑树节点rehash操作
((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 {
next = e.next;
//表示该节点rehash之后位于低位
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//表示该节点rehash之后位于高位
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//若低位有节点 置于新数组 j 处
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//若高位有节点 置于新数组 j+旧数组.len 处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
在resize方法的源码中，如果我们没有指定HashMap的初始长度和阈值时，hashmap会为我们默认初始化一个长度为16的数组，16也是2的幂。这时候，有小伙伴就要问了，hashmap有为用户提供初始化hashmap大小的构造方法，那可不可以搞破坏，把hashmap的初始长度设置为不为2的幂，从而降低这个hashmap的性能呢？嘿嘿嘿，那就来康康hashmap的构造方法吧。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//initialCapacity：初始容量
//loadFactor：负载因子
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);
}
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
其中的tableSizeFor方法是为了让传入的参数转化成2的幂，具体过程可以看看下面这张图
image-20200517164124229.png
所以，就算我们把初始容量设置成乱七八糟的数字，hashmap也会把你所设置的初始容量改成2的幂
image-20200517164556401.png
说完了put方法，get相比之下就简单很多了，下面是get方法源码，相信都是看的懂了的(手动狗头)
public V get(Object key) {
Node<K,V> e;
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
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);
}
}
return null;
}
参考文献：
HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）
网友评论