代码之家  ›  专栏  ›  技术社区  ›  Adelin

在Java的Hash-Map中,resize是如何工作的?

  •  0
  • Adelin  · 技术社区  · 6 年前

    下面是反编译的java代码,用于将条目放入哈希映射中的方法。

    /**
         * Implements Map.putAll and Map constructor.
         *
         * @param m the map
         * @param evict false when initially constructing this map, else
         * true (relayed to method afterNodeInsertion).
         */
        final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
            int s = m.size();
            if (s > 0) {
                if (table == null) { // pre-size
                    float ft = ((float)s / loadFactor) + 1.0F;
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                    if (t > threshold)
                        threshold = tableSizeFor(t);
                }
                else if (s > threshold)
                    resize();
                for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                    K key = e.getKey();
                    V value = e.getValue();
                    putVal(hash(key), key, value, false, evict);
                }
            }
        }
    

    这个公式是从哪里来的,它是如何工作的?

    float ft = ((float)s / loadFactor) + 1.0F;
    

    还有这个方法的意义是什么

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    
    1 回复  |  直到 6 年前
        1
  •  2
  •   xingbin    6 年前

    currentSize should <= capacity * loadFactor ,意思是什么时候 currentSize / loadFactor > capacity ,我们应该调整地图的大小。这个 +1

    正如它评论的那样, tableSizeFor 用于:

    返回给定目标容量的两个大小的幂。