Java Jdk1.8 HashMap源码阅读笔记
（一）
一、结构
public class HashMap
1、抽象类AbstractMap
public abstract class AbstractMap
一、结构
public class HashMap
1、抽象类AbstractMap
public abstract class AbstractMap
2、序列化接口：Serializable
该接口没有什么好说的，但通过该接口，就解释了为什么HashMap总一些字段是用transient来修饰。
一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。
二、阅读JDK中类注释
1、HashMap是无序的
如果希望保持元素的输入顺序应该使用LinkedHashMap
2、除了非同步和允许使用null之外，HashMap与Hashtable基本一致。
此处的非同步指的是多线程访问，并至少一个线程修改HashMap结构。结构修改包括任何新增、删除映射，但仅仅修改HashMap中已存在项值得操作不属于结构修改。
3、初始容量与加载因子是影响HashMap的两个重要因素。
public HashMap(int initialCapacity, float loadFactor)
初始容量默认值：
/**
* The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
加载因子默认值： /**
* The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
容量是HashMap在创建时“桶”的数量，而初始容量是哈希表在创建时分配的空间大小。加载因子是哈希表在其容量自动增加时能达到多满的衡量尺度（比如默认为0.75，即桶中数据达到3/4就不能再放数据了）。
默认0.75这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。 。
4、存储形式
（树形存储在treemap中再探讨） 链表形式存储？树形结构？
* This map usually acts as a binned (bucketed) hash table, but * when bins get too large, they are transformed into bins of * TreeNodes, each structured similarly to those in
* java.util.TreeMap. Most methods try to use normal bins, but * relay to TreeNode methods when applicable (simply by checking * instanceof a node).
三、源码阅读
1、添加元素 /**
* 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.) */
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 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node
//hashmap第一次添加元素，调用resize()方法初始化table if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
//通过与运算判断tab[hash]位置是否有值
//从newNode这里可以看出，hashmap中key value是以Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); else {
法
Node
}
Node
((k = p.key) == key || (key != null && key.equals(k)))) e = p;
else if (p instanceof TreeNode)//如果p类型为TreeNode，调用树的添加元素方 e = ((TreeNode
//不是TreeNode,即为链表,遍历链表，查找给定关键字 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) {
//到达链表的尾端也没有找到key值相同的节点，则生成一个新的 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; } }
// e不为空，即map中存在要添加的关键字 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;
}s Map
小注： 1、回调
afterNodeAccess(e);
afterNodeInsertion(evict);
是为LinkedHashMap回调准备的，相当于C#中的委托。 2、计算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 diswww.shanxiwang.nettributed (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. */
static final int hash(Object key) { int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
‘>>>’：无符号右移，忽略符号位，空位都以0补齐
value >>> num – num 指定要移位值value 移动的位数。
即按二进制形式把所有的数字向右移动对应位数，低位移出（舍弃），高位的空位补零。对于正数来说和带符号右移相同，对于负数来说不同。
^异或：两个操作数的位中，相同则结果为0，不同则结果为1。