HashMap的个别方法

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16 默认初始容量 16

static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 2的30次方

static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认负载因子 0.75

static final int TREEIFY_THRESHOLD = 8; //当一条链表中的元素个数大于8时，由链表转为红黑树

static final int UNTREEIFY_THRESHOLD = 6; //当扩容时，树形结构中元素个数小于这个值就会把树形结构还原为链表结构

static final int MIN_TREEIFY_CAPACITY = 64;//当哈希表中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化

transient Node<k,v>[] table; //Node数组，存储键值对，当发生散列冲突时，该下标中的每一个元素开始时以链表形式存储，后转为红黑树

 扩容的方法

 final Node<K,V>[] resize() {

     Node<K,V>[] oldTab = table;

     int oldCap = (oldTab == null) ? 0 : oldTab.length; //取得table的长度

     int oldThr = threshold; //取得扩容的阈值

     int newCap, newThr = 0;

     if (oldCap > 0) { //如果table长度大于0

         if (oldCap >= MAXIMUM_CAPACITY) { //判断是否大于最大容量

             threshold = Integer.MAX_VALUE;  //把 2的31次方赋值给阈值 ，也就是说这辈子不能扩容了

             return oldTab; //直接返回

         }

         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                  oldCap >= DEFAULT_INITIAL_CAPACITY)

                  //如果 table 的长度乘以2 小于最大容量 并且  table的长度大于等于默认初始容量

             newThr = oldThr << 1; // double threshold

     }

     else if (oldThr > 0) // initial capacity was placed in threshold

         newCap = oldThr;  //如果原来的threshold大于0 ， 则把此当作新的容量

     else {               // zero initial threshold signifies using defaults

         newCap = DEFAULT_INITIAL_CAPACITY; //如果threshold也是0 ，则给默认的容量 16

         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

         //新的阈值为 默认的负载因子*默认的初始容量

     }

     if (newThr == 0) {

         float ft = (float)newCap * loadFactor;//第二步else if并没有计算 新的阈值

         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

                   (int)ft : Integer.MAX_VALUE);

                   //如果 新的容量小于最大容量 并且 新的阈值小于最大容量 ？新的阈值：2的31次方

     }

     threshold = newThr;

     @SuppressWarnings({"rawtypes","unchecked"})

         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

     table = newTab; //扩容完毕

     if (oldTab != null) {  //把原来table中的值迁移到新的table中

         for (int j = 0; j < oldCap; ++j) {

             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)

                     ((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;//返回

 }

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) //如果table为null 或者 长度为0

        n = (tab = resize()).length; //  调用resize生成数组table, 并令tab指向数组table

    if ((p = tab[i = (n - 1) & hash]) == null) //通过表的长度与hash进行位运算

                        ，取得一个合适下标，如果该下标当前为null，创建新的节点

        tab[i] = newNode(hash, key, value, null);

    else { //如果散列冲突

        Node<K,V> e; K k;

        if (p.hash == hash &&  //如果该节点上这一对的 hash 与当前要放入的这一对 hash相同，且key相同

            ((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节点的下一个为null ，p.next指向当前要放入的Node

                    p.next = newNode(hash, key, value, null);

                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

                        treeifyBin(tab, hash); //  0.1.2.3.4.5.6.7 循环了八次，放入当前节点，即

                                                                    超过八个节点，则转为红黑树

                    break; //over 退出循环

                }

                if (e.hash == hash &&

                    ((k = e.key) == key || (key != null && key.equals(k))))

                    break; // 如果后面节点中由key相同 over 退出循环

                p = e;

            }

        }

        if (e != null) { // existing mapping for key

            V oldValue = e.value;

            if (!onlyIfAbsent || oldValue == null)// onlyIfAbsent为true表示仅当<key,value>不存在时进行插入, 为false表示强制覆盖;

                e.value = value;

            afterNodeAccess(e);

            return oldValue;

        }

    }

    ++modCount;

    if (++size > threshold)  //判断是否需要扩容

        resize();

    afterNodeInsertion(evict);

    return null;

remove方法

public V remove(Object key) {

    Node<K,V> e;

    return (e = removeNode(hash(key), key, null, false, true)) == null ?

        null : e.value;

}

final Node<K,V> removeNode(int hash, Object key, Object value,

                           boolean matchValue, boolean movable) {

    Node<K,V>[] tab; Node<K,V> p; int n, index;

    if ((tab = table) != null && (n = tab.length) > 0 && //如果table不为空，并且长度大于0并且

                        //通过key的hash值与长度所计算出来的数组下标所对应的引用不为空

        (p = tab[index = (n - 1) & hash]) != null) {

        Node<K,V> node = null, e; K k; V v;

        if (p.hash == hash && //如果hash值相同，且key也相同

            ((k = p.key) == key || (key != null && key.equals(k))))

            node = p; //把这个节点拿出来

        else if ((e = p.next) != null) {//如果hash相同 ，key不相同，并且下一个不是null

            if (p instanceof TreeNode)

                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);

            else {

                do { //找到hash相同 key相同的节点

                    if (e.hash == hash &&

                        ((k = e.key) == key ||

                         (key != null && key.equals(k)))) {

                        node = e; //找到了

                        break;

                    }

                    p = e;

                } while ((e = e.next) != null); //循环整个链表，知道为空 此时 p.next = e

            }

        }

        //matchValue if true only remove if value is equal

        //如果为真，则仅在值相等时删除 ！false

        if (node != null && (!matchValue || (v = node.value) == value ||

                             (value != null && value.equals(v)))) {

            if (node instanceof TreeNode)

                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);

            else if (node == p)

                tab[index] = node.next;

            else

                p.next = node.next; //直接把p.next 指向 当前要删除的节点的next 即跳过了当前节点

            ++modCount;

            --size;

            afterNodeRemoval(node);

            return node;

        }

    }

    return null;//没找着

}

不足之处，还请指出，谢谢！

附上链表转红黑树的方法

链表转红黑树

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(); //如果table的长度小于 MIN_TREEIFY_CAPACITY  即64 则会选择扩容

    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);

    }

}

巴特西

HashMap的个别方法

最新文章

热门文章