欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JDK1.8源码中的HashMap

程序员文章站 2022-06-04 19:20:43
...

     这几天工作空闲下来,把部分HashMap源码抄写了一遍,仔细研究了里面一些关键的方法。我将阅读时碰到的问题和答案写在了代码注释中,感觉这样比较直观。如果有想学习HashMap源码的码友,可以参考。

public class MyHashMap<K, V> implements MyMap<K, V> {
        /* ---------------- Constants -------------- */
	// 默认初始容量 (桶的数量,table数组的长度) capacity都是2的幂,如何保证,resize()
	private static final int INIT_CAPACITY = 1 << 4; 
	// 默认初始加载因子。为什么是0.75?理想状态下哈希表的每个箱子中,元素的数量遵守泊松分布,当负载因子为 0.75 时,泊松公式中λ 约等于 0.5,
	// 计算链表中数量为8的概率几乎为0.也就是说用0.75作为加载因子,每个碰撞位置的链表长度超过8个是几乎不可能的。
	private static final float LOAD_FACTOR = 0.75f; 
	// 最大容量,为什么不是2^31-1呢?overflow找到一个回答说,在2^30或者更低的范围来保证安全性,比2^31-1容易的多,没有必要追求极限。
	private static final int MAX_CAPACITY = 1 << 30; 
	// 桶中的链表中节点数量大于等于8,链表可能会转化为红黑树,还需考察MIN_TREEFY_CAPACITY
	private static final int TREEFY_THRESHOLD = 8; 
	// 当节点小于等于6,树退化为链表
	private static final int UNTREEFY_THRESHOLD = 6; 
	// 链表转化为树前,还要判断,只有键值对(注意:不是桶的数量)大于64才会转换。防止哈希表建立初期,多个键值对刚好放入一个链表,导致不必要的转化;
	private static final int MIN_TREEFY_CAPACITY = 64; 
	/*-------------------fileds 字段----------------*/
	// KV数量,(链表,树中的总和)
	transient int size; 
	// map结构修改的次数,例如添加新Node。注意如果是替换原有Node的旧值,modCount是不会改变的。
	transient int modCount;
	// hashMap的size大于该值时 将resize扩容,threshold=capacity*loadFactor(该threshold为设置的阈值装载因子,与下面的当前实际装载因子需要注意区分)
	int threshold;
	// 装载因子 用来衡量 map满的程度,size/capacity,而不是占用的桶的数量/capacity
	float loadFactor; 
	transient Node<K, V>[] table;
	transient Set<Map.Entry<K, V>> entrySet;
/*-------------------static utilities 静态方法----------------*/

	static final int hash(Object key) {
		int h;
		// 为什么不直接使用key的hashCode?。一,防止开发者写的hashcode函数性能不佳,散列不均匀。
                //二,key的hashCode的高位参与运算,当数组容量较小时也能保证hash值的均匀。
		return key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16);
	}

	// 经典之处:该算法为求一个不小于给定值的最小2^次幂
	static int tableSizeFor(int initialCapacity) {
		int n = initialCapacity - 1;// 防止initialCapacity本身就是2的x次幂,那么经过以下算法,将返回2的x+1次幂;
		n |= n >>> 1;// >>>为无符号右移,左边空缺全部补0。经过这一步骤,找出了二进制状态,最高位为1的位,并且最高位和次高位都变为1,结果中前2位变为了1(如果最高位所在位数大于等于2)
		n |= n >>> 2;// 经过这一步骤,最高2位和次高2位都变为1,结果中前4位变为了1(如果最高位所在位数大于等于4)
		n |= n >>> 4;// 经过这一步骤,最高4位和次高4位都变为1,结果中前8位变为了1(如果最高位所在位数大于等于8)
		n |= n >>> 8;// 经过这一步骤,最高8位和次高8位都变为1,结果中前16位变为了1(如果最高位所在位数大于等于16)
		n |= n >>> 16;// 经过这一步骤,最高16位和次高16位都变为1,结果中前32位变为了1(如果最高位所在位数大于等于32)
		return (n < 0) ? 1 : (n >= MAX_CAPACITY ? MAX_CAPACITY : n + 1);// 二进制全部变为1后,再进1,即可得到不小于该数的最小2^次幂
	}
