HashMap 源码解析(一)

  1. 云栖社区>
  2. 博客>
  3. 正文

HashMap 源码解析(一)

达拉崩巴斑得贝迪卜多比鲁翁 2019-07-02 19:51:04 浏览312
展开阅读全文

HashMap对于每次java开发者来说用的都很多,作为一个coder为了提升自己的代码能力,花了几天时间来研究了hashmap 的源码

1 首先了解一下hashmap 的数据结构

image(图片来源于网络,侵权请通知删除)

2代码中具体的格式为以下代码,存储了每个链表的头节点的数组

Node<K,V>[] table

一个Node的数组, 然后看下Node的数据结构

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

实现的Map.Entry的接口,用泛型定义了 key和value的属性,对于hashMap来说,这就是内部数据的存储方式,
对hash属性加上了final 属性 仅在初始化时赋值,同时可以看到next属性,Node即使上图中的链表节点

public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }

同时用final修饰了equals方法,分析下具体逻辑
1 判断两个对象引用是否相同,如果是,直接返回
2 判断该对象是否实现了基础接口Map.entry 判断两个对象的key和value的引用是不是都相同

3 数据put

HashMap的put操作是有返回值,在业务中可以根据返回值简化一些代码,具体返回值下面讨论
1 获取key的hashcode

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

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

可以看到 取到hashcode后 和自己本身的高16位做了亦或操作,是为了使hashcode的生成更加散列(未理解)

接下来是具体的插入流程

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {

        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判断hashmap 的table 是否已经进行了初始化,并根据new 时的参数,进行table的初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            //table 初始化,并获取node数组的长度,resize函数也承担了hashmap扩容的功能
            n = (tab = resize()).length;
            //将新生成的hashcode 和table的长度n-1做&操作,获取该节点在数据中的下标,如果数组中该位置没有数据,则根据传入的值生成新node节点
        if ((p = tab[i = (n - 1) & hash]) == null) 
            tab[i] = newNode(hash, key, value, null);
        else {//如果该位置已经存在其他节点(上面if操作已经对p进行了赋值,为tab[(n-1)&hash])
            Node<K,V> e; K k;
            //判断已经存在的节点数据和新传入的节点key和hash值是否相同
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)//jdk8红黑树特性,暂不了解
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {// 已存在节点的key和新增的key不相同,发生hash冲突
                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  定位到put数据位置,进行value赋值操作
                V oldValue = e.value; //获取key 对应节点的原来数据
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//对节点node重新赋值
                afterNodeAccess(e);
                return oldValue; //返回节点原数据
            }
        }
        //没有发生hash冲突,数组的某个位置被占用
        ++modCount;//The number of times this HashMap has been structurally modified,  hashMap 结构修改次数 
        if (++size > threshold)//~~数组已经被占用数量~~ 重新阅读源码后发现是hashMap数据量的大小,
         //不是被占用数组的大小,自定义类重写hashCode方法后发现,hashMap中的table数组即使只占用了少量几个位置,
         //在size到达临界值后也会进行扩容,即使数组大部分空间被浪得掉,因此hashCode()应该尽量减少hash冲突,减少内存浪费
            resize();
        afterNodeInsertion(evict);.//LinkedHashMap 方法
        return null;
    }

3 hashmap取数据
首先获取key的hashcode

public V get(Object key) {
        Node<K,V> 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) {// 判断hashmap是否已经完成初始化,且根据hashcode和数组长度产生的位置值判断数组中            
                                                                   的该位置是否存在数据
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))//判断第一个几点key和hashcode是否相同
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);.//jdk8红黑树
                do {//循环链表查找key和hashcode都符合的节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

4hashmap 数组初始化和扩容
在hashMap中 新增一调数据,如果已经占用的位置的数量size/length>DEFAULT_LOAD_FACTOR(0.75) 则会进行数组大小扩容, node[n] 数组的大小默认为16,当已经占用的数量>12时,数组大小会翻倍,所以在使用hashMap时,如果知道key的数量,可以在HashMap初始化时指定数组大小,减少resize()带来的时间消耗 new HashMap(int n),同时也可以指定扩容因子loadFactor,自行决定扩容时机,

n不是2的次方时,会自动设置为>n的最小2次方值

 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);
    }
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//判断是初始化还是扩容,获取node数组长度
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {//判断为扩容
            if (oldCap >= MAXIMUM_CAPACITY) {//判断数组大小是不是超限
                threshold = Integer.MAX_VALUE;
                return oldTab; //修改数组最大值为Integer的最大值,返回原数组
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }//判断数组长度*2后是否超过最大限定大小
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults 
                //hashmap 数组大小初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {//  J  如果是扩容,将老数组的数据重新填充到新的node数组中
                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)//jdk8 tree
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = 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;
                            }
                            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;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab; 
    }
     

网友评论

登录后评论
0/500
评论
达拉崩巴斑得贝迪卜多比鲁翁
+ 关注