JDK1.8
第一代码块（hashmap俩种构造方法）
/* ---------------- Public operations -------------- */
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
/**
* 用指定的初始值构造一个空的HashMap
* @param initialCapacity 初始容量
*@param loadFactor 负载因子
*@throws IllegalArgumentException 如果初始容量为负值或者负载因子为非正值
*/
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);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
// 默认initial capacity为16 loadfactor(0.75)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
第二代码块（putVal）
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 key, or null if there was no mapping for key.
* (A null return can also indicate that the map previously associated null with key.)
*/
/**
* 将指定值与此映射中的指定键相关联。
* 如果包含该键的映射，则旧的值被替换。
*
*@param key，将与指定值关联
*@param value ，与指定的键关联
*@返回之前与 key 关联的一个值，如果没有键的映射，则返回 null。
*（null返回值也意味着之前key的映射为null）
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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
*/
/**
* 实现 Map.put 和相关方法
* @param hash, hash for key
* @param key, the key
* @param value，the value to put
* @param 如果为true，则不更改现有值 默认为false
* @param 如果false，则表处于创建模式。默认为true 这个参数暂时不知道不知道有什么用
* @返回之前的值，如果没有返回 null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//table的定义：transient Node<K,V>[] table;
n = (tab = resize()).length;
//n为table的长度，长度扩展使用2的幂次方方式来扩展
//hash = hash(key)
//当计算出hash时，使用（n-1）& hash来计算table的下标
if ((p = tab[i = (n - 1) & hash]) == null)
//之前没有添加过tab[i]这个键值对，新建一个元素，添加到table中
tab[i] = newNode(hash, key, value, null);
else {
//已经存在key，通过p=tab[i = (n-1) & hash]拿到存在的key
Node<K,V> e; K k;
//验证表里拿到的元素和传入的元素是否为一个元素
//（其实就是验证key的值以及key的hash）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/**哈希碰撞的情况产生，jdk1.8使用在Java 8之前的实现中是用链表解决冲突的，
在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。
因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。
因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，
这样在n很大的时候，能够比较理想的解决这个问题，在[Java 8：HashMap的性
能提升](http://www.importnew.com/14417.html)一文中有性能测试的结果。
引用自：
https://yikun.github.io/2015/04/01/JavaHashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
*/
else if (p instanceof TreeNode)//判断p是否为TreeNode或者是它的子类的一个实例
e = ((TreeNode<K,V>)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;
//具体注释见第三个代码块,位运算规则在最后
//初始容量为16，负载因子为0.75
//第一次扩容后，当前table的size大于threshold=16*0.75时，触发第二次扩容
//第二次扩容 ，newcap=oldcap<<1，newthreshold=oldthrehold<<1
if (++size > threshold)
//在这个方法中，table与newtable指向同一个对象，所以可以接着操作表
resize();
afterNodeInsertion(evict);
return null;
}
第三代码块（Node）
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
/**
*我认为这就是个链表啊 hash bin 是个什么鬼东西? hash箱子？hash树？那为什么不叫hashtree？ （参见下面的TreeNode子类，以及LinkedHashMap中的Entry子类。）
*/
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;
}
}
第四代码块（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
*/
/**
* 初始化或双倍初始化表大小。
* 当扩展长度时，元素的索引要么相同要么为oldindex+n（n为oldTab.length）通过一些计算就可以得出。
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//static final int MAXIMUM_CAPACITY = 1 << 30;
//static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//static final float DEFAULT_LOAD_FACTOR = 0.75f;
//static final int TREEIFY_THRESHOLD = 8;
//static final int UNTREEIFY_THRESHOLD = 6;
//static final int MIN_TREEIFY_CAPACITY = 64;
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//初始化table，执行这个分支
newCap = DEFAULT_INITIAL_CAPACITY;
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 = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//这一步将table指向newTab的对象，oldTab指向oldTab对象
//仍然可以进行对oldTab的操作
//table将被put重新使用
table = newTab;
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)
((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;
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;
}
}
}
}
}
return newTab;
}
第五代码块（hash）
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
/**
* 计算 key.hashCode ()通过([逻辑异或])与高位和低位的运算结果进行扩展。
* 为什么要通过这种方式呢？因为如果 (在一个小表中以Float类型的key中存放连续的整数，总是会引起hash碰撞)
* 高位转低位h>>>16，目的是使高低位都能参与运算。为什么这么做？暂时没有弄明白
* 因为许多常见的hashcode已经合理分布(所以不能从分布中受益) ，而且因为我们使用树来处理大量的hash冲突，
* 所以我们只是用权衡的方式对高位与低位进行异或运算（h = key.hashCode()) ^ (h >>> 16），这么做是考虑到高位的影响
* 在速度，效用和长度扩展质量之间的一种权衡做法
* 用以减少系统开销，同时考虑到最高位的影响，否则由于表长度的原因，高位永远不会用于索引计算。 因为index =（n-1）& hash， n-1比较小，实际上只会低位参与索引计算。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
以下位运算符规则来自http://www.runoob.com/java/java-operators.html
A = 0011 1100
B = 0000 1101
A & B = 0000 1100
A | B = 0011 1101
A ^ B = 0011 0001
~A= 1100 0011
下表列出了位运算符的基本运算,假设整数变量A的值为60和变量B的值为13：
操作符 描述 例子
＆ 如果相对应位都是1，则结果为1，否则为0 （A＆B），得到12，即0000 1100
| 如果相对应位都是0，则结果为0，否则为1 （A | B）得到61，即 0011 1101
^ 如果相对应位值相同，则结果为0，否则为1 （A ^ B）得到49，即 0011 0001
〜 按位取反运算符翻转操作数的每一位，即0变成1，1变成0。 （〜A）得到-61，即1100 0011
<< 按位左移运算符。左操作数按位左移右操作数指定的位数。 A << 2得到240，即 1111 0000
'>>' 按位右移运算符。左操作数按位右移右操作数指定的位数。 A >> 2得到15即 1111
'>>>' 按位右移补零操作符。左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。 A>>>2得到15即0000 1111
image.png
图片引用自：https://yikun.github.io/2015/04/01/JavaHashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
第六代码块（本地方法hashCode）
/**
* 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}.
* <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.
* <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.
* <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.
* </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.)
*
* @return a hash code value for this object.
* @see java.lang.Object#equals(java.lang.Object)
* @see java.lang.System#identityHashCode
*/
public native int hashCode();
未完 还有红黑树的内容未写
网友评论