1 存储数据结构
分析源码之前，先了解两个数据结构，数组和链表。
1.1 数组
- 内存中分配固定的空间
- 删除或者增加，导致数组下标内存位移，效率低
- 数组大小固定不利于扩增
- 随机读取的效率高，因为数组是连续的，知道内存地址，可以直接获取
Object [] arrays;
1.2 链表
- 链表的内存大小不固定
- 删除增加数据方便，因为每一个链表节点存储了节点的数据和下一节点的内存地址（单项或者双向）
- 查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。
- 方便扩容，增删效率高
Node {
Object data;
Node next;
Node prex;
}
1.3 集合特性
对于集合框架我们的关注点一般在一下几点：
- 集合底层实现的数据结构是什么 数组+链表+红黑树
- 集合中元素是否允许为空 key和value都可以为空
- 是否允许重复的数据 key不可以，value可以
- 是否有序(这里的有序是指读取数据和存放数据的顺序是否一致) 否
- 是否线程安全。 否
2 HashMap
通过上面我们看到数组查询效率高，增删效率低，而链表反之，那么问题来了，有没有一种结构结合二者的优点？我们看下hashMap，直接上码！
依赖关系
HashMap主要是继承自AbstractMap，实现了Cloneable和Serializable接口使得HashMap具有克隆和序列化的功能、实现了Map接口因此具有Map的性质。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
简单写个main，put etc..
HashMap map=new HashMap();
map.put("c","123");
点击put方法进入源码世界
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
看english注解，发现如果你put的key已经存在的话，处理完会覆盖之前的值，并且返回旧值，but putVal后面多了两个参数，先不管他,这个hash(key)有必要了解下，go on
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
h>>>16代表右位移，低位溢出，符号位不变，并用符号位补溢出的高位，那么看下hashCode()方法，打开Object类，可以看到
public native int hashCode();//c++写的貌似我看不到
public int hashCode() {//这个是String类下重写的
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
public static int hashCode(int value) {//这个是Interger类重写的
return value;
}
//etc...
原来不同对象都可以重写此方法，获取一串不唯一的数字，然后做右移操作，然而这个值来干啥呢？go on！
/**
* 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.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
}
好，来到这里终于知道之前的两个参数啥意思了，putVal(hash(key), key, value, false, true); onlyIfAbsent if true, don't change existing value，evict if false, the table is in creation mode
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
初始化为空的走扩容，下面着重看下resize方法,只考虑初始化，删除其他的代码
final Node<K,V>[] resize() { //通过这个方法也能看出，map的本质是Node数组
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;//这个说明鬼，接着往下看
int newCap, newThr = 0;
newCap = DEFAULT_INITIAL_CAPACITY;//点击看默认16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//这个是总大小*负载因子，默认0.75
}
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//开辟数组
table = newTab;
return newTab;
}
内存有了，接着走，根据hash取存储下标，如果这个地方没有值，那就存数据
if ((p = tab[i = (n - 1) & hash]) == null)//经过高位运算的hash值和数组的大小-1取与，也就是说取值的范围0-15也就是数组的下标
tab[i] = newNode(hash, key, value, null);
································································································································
//在回顾下node的结构，单链表
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;//hash在这里
this.key = key;
this.value = value;
this.next = next;
}
那么问题来了hash值一样了怎么办？ 怎么会一样，比如String a，Interger 97
HashMap map=new HashMap();
map.put(new String("a"),"a");
map.put(new Integer(97),97);
//String hashCode 方法
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
//Interger hashCode 方法
public static int hashCode(int value) {
return value;
}
如果存在相同的hash值，那么第二个来的时候必然已经存在
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //如果key是同一个对象，把存在的节点赋值给e，那值怎么办？别着急赋值在后面
else if (p instanceof TreeNode)//1.8新增的一种结构，稍后看
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//这里就是解决hash冲突的地方了
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 多了个限制，防止链表无限扩充吧，稍后分析
treeifyBin(tab, hash);
break;
}
//链表已经存在冲突的hash数据，如果key对象和再次传过来的一样，直接返回当前node的节点，即更改引用。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 最后复制操作来了
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//开关+以前的数据为空，就覆盖
e.value = value;
afterNodeAccess(e);
return oldValue;
}
上面代码可以看到遍历当前的Node节点，看他的下一个是不是存在，如果不存在，就放在他下一个的位置
那么极端情况，hash一直冲突，Node就可以无限增长了吗，肯定是不可以的。
TREEIFY_THRESHOLD 看下源码大小限制为8,超过了走treeifyBin()，然后再看下treeifyBin方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();//如果小于64继续扩容
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
超过64转树，小于64通过扩容解决，先瞧瞧不到64继续扩容会怎样，继续看下resize方法的实现
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
进行扩容oldCap << 1 位运算增加一倍，扩容怎么能解决hash冲突？继续往下go
最下面，循环遍历旧的数组，针对没有子节点的链表，重新计算index的位置，赋值。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
接着针对有子节点的Node
/**
JDK1.7中，resize时，index取得时，全部采用重新hash的方式进行了。JDK1.8对这个进行了改善。
以前要确定index的时候用的是(e.hash&oldCap-1)，是取模取余，而这里用到的是(e.hash &oldCap)
它有两种结果，一个是0，一个是oldCap，
比如oldCap=8,hash是3，11，19，27时，
(e.hash & oldCap)的结果是0，8，0，8，这样3，19组成新的链表，index为3
而11，27组成新的链表，新分配的index为3+8；
JDK1.7中重写hash是(e.hash & newCap-1)，也就是3，11，19，27对16取余，也是3，11，3，11，
和上面的结果一样，但是index为3的链表是19，3，index为3+8的链表是27，11，
也就是说1.7中经过resize后数据的顺序变成了倒叙，而1.8没有改变顺序。
**/
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
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;
}
也就是说针对e.hash & oldCap=0的保持原来的索引位置不变，为1的原索引位置+原数组的大小，这也是是1.8针对1.7做的优化。回过头来再分析下如果数组Node总大小大于64了会怎样？
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
接下来分析不下去了，因为要补下红黑树的知识点。。。先分析下get接口，关键代码如下
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;//直接找到返回value值
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;
}
网友评论