HashMap 的一些整理： (JDK 1.7)
- 基于哈希表的Map接口的非同步实现，定义了键映射到值的规则
- 此实现提供所有可选的映射操作，并允许使用null值和null键
- 此实现假定哈希函数将元素适当分布在各桶之间，为读取操作提供稳定性能
- 迭代时间与实例容量(桶的数量)及其大小(键-值映射关系数)成正比
■ 类定义
public class HashMap<K,V>
extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
- 继承 AbstractMap抽象类，实现了Map接口
- 实现 Cloneable接口
- 实现 java.io.Serializable 接口，支持序列化
HashMap - “链表散列” (数组+单向链表)， 数组每一项都是一条链的数据结构 【冲突解决方案-封闭寻址方法】
■ 重要的全局变量
//The default initial capacity - MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 16;
//The maximum capacity - MUST be a power of two <= 1<<30.
static final int MAXIMUM_CAPACITY = 1 << 30;
//The load factor used when none specified in constructor.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//The table, resized as necessary. Length MUST Always be a power of two.
transient Entry<K,V>[] table;
//The number of key-value mappings contained in this map.
transient int size;
//The next size value at which to resize (capacity * load factor).
int threshold;
//The load factor for the hash table.
final float loadFactor;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
■ 构造器
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);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//阈值为容量*负载因子和最大容量+1之间的最小值 以此值作为容量翻倍的依据(不能超过最大容量)
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化一个2次幂的Entry类型数组 一个桶对应一个Entry对象
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
- Entry
/**
* 静态类 默认实现内部Entry接口 (接口中可定义内部接口-Map.Entry接口为Map的内部接口)
* PS:JDK8中引入default，作用为在接口中定义默认方法实现
*/
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//key具有引用不可变特性
V value;
Entry<K,V> next;//next指向下一个：单向链表，头插入
final int hash;
……
}
■ HashMap 重要方法
- put(k, v)
/**
* 存放键值对
* 允许存放null的key和null的value
* @return key不存在返回null，否则返回旧值
*/
public V put(K key, V value) {
/**
* 1.针对key为null的处理有两种方式：
* 1.1从tab[0]开始向后遍历，若存在key为null的entry，则覆盖其的value
* 1.2遍历完成但仍不存在key为null的entry，则新增key为null的entry
* 准则：一个HashMap只允许有一个key为null的键值对
* 注意：由于hash(null) = 0，因此key=null的键值对永远在tab[0]
*/
if (key == null)
return putForNullKey(value);
/**
* 根据key的hashCode并结合hash()算法计算出新的hash值
* 目的是为了增强hash混淆 -> 因为key.hashCode()很可能不太靠谱
* 而HashMap是极度依赖hash来实现元素离散的，通俗来说就是
* 尽可能的让键值对可以分到不同的桶中以便快速索引
*/
int hash = hash(key);
//2.根据hash计算该元素所在桶的位置 -> 即数组下标索引
int i = indexFor(hash, table.length);
/**
* 3.遍历链表，若该key存在则更新value，否则新增entry
* 判断该key存在的依据有两个：
* 1.key的hash一致
* 2.key一致(引用一致或字符串一致)
* put操作遵循：有则更新，无则新增
*/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//使用临时变量k临时存储遍历时的e.key -> 主要是为了代码复用
Object k;
//hash一致 && (key引用相同 或 key字符串比较相同)
if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
//值更新
V oldValue = e.value;
e.value = value;
//钩子方法
e.recordAccess(this);
//返回旧值
return oldValue;
}
}
//put操作属于结构变更操作
modCount++;
//无则新增
addEntry(hash, key, value, i);
//该key不存在就返回null -> 即新增返回null
return null;
}
- hash()
//JDK1.7
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//异或就是两个数的二进制形式，按位对比，相同取0，不同取一
//此算法加入了高位计算，防止低位不变，高位变化时，造成的 hash 冲突
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//JDK1.8 扰动函数 -> 散列值优化函数
static final int hash(Object key) {
int h;
//把一个数右移16位即丢弃低16为，就是任何小于2^16的数，右移16后结果都为0
//2的16次方再右移刚好就是1 同时int最大值为32位
//任何一个数，与0按位异或的结果都是这个数本身
//为indexFor做准备
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- indexFor()
/**
* Int范围(2^32)从-2147483648到2147483648，加起来大概40亿空间，内存不能直接读取
* 用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标
* @Param h 根据hash方法得到h
* @Param length 一定是2次幂
*/
static int indexFor(int h, int length) {
//2次幂-1 返回的结果的二进制为永远是都是1 比如 15 -> 1111 (16 -> 10000)
//与运算 只有 1 & 1 = 1 正好相当于一个“低位掩码” (二进制表示)
//如果length-1中某一位为0，则不论h中对应位的数字为几，对应位结果都是0，这样就让两个h取到同一个结果，hash冲突
//同时这个操作可以保证索引不会大于数组的大小(见开头的描述)
return h & (length-1);
}
- addEntry()
//该方法为包访问 package java.util(本包私有性高于子类)
void addEntry(int hash, K key, V value, int bucketIndex) {
//当前容量超过阈值 && 当前坐标数组非空
//有个优雅的设计在于，若bucketIndex处没有Entry对象，那么新添加的entry对象指向null，从而就不会有链了
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//容量扩容一倍
hash = (null != key) ? hash(key) : 0;//hash重新计算
bucketIndex = indexFor(hash, table.length);//index重新计算
}
createEntry(hash, key, value, bucketIndex);//新增Entry元素到数组的制定下标位置
}
//该方法为包访问 package java.util
void createEntry(int hash, K key, V value, int bucketIndex) {
// 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = table[bucketIndex];
// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
// 形成链表，新加入的放入链表头部，最先加入的放入尾部
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
■ 关于indexFor 和 hash方法的进一步解读
- hashCode返回的-2147483648到2147483648的int值，加起来大概40亿的映射空间。只要哈希函数映射比较均匀松散，一般很难出现碰撞key.hashCode()
- 但问题是40亿长度数组，内存放不下，该散列值不能直接拿来用。用之前必须先对数组长度取模运算，得到的余数才能来访问数组下标indexFor()
- 长度取2的整次幂，而length-1时正好相当于一个低位掩码。与操作的结果就是散列的高位全部归零，只保留低位值，用作下标访问
10100101 11000100 00100101
& 00000000 00000000 00001111
00000000 00000000 00000101 //高位全部归零，只保留末四位 - 但问题是，无论散列值再松散，但只取最后几位，碰撞也很严重。更要命的是如果散列本身做的不好，分布上成等差数列，就会出现规律性重复，这时候就需要扰动函数进行打散优化.
扰动函数生效：
扰动函数
右位移16位(32位一半)，让高半区和低半区做异或，目的是混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位包含高位的部分特征，这样高位的信息也变相保留下来- 当长度非2次幂(最后一位永远是0)，进行与运算(只有都为1得1，否则为0)，会造成最后一位永远是0，那最后一位就无法使用，导致(1)空间的巨大浪费。同时可使用的位置比原数组长度小很多，(2)进一步增加了碰撞的几率
■ Fail-Fast 机制
- 当使用迭代器的过程中有其他线程修改了map，将抛出ConcurrentModificationException
transient int modCount;//修改计数 put、remove或clear时mount++ clear时清空
HashIterator() {
expectedModCount = modCount;
if (size > 0) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
final Entry<K,V> nextEntry() {
//期望变更数量不匹配
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- remove()
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
* Removes and returns the entry associated with the specified key
* in the HashMap. Returns null if the HashMap contains no mapping
* for this key.
*/
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];//用于记录该key的前一个元素(默认先从队首开始)
Entry<K,V> e = prev;//从队首开始往队尾遍历
//遍历key所在链表
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;//remove属于结构性改造，modCount计数+1
size--;//当前Map的有效元素数量-1
if (prev == e)
table[i] = next;//若当前key正好位于队首，则队首指向next
else
prev.next = next;//若当前key不位于队首，则该key之前的元素的next指向该key的下一个元素
e.recordRemoval(this);//LinkedHashMap专用方法
return e;
}
//继续往队尾找
prev = e;//指向当前循环元素的上一个元素
e = next;//指向下一次循环元素
}
return e;
}
■ HashMap 迭代几种方式
package utilsFrameworks; import java.util.HashMap;
import java.util.Map;
import java.util.Random; /**
* Created by romanDev on 2017/7/30.
* @details Map的几种迭代方式
* @note 【2017 java's day】
*/
public class IteratorMap {
public static void main(String[] args) {
Random rand = new Random(47);
Map<Integer, Object> map = new HashMap<Integer, Object>();
for(int i=0;i<100;i++) {
int r = rand.nextInt(20);
Integer freq = (Integer) map.get(r);
map.put(r, freq == null? 1: freq+1); //三目
}
System.out.println(map); //遍历方法一
/*for (Integer key : map.keySet()) {
System.out.println("key="+ key + " and value=" + map.get(key));
}*/ //遍历方法二
/*Iterator<Map.Entry<Integer,Object>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, Object> entry = it.next();
System.out.println("key=" + entry.getKey() + " and value=" + entry.getValue());
}*/ //遍历方法三 (推荐)
for (Map.Entry<Integer,Object> entry : map.entrySet()) {
System.out.println("key=" + entry.getKey() + ", value=" + entry.getValue());
}
} }
PS：感谢好基友Kira 的友情帮助，部分文章内容转载于 【集合番@HashMap一文通(1.7版) 由 黄志鹏kira】