简书 加薪猫
转载请注明原创出处，谢谢！
这一系列主要介绍HashMap(1.8)，记录也是分享，欢迎讨论
0.HashMap 结构
HashMap 的数据存在哪里？数据结构是什么？
1.HashMap所有的key-value,存在一个全局变量Node<K,V>[] table里面。
2.Node<K,V> 这个的结构具体看代码
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;
}
}
hash用来存储这个Node中key经过HashMap的hash(K key)方法计算后得出的，key、value不说了，next存储一下个Node节点。HashMap是数组+链表的形式存储的，当然这个Node的子类还有TreeNode，这个我们之后再说
哈希值是否有重复？为什么要用链表存储？
按理说哈希值是不会有重复的，java Object类中的hashCode方法使用类的地址转int，保证了hash值的唯一性，虽说哈希值不会重复，但是在存储时我们还是会发生冲突的，具体我们可以看下面的介绍，用链表存储就是为了解决冲突问题的，具体可以仔细研究1.1.2节。其次1.8不仅用链表，当链表长度超过默认值（8）时，HashMap还会把这个链表转为红黑树，这也是为了提升查找效率。
正文
HashMap源码中最有用，最值得看的就是resize()扩容方法，直接去看resize()方法肯定是一头雾水。
所以这里是从我们最常用的方法一步步去分享。
1. get(Object key)
直接上代码
public V get(Object key) {
Node e;
return(e = getNode(hash(key),key)) ==null?null: e.value;
}
get方法里面主要就是hash 和 getNode
1.1 hash(Object key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.1.1 hashCode
所有对象都会有也是必须有hashCode()方法的，这也就是为什么HashMap的Key要求必须是对象的原因（不可用基本类型，int,long,等等）。当然Value也是要求必须是对象的，为什么就待日后再说。
这是Object类里面hashCode()方法。
public native int hashCode();
一个不常见的关键词 native，使用native关键字说明这个方法是原生函数，也就是这个方法是用C/C++语言实现的。。。后面的不想说啦，既然是C系列那么就不在在下的关注之中了，我们回到源码Object对这个函数的描写
* Returns a hash code value for the object. This method is
* supported for the benefit of hash tables such as those provided by
* {@link java.util.HashMap}.
* 返回对象的哈希值，这个方法是为了给哈希表提供帮助的（也就是这次讲的HashMap）
* <p>
* The general contract of {@code hashCode} is:
* 约束是
* <ul>
* <li>Whenever it is invoked on the same object more than once during
* an execution of a Java application, the {@code hashCode} method
* must consistently return the same integer, provided no information
* used in {@code equals} comparisons on the object is modified.
* This integer need not remain consistent from one execution of an
* application to another execution of the same application.
* 在一个java应用执行中，对同一个对象多次调用 hashCode()方法，必须返回相同的整形，
* 这个前提是在对象的比较中，没有任何信息被修改.相同程序在多次分别执行时，是不需要相同的
* <li>If two objects are equal according to the {@code equals(Object)}
* method, then calling the {@code hashCode} method on each of
* the two objects must produce the same integer result.
* 如果两个对象调用equals()方法是相等的，那么调用hashCode方法的返回也是相同的
* <li>It is <em>not</em> required that if two objects are unequal
* according to the {@link java.lang.Object#equals(java.lang.Object)}
* method, then calling the {@code hashCode} method on each of the
* two objects must produce distinct integer results. However, the
* programmer should be aware that producing distinct integer results
* for unequal objects may improve the performance of hash tables.
* 两个不相等的对象，（不）要求hashCode相同，但是程序猿需要知道，给不相等对象提供不同的
* hash值有利于hash表的查询
* </ul>
* <p>
* As much as is reasonably practical, the hashCode method defined by
* class {@code Object} does return distinct integers for distinct
* objects. (This is typically implemented by converting the internal
* address of the object into an integer, but this implementation
* technique is not required by the
* Java™ programming language.)
* 呵呵，Object自己的hashCode方法在不同的对象上返回不同的整形
*（这是依赖内部地址转换为整形来实现，但是我们重写这个方法的时候不要求这样~）
*
* @return a hash code value for this object.
* @see java.lang.Object#equals(java.lang.Object)
* @see java.lang.System#identityHashCode
1.1.2 >>>
Object.hashCode()已经返回了这个对象的hash值，那么为什么HashMap里面还有有个hash方法呢？
(h = key.hashCode()) ^ (h >>> 16)
这个操作的高度概括就是让Key的哈希值高位参与运算。
为什么要高位参与运算呢？
我们算出来的哈希值是一个int型，2进制32位带符号的int是-2147483648~2147483648，其实很难会发生碰撞(上面也说到了，Object提供的hashCode方法算出来不同对象的哈希值是不会有重复的)，如果我们直接使用哈希值作为数组下标访问的话，内存是吃不消的，所以这个算出来的哈希值之后会和 当前HashMap的大小做取模运算得到的余数 当前HashMap的大小-1 做与运算作为下标
p = tab[index = (n - 1) & hash]
这一段是之后put方法中使用获得下标的语句，这个我们之后再讲，根据上面的代码，我们再看。HashMap的默认大小是2^4=16,换算成32位的样式就是
0000 0000 0000 0000 0000 0000 0001 0000 -->16
0000 0000 0000 0000 0000 0000 0000 1111 -->15
当我们拿着15去做与运算的时候
从0000 0000 0000 0000 0000 0000 0000 0000
到1111 1111 1111 1111 1111 1111 1111 0000
所有低四位为0的对象，在这个HashMap中都会存到下标为0的对象里面，不考虑扩容等问题，这样的HashMap(1.8之前)他的查找效率就跟链表一样，即使1.8将链表大小超过8的链表转为红黑树，这也不是HashMap的设计初衷。
但是我们将算出来的哈希值右移16位后取异或，那么就当前大小16的HashMap来说，参与运算的就不只是0 ~ 3位，是0 ~ 3和16 ~ 19位共同的计算结果，这个操作使我们的分布更加均匀。
而我们的HashMap的大小默认值是16也就是2^4，而有符号int标志范围。
顺便一提的是这也是为什么我们HashMap的大小必须2的幂次方，因为这样，大小-1正好是地位掩码。
1.2 getNode(int hash,Object key)
以上，我们知道了在HashMap中哈希值的计算方式，下面我们要讨论的是取到hash值之后，我们要怎么去取到具体的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，最底层的数据结构是Node<K,V>[],其实这段代码蛮好懂的，就是几个条件，唯一值得注意的地方就是，我们在具体判断的时候，首先判断((k = e.key) == key),其次我们还要判断(key != null && key.equals(k))，==和equals的区别就不赘述了。
从一个get方法我们也可以看出，如果我们想用自己新建的一个类作为HashMap的key,我们一定要正确的重写这个类的hashCode()和equals()方法，不然最终的结果可能并不是我们想要的。
这段代码里面还有与之前JDK版本相比最大的区别就是引入了红黑树，这段代码也可以看到，如果我们这个节点是TreeNode的话，我们会使用TreeNode的getTreeNode(hash,key)的方法获得我们想要的Node节点，如果不是TreeNode的话，我们会遍历链表。
今天先到这里~
我是加薪猫
技术是加薪的前提，生活是加薪的意义
技术等于生活
网友评论