Hashmap 调整大小实现

Question

我在 Kotlin 中有哈希映射实现。由于某种原因，调整大小后，leetcode 上的测试用例（需要添加大量元素）失败。当我将地图的大小设置为一个大数字（无需调整大小）时，测试通过。我的调整大小函数实现中可能存在什么错误？

const val LOAD_FACTOR = 0.75

class MyHashMap() {
    var map = arrayOfNulls<Entry>(1000)
    var added = 0

    fun resize() {
        var newMap = arrayOfNulls<Entry>(map.size*2)
        for (entry in map.filterNotNull()) {
            var index = hash(entry.key, newMap)
            newMap[probe(index, entry.key, newMap)] = Entry(entry.key, entry.value)
        }
        map = newMap
    }

    fun probe(index: Int, key: Int, m: Array<Entry?>): Int {
        var localIndex = index
        while (m[localIndex % m.size] != null) {
            if (m[localIndex % m.size]?.key == key) break
            localIndex++
        }
        return localIndex % m.size
    }

    fun put(key: Int, value: Int) {
        if (added.toDouble() / map.size >= LOAD_FACTOR) resize()
        var index = hash(key, map)
        map[probe(index, key, map)] = Entry(key, value)
        added++
    }

    fun get(key: Int): Int {
        var index = hash(key, map)
        while (map[index % map.size] != null) {
            if (map[index % map.size]?.key == key) {
                return map[index % map.size]?.value ?: -1
            }
            index++
        }
        

        return -1
    }

    fun remove(key: Int) {
        var hash = hash(key, map)
        while (map[hash % map.size] != null) {
            if (map[hash % map.size]?.key == key) {
                added--
                map[hash % map.size] = null
                break
            }
            hash++
        }
    }

    fun hash(key: Int, m: Array<Entry?>) = key % m.size
}```

Answer 1

正如我在评论中提到的，从您的描述中不清楚到底是什么失败了。可能会或可能不会导致失败的一个错误是您修改的方式

added

。

在

put()

中，每次调用该方法时都会增加

added

的值 并且，在决定是否需要

resize

时，您还假设这是数组中非空元素的数量。

这是不正确的。