java中的hashmap

JAVA中常用的map就是hashMap。只要想到键值对,一定是hashmap没有第二选择。很多程序员不求甚解的开始使用这个hashmap,但是你对这个类有多少了解呢?今天就谈谈hashMap的类结构吧。其实HashMap还是相当的简单的,首先看一下,HashMap在new的时候干了什么:

   public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

先不急着解释前几个参数,数一下table吧。这个table是个什么东西呢。我们看到了Entry。稍微有点开发经验的java程序员都知道这个是一个内部类。这里就不再拷贝出来它的源代码了。想研究的人自己去看吧。这个其实是一个key-value结构的链表元素。不卖关子了,其实hashmap就是数组和链表实现的,具体可以参考这样一个图: 想要更加深入的了解hashmap的结构当然仅仅看构造函数是不够的,更多细节在put这个函数中:

public V put(K key, V value) {  
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

首先映入眼帘的是对key为null的处理——大家都知道这个是和hashtable的一个区别就是支持key为null。然后就是会计算出当前key的hash值,至于为啥是那个看不懂的计算公式,只能依靠你的数学只是了。之后呢,会根据hashcode计算出当前在数组的位置,具体算法就是跟这个table的当前取模余数。之后这个for循环处理key完全相同(即hashcode和值都相同)的时候将老的值替换掉,然后返回老的值。紧接着总数加1然后新增节点。下面看一下addEntitry方法:

  void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
   table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

这个方法中包含了两个处理逻辑一个是将新的节点放到table中,然后在新建Entitry的时候处理冲突,将冲突的老的值放在next上面。之后判断size增加后有没有超过阀值,如果超过了更具table的2倍进行扩充。当然之所以说hashmap不是线程安全的,也就是在这个时候容易出问题产生一个闭环,造成cpu的使用率直接到100%,这个是后话,在下一篇中再做描述。 说完了put方法,当然还有一个get方法,下面看一下get方法的代码:

   public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

大致过程是先算出hash值,然后算出在table的索引值,之后遍历这个table找到hashcode和key相等的value值返回,应该很容易就能看懂了。 由于只看了jdk6 的代码,就在博客中说是java的hashmap差点就铸成大错了。原来jdk8 对原来的hashmap做了修改,put方法做了改进,具体先看代码:

 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
  final 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;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,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);
                        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;
                }
            }
            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;
    }

看完代码就会发现,如今的hashmap已经比之前jdk 6和jdk7的复杂了好多。当然没有碰撞的时候还是一样的算法,发生了碰撞的话就会又不一样的判断了。如果碰撞的linklist大于TREEIFY_THRESHOLD-1(为7)的值的时候就会把原来的linklist变成bintree(调用treeifyBin方法)。这样在调用get的方法的时候,就会由O(n)变成O(logn)(具体分析的链接),可以有效的避免了恶意程序的hash碰撞攻击了。这里也给出get方法的具体实现过程(没有特别具体只是给出相关代码,希望更详细的可以上官网下载源代码阅读):

public V get(Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

 final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,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) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

    final TreeNode<K,V> getTreeNode(int h, Object k) {
        return ((parent != null) ? root() : this).find(h, k, null);
    }

     final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        TreeNode<K,V> p = this;
        do {
            int ph, dir; K pk;
            TreeNode<K,V> pl = p.left, pr = p.right, q;
            if ((ph = p.hash) > h)
                p = pl;
            else if (ph < h)
                p = pr;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            else if (pl == null)
                p = pr;
            else if (pr == null)
                p = pl;
            else if ((kc != null ||
                      (kc = comparableClassFor(k)) != null) &&
                     (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
            else
                p = pl;
        } while (p != null);
        return null;
    }

尤鹏飞

继续阅读此作者的更多文章