建设局网站港府名都,常州 wordpress,网站建设.软件开发,深圳网站制作公司建设HashMap 源码阅读
HashMap 简介
HashMap 主要用来存放键值对#xff0c;实现了基于哈希表的 Map 接口#xff0c;非线程安全。
HashMap 可以存放 null 的 key 和 null 值#xff0c;但 null 作为 key 只能有一个#xff0c;null 作为 value 可以有多个。
HashMap 有两个…HashMap 源码阅读
HashMap 简介
HashMap 主要用来存放键值对实现了基于哈希表的 Map 接口非线程安全。
HashMap 可以存放 null 的 key 和 null 值但 null 作为 key 只能有一个null 作为 value 可以有多个。
HashMap 有两个版本
JDK8之前HashMap 的底层数据结构为数组 链表数组是 HashMap 的主体链表则是为解决哈希冲突而存在的。JDK8之后HashMap 的底层数据结构为数组 链表/红黑树当链表长度大于阈值默认是8并且数组容量大于64时将链表转换为红黑树以减少搜索时间。
HashMap 的默认大小为16之后每次扩充容量都变为原来的2倍并且 HashMap 总是以2的幂作为哈希表的大小
构造函数
// 默认构造函数。public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted}// 包含另一个“Map”的构造函数public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);//下面会分析到这个方法}// 指定“容量大小”的构造函数public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 指定“容量大小”和“负载因子”的构造函数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);}其中loadFactor被称为负载因子其默认大小为0.75f static final float DEFAULT_LOAD_FACTOR 0.75f; 关于负载因子
在分析构造函数时我们提到了负载因子的默认大小为0.75所以为什么为0.75而不是1或者0.5呢
首先要知道 loadFactor 的作用
loadFactor 负载因子用来控制数组存放数据的疏密程度 负载因子越大越趋近于1那么数组存放的数据也就越多链表长度就会增加会导致查找开销大效率低。 负载因子越小越趋近于0那么数组存放的数据也就越少存放数据很分散导致数组利用率低会频繁扩容非常消耗性能。 loadFactor 与 threshold threshold capacity * loadFactor当 Sizethreshold的时候那么就要考虑对数组的扩增了也就是说这个的意思就是 衡量数组是否需要扩增的一个标准。 作为一般规则默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销但会增加查找成本反映在 HashMap 类的大多数操作中包括 get 和 put。在设置其初始容量时应考虑映射中的预期条目数及其负载因子以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子则不会发生重新哈希操作。
方法解析
putMapEntries 方法
final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {int s m.size();if (s 0) {// 判断table是否已经初始化if (table null) { // pre-size// 未初始化s为m的实际元素个数float ft ((float)s / loadFactor) 1.0F;int t ((ft (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);// 计算得到的t大于阈值则初始化阈值if (t threshold)threshold tableSizeFor(t);}// 已初始化并且m元素个数大于阈值进行扩容处理else if (s threshold)resize();// 将m中的所有元素添加至HashMap中for (Map.Entry? extends K, ? extends V e : m.entrySet()) {K key e.getKey();V value e.getValue();putVal(hash(key), key, value, false, evict);}}
}put() 方法
HashMap 对外只提供put() 方法用于添加元素put() 方法内部调用的是putVal() 方法
putVal() 方法的流程如下
如果定位到的数组位置没有元素就直接插入如果定位到的数组位置有元素就和要插入的 key 作比较如果 key 相同就直接覆盖如果 key 不同就判断p是否为一个树节点如果是就调用e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value)将元素添加进入如果是链表节点则遍历到链表尾部插入。 public V put(K key, V value) {//hash(key)获取key的hash值当key为null时哈希值为0//keyvalue要存储的键值对//第四个参数为onlyIfAbsent默认是false如果是true表示如果不存在改key就进行put操作return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;// 第一次put操作table未初始化或者长度为0进行扩容//第一次resize()扩容操作后数组容量会初始化为16if ((tab table) null || (n tab.length) 0)n (tab resize()).length; // (n - 1) hash 确定元素存放在哪个桶中// 桶为空新生成结点放入桶中(此时这个结点是放在数组中)if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);// 桶中已经存在元素else {// e为辅助节点用来记录key值与新插入节点相同的旧节点NodeK,V e; K k;// 比较桶中第一个元素(数组中的结点)的hash值相等key相等if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))// 将第一个元素赋值给e用e来记录e p;// hash值相等key不相等// 为红黑树结点else if (p instanceof TreeNode)// 放入树中e ((TreeNodeK,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);// 结点数量达到阈值(默认为 8 )执行 treeifyBin 方法// 这个方法会根据 HashMap 数组来决定是否转换为红黑树。// 只有当数组长度大于或者等于 64 的情况下才会执行转换红黑树操作以减少搜索时间。否则就是只是对数组扩容。if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);// 跳出循环break;}// 判断链表中结点的key值与插入的元素的key值是否相等if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))// 相等跳出循环break;// 用于遍历桶中的链表与前面的e p.next组合可以遍历链表p e;}}// 表示在桶中找到key值、hash值与插入元素相等的结点if (e ! null) {// 记录e的valueV oldValue e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue null)//用新值替换旧值e.value value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 结构性修改modCount;// 实际大小大于阈值则扩容if (size threshold)resize();// 插入后回调afterNodeInsertion(evict);return null;
}
JDK7的 put( ) 方法 如果定位到的数组位置没有元素 就直接插入。 如果定位到的数组位置有元素遍历以这个元素为头结点的链表依次和插入的 key 比较如果 key 相同就直接覆盖不同就采用头插法插入元素。
get( ) 方法
public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,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) {// 在树中getif (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);// 在链表中getdo {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;
}
resize( ) 方法
进行扩容会伴随着一次重新 hash 分配并且会遍历 hash 表中所有的元素是非常耗时的。在编写程序中要尽量避免 resize。
final NodeK,V[] resize() {//旧数组NodeK,V[] oldTab table;//旧数组容量int oldCap (oldTab null) ? 0 : oldTab.length;//旧数组阈值int oldThr threshold;//新数组的容量和阈值int newCap, newThr 0;if (oldCap 0) {// 超过最大值就不再扩充了就只好随你碰撞去吧// MAXIMUM_CAPACITY 130if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}// 没超过最大值容量和阈值都扩充为原来的2倍else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}//oldCap 0 未初始化//当使用new HashMap(int initalCapacity)时else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { //当使用new HashMap()时// signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 计算新的resize上限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})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;//如果为初始化数组那么到这里已经结束if (oldTab ! null) {// 把每个bucket都移动到新的buckets中for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;//当该数组下标j位置只有一个元素时直接迁移这个元素if (e.next null)//计算此元素在新数组的位置newTab[e.hash (newCap - 1)] e;//如果e为红黑树节点else if (e instanceof TreeNode)//红黑树节点迁移((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { //e为链表节点NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;// 原索引// 不需要换桶if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}// 需要换桶// 新桶位置 旧桶位置oldCapelse {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);// 原索引放到bucket里if (loTail ! null) {loTail.next null;newTab[j] loHead;}// 原索引oldCap放到bucket里if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
}
