侧边栏壁纸
博主头像
buukle博主等级

布壳儿

  • 累计撰写 106 篇文章
  • 累计创建 15 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

jdk(6) - hashMap

administrator
2021-06-18 / 0 评论 / 0 点赞 / 252 阅读 / 6059 字

1 . HashMap数据结构

源码片段:

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
	......
	/**
	* The table, initialized on first use, and resized as
	* necessary. When allocated, length is always a power of two.
	* (We also tolerate length zero in some operations to allow
	* bootstrapping mechanics that are currently not needed.)
	*/
	// table 是一个Node类型的数组,下文是Node的部分源码
	transient Node<K,V>[] table; 
		
	... ...
	// Node 是一个链表数据结构
	static class Node<K,V> implements Map.Entry<K,V> {
			final int hash;
			final K key;
			V value;
			Node<K,V> next;
		...
		}
	}

整体看来,HashMap是一个由数组 + 链表 结合起来构成的复合型数据结构.

2 . api

put()方法及相关部分源码

...
	/**
 	 * put 方法入口
	 */
	public V put(K key, V value) {
        	return putVal(hash(key), key, value, false, true);
    	}
	...
	/**
	 * hash 方法入口
	 */
	static final int hash(Object key) {
        	int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
	...
	/**
     * 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<K,V>[] tab; Node<K,V> p; int n, i;
        // 1. 判断是否空,是则扩容一下 (在这个过程中, 顺便将table的引用赋给了tab,tab在之后会被用到)
		if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
		// 计算被插入元素应该落入索引 i 的值,算法 : 用当前数组的长度和key的hash值做 & 运算;
		// 获取tab[i] 处的元素,判断该元素是否为空
		// 2. tab[i]处的值是空,hash不冲突,那就新建一个元素实例,并将其放在索引 i处 ,(即tab[i])ok了.
		if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 3. tab[i]处的值不是空,hash冲突了
		else {
            Node<K,V> e; K k;
            // 3.1 key与当前位置的老key相等,将老的元素引用赋给e;
			if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
			// 3.2 红黑树的插入处理,如果key值相等,将老的元素引用赋给e;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 3.3 链表的插入处理,,如果key值相等,将老的元素引用赋给e;
			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;
                }
            }
			// 如果老元素e存在,说明key是重复插入,那么根据是否"缺席插入" 处理是否进行新老替代,并将老的元素的value返回
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

由源码可知,进入put(k,v)方法时,首先对key 做了hash ① 运算,然后将hash值连同key,value和一些其他参数调用putVal()方法;
putVal()内部实现大致思路是:
(1)首先判断是否是空的,不是则继续下一步,否则重新扩容hashmap,并将(k,v)存放入table中,返回;
(2)不为空,判断table数组在key的hash值所指向索引处是否有值(是否有hash冲突),有 : 则判断value是否相同,相同则替换并返回;不同则进入下一步.
(3)存在hash冲突,并且值不一样,判断node的类型,如果是TreeNode,则将本(key,value)放入该索引处对应红黑树的末尾并返回;否则将本(key,value)放入该索引链表末尾返回.(此处省略了后续回调的代码)

3 . 线程安全

hashmap由于扩容操作涉及到对多个元素进行操作的程序,且有一定次序性,固在多线程环境时,可能会有风险.

transfer()方法源码 :

......
 	/**
     * Transfers all entries from current table to newTable.
     */
      void transfer(Entry[] newTable, boolean rehash) {
          int newCapacity = newTable.length;
          for (Entry<K,V> e : table) {
              while(null != e) {
                 Entry<K,V> next = e.next;
                 if (rehash) {
                     e.hash = null == e.key ? 0 : hash(e.key);
                 }
                 int i = indexFor(e.hash, newCapacity);
                 e.next = newTable[i];
                 newTable[i] = e;
                 e = next;
             } // while

         }
      }
	......

由源码可知,扩容部分的逻辑大概是 :

新建一个数组-- newTab其容量为老数组的2倍,然后遍历老的数组-- oldTab,将其中的值拷贝进新的数组即可.
再涉及链表部分操作的时候,对县城情况下会引起首位死循环 (无hash冲突链表的情况下无此风险).

简单地讲:
<1> α线程在刚刚获取到当前元素(e)和下一元素(next)的指针时候,cpu将α线程挂起,切换到β线程,
<2> 在β线程做完扩容后,cpu再切回α线程,此时由于jdk1.7在扩容时,链表会与原链表倒叙(采用头插法导致),其指向关系也发生了变化,而α
线程在按照切换之前指针进行扩容后,新链表倒叙,导致α线程将旧的指向关系带进了新的扩容后的链表,最终导致链表成环.

jdk1.8后,此问题没有了,原因是1.8以后hashMap做了部分优化:
<1> 当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能.
<2> 在扩容时候对链表操作时,引入了两个临时指针,采用尾插法,不会引起死循环的问题了.

但是1.8也不能完全避免hashMap多线程操作时丢失数据的情况,在企业应用中,已知的小概率风险一定会重现. 固稳妥起见还是用ConccurrentHashMap吧.


注释部分

① : hash运算

一种散列算法,其内部调用了jdk的native方法,native方法由c++实现,并编译成dll文件,打包进入了jdk环境.算法的目的是将同一类型,值不相同的数据通过计算后增大他们之间的散列距离(通俗的说,就是加他他们之间的缝隙,减少冲突的几率),应用于求取(非严谨要求的)唯一散列值的场景.

在java中,Object类本身提供的hashCode() 方法调用的是native中的方法,但是不同的子类有时候会有不同的重写.例如 String :

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

其采用了 string 串不同索引处的ASC码与 31 * h 阶乘的方式,计算String 类型数据的hashCode值;

0
jdk
  1. qrcode alipay
  2. qrcode weixin

评论区