在Java中限制HashMap的最大大小

Question

我想限制HashMap的最大大小，以便对我正在实现的多种哈希算法进行度量。我查看了一个HashMap的重载构造函数中的负载因子。

HashMap(int initialCapacity, float loadFactor) 

我尝试在构造函数中将loadFactor设置为0.0f（意味着我不希望HashMap的大小增长）。但是javac报错说这是无效的：

Exception in thread "main" java.lang.IllegalArgumentException: Illegal load factor: 0.0
        at java.util.HashMap.<init>(HashMap.java:177)
        at hashtables.CustomHash.<init>(Main.java:20)
        at hashtables.Main.main(Main.java:70) Java Result: 1

有没有其他方法可以限制 HashMap 的大小，使其不会无限增长？

- andandandand

---

当地图已满并尝试插入另一个元素时，应该发生什么？ - biziclop

只是提醒一下，哈希表需要压缩它们的键空间，因为你不能保留2^31 * 4字节的内存空间来保存每个可能的键的值。因此，哈希表通常会截断哈希并使用链表来处理冲突。loadFactor大致表示在表开始使用哈希的更多位之前，链表的最大大小。因此，长度为0的链表没有意义：你无法在其中存储任何东西。 - chacham15

负载因子表示何时增加数据结构的大小。初始大小（i）和负载因子（x）意味着当我们有i * x个元素时，我们会增加大小。如果x = 0，则相当于要求Java在有0个元素时增加数据结构的大小。 - Sriman

Answer 1

你可以创建一个新的类来限制HashMap的大小，具体实现如下：

public class MaxSizeHashMap<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public MaxSizeHashMap(int maxSize) {
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

- WhiteFang34

---

只是为了澄清，如果我理解正确的话，这种方式在插入新元素时，它只会从映射中删除最老的元素，并将新元素替换进去，从而将大小限制为 maxSize。这并不意味着它不允许您添加新元素。 - Alaa M.

Answer 2

有时候简单就是更好的选择。

public class InstrumentedHashMap<K, V> implements Map<K, V> {

    private Map<K, V> map;

    public InstrumentedHashMap() {
        map = new HashMap<K, V>();
    }

    public boolean put(K key, V value) {
        if (map.size() >= MAX && !map.containsKey(key)) {
             return false;
        } else {
             map.put(key, value);
             return true;
        }
    }

    ...
}

- Mike

---

此答案限制了您的Map的最大大小。请参考Margus的答案，使用更简单的Map来防止添加或删除条目。 - matt burns

@mattburns，这不就是问题吗？还是在你的评论之后重新表述了问题？ - Sriman

@sriman，是的，这符合问题标题，但不符合详细问题描述。OP希望它永远不会增长（例如，是不可变的）。但是10年后，阅读此内容的人可能只是因为他们搜索了限制哈希映射最大容量而来... 呃 - matt burns

你可以扩展AbstractMap或HashMap来避免重新实现整个Map接口。 - Clement Cherlin

Answer 3

我曾尝试在构造函数中将loadFactor设置为0.0f（表示我不希望HashMap的大小增长），但是javac认为这是无效的。loadFactor为1.0f表示“在HashMap填满100％之前不要增长”。如果被接受，loadFactor为0.0f将意味着“呈指数增长”，这就是为什么它不被接受的原因。

从HashMap文档中可以看到：

容量是哈希表中桶的数量，初始容量只是创建哈希表时的容量。负载因子是允许哈希表在其容量自动增加之前变满的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表会重新散列（即内部数据结构会被重建），以便哈希表具有大约两倍的桶数。

例子：使用默认设置初始化的HashMap容量为16，负载因子为0.75f。容量*负载因子=16*0.75=12。因此，向HashMap添加第13个项目将导致其增长到（大约）32个存储桶。

无效示例：使用容量为16和负载因子为0.0f初始化的HashMap。容量*负载因子=16*0=0。因此，每次尝试添加项目都会触发重新散列和大小加倍，直到内存耗尽。

您最初想要的内容：

如果初始容量大于最大条目数除以负载因子，则永远不会发生重新散列操作。

如果创建具有容量M > N、负载因子为1的HashMap并添加N个项目，则它不会增长。

Map<KeyType, ValueType> nonGrowingHashMap = new HashMap<>(MAXIMUM_MAP_SIZE, 1.0f);

- Clement Cherlin

Answer 4

简单的解决方案通常是最好的，所以使用 unmodifiable 或 Immutable hashmap。

如果您无法更改元素数量，则大小将被固定 - 问题得到解决。

- Margus

---

并不总是更好，因为HashMap在需要处理大量数据时最常用。当使用不可变的哈希映射时，内存消耗可能会成为一个问题。 - Rishi Dua

Answer 5

public class Cache {
    private LinkedHashMap<String, String> Cache = null;
    private final int cacheSize;  
    private ReadWriteLock readWriteLock=null;
    public Cache(LinkedHashMap<String, String> psCacheMap, int size) {
        this.Cache = psCacheMap;
        cacheSize = size;
        readWriteLock=new ReentrantReadWriteLock();
    }

    public void put(String sql, String pstmt) throws SQLException{
        if(Cache.size() >= cacheSize && cacheSize > 0){
            String oldStmt=null;
            String oldSql = Cache.keySet().iterator().next();
            oldStmt = remove(oldSql);
            oldStmt.inCache(false);
            oldStmt.close();

        }
        Cache.put(sql, pstmt);
    }

    public String get(String sql){
        Lock readLock=readWriteLock.readLock();
        try{
            readLock.lock();
            return Cache.get(sql);
        }finally{
            readLock.unlock();
        }
    }

    public boolean containsKey(String sql){
        Lock readLock=readWriteLock.readLock();
        try{
            readLock.lock();
            return Cache.containsKey(sql);
        }finally{
            readLock.unlock();
        }
    }

    public String remove(String key){
        Lock writeLock=readWriteLock.writeLock();
        try{
            writeLock.lock();
            return Cache.remove(key);
        }finally{
            writeLock.unlock();
        }
    }

    public LinkedHashMap<String, String> getCache() {
        return Cache;
    }

    public void setCache(
            LinkedHashMap<String, String> Cache) {
        this.Cache = Cache;
    }


}

- Kanagavelu Sugumar

Answer 6

HashMap类中的put方法负责将元素添加到HashMap中，它通过调用名为addEntry的方法来实现，其代码如下：

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

正如您在此方法中所看到的，如果超过了阈值，则会调整HashMap的大小，因此我建议尝试扩展HashMap类并编写自己的put和addEntry方法以删除调整大小。可以尝试以下代码：

package java.util;

public class MyHashMap<K, V> extends HashMap {


    private V myPutForNullKey(V value) {
        for (Entry<K, V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        myAddEntry(0, null, value, 0);
        return null;
    }

    public V myPut(K key, V value) {
        if (key == null)
            return myPutForNullKey(value);
        if (size < table.length) { 
            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++;
            myAddEntry(hash, key, value, i);
        }
        return null;
    }

    void myAddEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K, V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
        size++;
    }
}

由于put和addEntry无法重写，您需要编写自己的方法，并且您还需要对putForNullKey执行相同的操作，因为它在put内部调用。在put中需要进行验证以验证我们是否尝试在表已满时放置对象。

- Maricel