1.概念
HashMap是Java中最常用的集合类之一，以<K,V>的形式来进行数据存储。常用来比较的还有HashTable，ConcurrentHashMap 等。
2.数据结构
什么是数据结构，在我的认识中，我们的数据需要存储在计算机中，那么它的存储形式，就是一个个的数据结构。常见的数据结构包括：数组，链表，二叉树，红黑树等等
提起hashMap内部的数据结构 那么大多数开发者都可以说出 在其内部是维护了一个数组，数组的每个元素又是一个单向链表。在1.7之前的版本中，这是没错的，但是维护单向链表由此带来的一个缺点就是当我们的hashMap发生大量的指针碰撞之后，当我们需要get其中的一个值的时候，就有可能需要遍历单向链表，那么时间复杂度就是O(n),为解决这一问题，在1.7之后，hashMap中引入了红黑树，将达到一定条件的链表转变为一个红黑树，此时时间复杂度就变为了O(logn)。
问，为何不使用比如线性探测法 往数组的其他位置放 如果长度不够 则进行扩容
答：第一，这样有可能导致 本来数组还有空余位置就触发了扩容，内存浪费。第二，扩容时 需要根据hash值和数组长度重新计算每一个key的hash值，然后重新排列整个map，消耗系统资源。总体上来说，是一个时间换空间的操作。
3.hashMap如何存储数据
接下来就是本文的重点了，hashMap到底是如何存储数据的呢？
让我们带着几个问题来看代码
（1）数组是什么时候进行初始化的
（2）数组在内存中为一块连续的内存地址，所以要求我们在初始化数组是设定数组的长度。那么数组的大小设置为多少呢
（3）hash值如何计算
（4）什么是hash冲突，发生后冲突后hashMap是如何处理的
public V put(K key,V value) {
return putVal(hash(key), key, value,false,true);
}
这就是在hashMap中进行put的方法，我们需要关注两个点 第一，putVal(hash(key), key, value,false,true) 这是进行存储操作的方法；第二，hash（key）这是计算hash值的方法 。
我们先来看第一个
transient Node[]table;
Node[] tab; Node p;int n, I;
//声明了一个Node对象，Node元素中包含了如下变量
final int hash;
final K key;
V value;
Nodenext; //下一个元素的地址引用 佐证了这是一个单向链表
if ((tab =table) ==null || (n = tab.length) ==0) //此处为判断声明的Node[]是否为空
n = (tab = resize()).length; //为空执行resize() 方法
在resize（）方法中 ，当判断oldTab.length==0时 有如下代码
newCap=DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY);
//下面两行是类中声明的常量
static final int DEFAULT_INITIAL_CAPACITY =1 <<4;// aka 16 位运算 即初始化的数组长度
static final float DEFAULT_LOAD_FACTOR =0.75f;// 负载因子
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
我们可以看到，当首次进行put时，进行了数组的初始化，并定义了数组的长度为16，那么问题来了，数组的长度给定了之后，tab[]下标为0-15。如果我们不断插入数据，当key的hash值不在这16个长度之内时会发生什么呢，让我们继续看源码，还是putval（）
if ((p = tab[i = (n -1) & hash]) ==null)
tab[i] = newNode(hash, key, value,null);
通过这两行代码我们可以看到 去计算了一次hash值 当tab[i]==null时，new了Node元素 放了进去 完成了数据存储
如果此时tab[i]不为null则执行下面的代码。
else {
Node e;K k;
if (p.hash == hash &&
((k = p.key) == key || (key !=null && key.equals(k))))
e = p;
在这我们看到 当 k的hash值相等且 equals（）相等的时候，进行了覆盖
else if (pinstanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
k不相等的时候 如果当前Node对象包含了红黑树 那么就把它放在了树里
else {
for (int binCount =0; ; ++binCount) {
if ((e = p.next) ==null) {
p.next = newNode(hash, key, value,null);
if (binCount >=TREEIFY_THRESHOLD -1)// -1 for 1st
TREEIFY_THRESHOLD =8
treeifyBin(tab, hash);
break;
}
对单向链表进行遍历。当p.next==null 是说明这是单向链表的尾结点，指针null。记录单向链表的遍历的次数。 TREEIFY_THRESHOLD=8 当链表长度》=8-1时， 将链表转为红黑树
if (e.hash == hash &&
((k = e.key) == key || (key !=null && key.equals(k))))
break;
//同样是进行key的hash判断 一致则覆盖掉原有值
p = e;
}
}
if (e !=null) {// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
//覆盖的过程
++modCount; //记录put的次数
if (++size >threshold)
resize();
//重点来了 在此时，如果数组需要进行扩容数组在什么时候扩容呢，就是代码中的threshold = newThr
在resize()方法中 如果原有tab长度＞0且＜2的30次方，则tab长度变为原来的<1 即原来的2倍
size这个值在哪计算还没发现 待我稍后进行补充
afterNodeInsertion(evict);
return null;
4.完整的源码
final V putVal(int hash,K key,V value,boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p;int n, i;
if ((tab =table) ==null || (n = tab.length) ==0)
n = (tab = resize()).length;
if ((p = tab[i = (n -1) & hash]) ==null)
tab[i] = newNode(hash, key, value,null);
else {
Node e;K k;
if (p.hash == hash &&
((k = p.key) == key || (key !=null && key.equals(k))))
e = p;
else if (pinstanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount =0; ; ++binCount) {
if ((e = p.next) ==null) {
p.next = newNode(hash, key, value,null);
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)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size >threshold)
resize();
afterNodeInsertion(evict);
return null;
}
本篇解决了1.2.4三个问题 至于第3个问题 改日在叙。如有谬误如疏漏之处烦请各位看官多多指正
网友评论