/*-------------------public operations----------------*/

	public MyHashMap() {
		super();
		this.loadFactor = LOAD_FACTOR;
	}

	public MyHashMap(int initialCapacity) {
		this(initialCapacity, LOAD_FACTOR);
	}

	public MyHashMap(int initialCapacity, float loadFactor) {
		if (initialCapacity < 0)
			throw new RuntimeException("容量不能为负");
		if (initialCapacity > MAX_CAPACITY)
			initialCapacity = MAX_CAPACITY;
		this.loadFactor = loadFactor;
		this.threshold = tableSizeFor(initialCapacity);
		// 很奇怪 为什么是threhold? this.threshold = tableSizeFor(initialCapacity) *loadFactor;
		//貌似这样才符合意思。其实构造函数并未对table初始化,初始化是在put函数,再到resize函数中进行的,并且在resize中重新计算了threhold值
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public int size() {
		return size;
	}

	public V put(K key, V value) {
		return putVal(hash(key), key, value, false, true);
	}

putVal():

/*
	 * put()思路:
	 * 1.table是否null,是否需要扩容
	 * 2.根据hash计算数组tab索引i,如果tab[i]==null,直接新建节点插入该槽位,转到步骤6,否则到步骤3
	 * 3.tab[i]的首个元素的key是否与传入key相同,相同覆盖value,转到步骤6,否则到步骤4
	 * 4.判断tab[i]是否是treeNode,是,插入树中,转到步骤6,否则到步骤5
	 * 5.遍历tab[i]时,如果链表的next为空,进行链表的插入操作,插入后,判断长度是否大于8,是则转化为红黑树。如果遍历时发现key值匹配,
	 * 覆盖value 6.插入成功后,判断size是否大于threshold,是否需要扩容
	 */
	private 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) {
			n = (tab = resize()).length;// 注意此处n必须重新赋值,不能只是tab赋值,因为if条件中,有可能只走到前半部分。
		}
		// 巧妙之处:计算槽位的时候本来应该为hash%n,但是取模运算效率低下。总槽位n为2的x次幂时,hash%n可以用hash&(n-1)替代,
		//结果一样,效率却可以提升5~8倍。
		if ((p = tab[(i = hash & (n - 1))]) == null) {
			tab[i] = new Node<K, V>(hash, key, value, null);
		} else {
			Node<K, V> e;
			K k;
			// 该条件就是判断tab[i]的key与传入的key是否相同。用短路与先判断hash值,效率比直接判断key相等更高
			if (p.hash == hash && ((p.key == key || (key != null && key.equals(p.key))))) {
				e = p;// 为什么不直接p.value=value;
			} else if (p instanceof TreeNode) {
				e = putTreeVal(this, tab, hash, key, value);// 此方法就先不研究了
			
                        } else {
				for (int binCount = 0;; ++binCount) {
					if ((e = p.next) == null) {
						p.next = new Node<K, V>(hash, key, value, null);//e还是null
						if (binCount >= TREEFY_THRESHOLD - 1) {
							// treefyBin(tab,hash);暂不研究
							break;
						}
					}
					if (e.hash == hash && (((k=e.key) == key || (key != null && key.equals(k))))) {
						break;
					}
					p = e;
				}
			}
			//e不为空 说明map中有key相同的节点
			if (e != null) {
				V oldValue=e.value;
				e.value=value;
				return oldValue;//如果是覆盖值的操作,直接return,不走到下面,modCount++了,也即只会统计结构改变了的次数
			}
		}
		++modCount;
		if(++size>threshold)
			resize();
		return null;
	}

resize():

        /*读resize方法之前先明白,由于n(capacity)都是2的x次幂,扩容后,重新计算的节点的索引位置i要么还是i,
	 * 要么是i+oldCap。因为2n-1(32-1:10101)比n-1(16-1:00101)多一个最高位的1,这个1就是
	 * oldCap的值,那么重新计算索引hash&(2n-1)的时候,只需要看hash & oldCap为0或1即可,
	 * 为0新位置还是i,为1,则新位置为i+oldCap  */
	private 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>=MAX_CAPACITY) {
				threshold=Integer.MAX_VALUE;
				return oldTab;
			} else if((newCap=oldCap<<1)<MAX_CAPACITY&&oldCap>=INIT_CAPACITY) {//新的数组和新的阈值都扩到2倍
				newThr = oldThr << 1;
			}
		} else if(oldThr>0) {//分支二:oldCap==0,oldThr>0;为调用有参数的构造函数时所执行
			newCap=oldThr;//通过tableSizeFor得到的2的n次幂在构造函数中赋值给了threshold,在这里赋值到了capacity,所以下面要重新计算阈值
		} else {//分支三:oldCap==0,oldThr==0;为调用无参数的构造函数时所执行
			newCap=INIT_CAPACITY;
			newThr=(int) (newCap*loadFactor);
		}
		if(newThr==0) {//只有分支一中的情况二,扩容之后newThr==0
			float ft=newCap*loadFactor;
			newThr=(newCap<MAX_CAPACITY && ft<(float)MAX_CAPACITY)?(int)ft:Integer.MAX_VALUE;
		}
		threshold=newThr;
                //创建新的数组
		@SuppressWarnings("unchecked")
		Node<K,V>[] newTab=(Node<K,V>[])new Node[newCap];
		table=newTab;
		if(oldTab!=null) {//即oldCap>0;为分支一扩容情况,把旧数组中的每个node复制到新数组
			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) {//红黑树
						//tree..
					
                                        } else {//链表
						//分别指向新数组中,e.hash&(newCap-1)等于原位置的尾节点和头节点
						Node<K,V> loTail=null,loHead=null;
						//分别指向新数组中,e.hash&(newCap-1)等于原位置+oldCap的尾节点和头节点
						Node<K,V> hiTail=null,hiHead=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;//将尾节点指向新的节点
								//原位置+oldCap
							} 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;
						}
						//将重新布置到原位置+oldCap位置的链表的头节点放到数组槽位中
						if(hiTail!=null) {
							hiTail.next=null;
							newTab[j+oldCap]=hiHead;
						}
					}
				}
			}
		}
		return newTab;
	}