本文向您展示了如何在JDK7和JDK8中实现HashMap。内容简洁易懂，一定会让你大放异彩。希望通过这篇文章的详细介绍，你能有所收获。
JDK7中的HashMap
底层的HashMap维护一个数组，数组中的每一项都是一个Entry。
瞬态EntryK，V[]表；
我们放入HashMap的对象实际上存储在这个数组中；
而映射中的键和值以条目的形式存储在数组中。
静态类EntryK，V实现Map。EntryK，V {
最终K键；
v值；
EntryK，V接下来；
int hash
这个Entry应该放在数组中的什么位置(这个位置通常叫做位桶或者哈希桶，也就是哈希值相同的条目会放在同一个位置，通过链表连接)，这个位置是通过键的hashCode来计算的。
最终整数散列(对象k){ 0
int h=0；
^=哈什科德()；
^=(h20)^(h12)；
返回h . ^(H7)^(H4)；
}
通过哈希计算的值将使用indexFor方法来查找表下标，它应该位于：
静态int indexFor(int h，int length){ 0
返回h(长度-1)；
}
这个方法实际上相当于模table.length。
当两个密钥由hashCode计算相同时，就会发生哈希冲突(碰撞)。HashMap通过使用链表来解决哈希冲突。
当存在哈希冲突时，将数组中存储的Entry设置为新值的下一个(这里需要注意的是，例如A和B都经过哈希后，都映射到下标I，之前已经有A了。当map.put(B)时，将B放在下标I，A是B的下一个，所以新值存储在数组中，旧值在新值的链表中)
示意图：
所以当有很多哈希冲突的时候，HashMap就会退化成链表。
地图后总结流程。输入：
当把一对键值放入HashMap时，它会根据键值的hashCode值计算一个位置，这个位置就是对象在数组中存储的位置。
如果这个位置没有对象，直接把这个对象放入数组；如果某个对象已经存在于该位置，则开始沿着现有对象链进行搜索(为了确定值是否相同，映射不允许键和值的重复键和值对)。如果该链中有对象，请使用equals方法对它们进行比较。如果该链中每个对象的equals方法的比较结果为false，则将该对象放入数组中，然后将数组中该位置之前存在的对象链接到该对象的后面。
值得注意的是，当键为空时，它被放入表[0]
私有V putforullkey(V值){ 0
for (EntryK，V e=表[0]；e！=nulle=e . next){ 0
if(e . key==null){ 0
V oldValue=e.value
不间断空格
; e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
当size大于threshold时，会发生扩容。 threshold等于capacity*load factor
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
jdk7中resize，只有当 size>=threshold并且 table中的那个槽中已经有Entry时，才会发生resize。即有可能虽然size>=threshold，但是必须等到每个槽都至少有一个Entry时，才会扩容。还有注意每次resize都会扩大一倍容量
JDK8中的HashMap
一直到JDK7为止，HashMap的结构都是这么简单，基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。
这样子的HashMap性能上就抱有一定疑问，如果说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。
JDK7中HashMap采用的是位桶+链表的方式，即我们常说的散列链表的方式，而JDK8中采用的是位桶+链表/红黑树（有关红黑树请查看红黑树）的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。
JDK8中，当同一个hash值的节点数不小于8时，将不再以单链表的形式存储了，会被调整成一颗红黑树（上图中null节点没画）。这就是JDK7与JDK8中HashMap实现的最大区别。
接下来，我们来看下JDK8中HashMap的源码实现。
JDK中Entry的名字变成了Node，原因是和红黑树的实现TreeNode相关联。
transient Node<K,V>[] table;
当冲突节点数不小于8-1时，转换成红黑树。
static final int TREEIFY_THRESHOLD = 8;
以put方法在JDK8中有了很大的改变
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;
int n, i;
//如果当前map中无数据，执行resize方法。并且返回n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果要插入的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上就完事了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//否则的话，说明这上面有元素
else {
Node<K,V> e; K k;
//如果这个元素的key与要插入的一样，那么就替换一下，也完事。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//1.如果当前节点是TreeNode类型的数据，执行putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//还是遍历这条链子上的数据，跟jdk7没什么区别
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//2.完成了操作后多做了一件事情，判断，并且可能执行treeifyBin方法
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //true || --
e.value = value;
//3.
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断阈值，决定是否扩容
if (++size > threshold)
resize();
//4.
afterNodeInsertion(evict);
return null;
}
treeifyBin()就是将链表转换成红黑树。
之前的indefFor()方法消失 了，直接用(tab.length-1)&hash，所以看到这个，代表的就是数组的下角标。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
上述内容就是JDK7与JDK8中HashMap的实现是怎样的，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注行业资讯频道。
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/94849.html