插入哈希的复杂度 Table
Complexity of insert in Hash Table
考虑大小为 M 的初始空散列 table 和散列函数 h(x) = x mod M。在最坏的情况下，时间复杂度是多少（以 Big-Oh 表示法) 如果使用单独的链接来解决冲突（无需重新散列），则将 n 个键插入 table？假设 table 的每个条目（桶）存储一个无序列表。当向无序列表添加新元素时，这样的元素被插入到列表的开头。
在 没有 冲突的情况下，将键插入散列 table/map 是 O(1)，因为查找存储桶是一个常量时间操作。我不希望这在冲突的情况下会有所不同，假设冲突是使用链表 和 解决的，新元素被插入到列表的头部。这样做的原因是，在链表的头部添加一个新元素基本上也是O(1)。因此，在这些假设下插入也应该是 O(1)，因此插入 n 键应该是 O(n).
考虑大小为 M 的初始空散列 table 和散列函数 h(x) = x mod M。在最坏的情况下，时间复杂度是多少（以 Big-Oh 表示法) 如果使用单独的链接来解决冲突（无需重新散列），则将 n 个键插入 table？假设 table 的每个条目（桶）存储一个无序列表。当向无序列表添加新元素时，这样的元素被插入到列表的开头。
在 没有 冲突的情况下，将键插入散列 table/map 是 O(1)，因为查找存储桶是一个常量时间操作。我不希望这在冲突的情况下会有所不同，假设冲突是使用链表 和 解决的，新元素被插入到列表的头部。这样做的原因是，在链表的头部添加一个新元素基本上也是O(1)。因此，在这些假设下插入也应该是 O(1)，因此插入 n 键应该是 O(n).