HashMap源码分析

hashmap

jdk1.7 和1.8中关于对hashmap的实现，有了一些变化，其中很重要的一个变化，就是在解决hash冲突的时候，存储数据结构有所调整。

1.7版本：

主要实现方式： 通过数组+ 链表的方式实现。当hash冲突的时候，使用链表来解决冲突。但是当hash不均匀的时候，可能会导致数据倾斜到某个数组槽位。那么对集合的更新、查找操作最后转变为线性查找，失去了hash查找的特性。

//使用数组式的链表，如果key的hash值一样，则通过list结构来解决冲突，当hash不均匀，可能会导致最后的数据变为线性查找list,性能无法保证
transient entry<k,v>[] table;

    static class entry<k,v> implements map.entry<k,v> {
        final k key;
        v value;
        entry<k,v> next;
        int hash;
        /**其他方法**/
    }

    public v put(k key, v value) {
        if (key == null)
            return putfornullkey(value);
        int hash = hash(key);
        int i = indexfor(hash, table.length);
        //当该数组的hash槽位有数据时，则通过链表的方式追加到链表的结尾
        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;
    }

    void addentry(int hash, k key, v value, int bucketindex) {
        if ((size >= threshold) && (null != table[bucketindex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketindex = indexfor(hash, table.length);
        }

        createentry(hash, key, value, bucketindex);
    }

    void createentry(int hash, k key, v value, int bucketindex) {
        entry<k,v> e = table[bucketindex];
        table[bucketindex] = new entry<>(hash, key, value, e);
        size++;
    }

1.8 版本

在1.8的版本中，同样是通过数组+链表的方式存储结构。但是1.7的entry 被命名为node，并且 当node容量到达8的时候，会将node转换为treenode(红黑树结构)，查找效率大大提高

    /**
     * basic hash bin node, used for most entries.  (see below for
     * treenode subclass, and in linkedhashmap for its entry subclass.)
     */
    static class node<k,v> implements map.entry<k,v> {
        final int hash;
        final k key;
        v value;
        node<k,v> next;
        /**其他方法**/
     }
     
    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;
            //如果已经有该key值，则直接返回该node
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果该node 是treenode，则直接放入到treenode结构中
            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);
                        //如果该槽位的值大于等于7的时候，需要转换成treenode数据结构来存储;treeify_threshold等于8
                        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;
    }
     
    /**
     * 将node数组中，对应hash槽位的node转换为treenode数据结构
     * 
     * replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifybin(node<k,v>[] tab, int hash) {
        int n, index; node<k,v> e;
        if (tab == null || (n = tab.length) < min_treeify_capacity)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            treenode<k,v> hd = null, tl = null;
            do {
                treenode<k,v> p = replacementtreenode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }