java - 哈希表/插入新的键和值

Question

据我了解，java中有一个选项可以向HashTable插入一个新键。这是通过以下方式完成的：

 Hashtable<String,String> hashTable=new Hashtable<String,String>();
 hashTable.put("Donald", "Trump");

唐纳德是关键，特朗普是价值。如果我想将值“TrumpY”添加到“Donald”，则使用相同的操作：

 hashTable.put("Donald", "TrumpY");

我对此操作的时间复杂度有疑问。据我了解，时间复杂度是O(1). 但这与第一次和第二次手术有关吗？因为第一个需要向哈希表添加一个新的键，而第二个只需要向已经存在的键添加一个值。

score 3 · Accepted Answer

要找到必须添加值的槽，Map 必须找到该槽的位置。为此，它使用密钥的哈希码。根据底层实现，可能存在冲突处理（链接），...因此，如果密钥已经存在，则第二个操作通常需要哈希计算 + 查找 + 设置值所需的时间。

score 0 · Accepted Answer

第一次插入密钥将花费更多时间，因为它必须创建一个新的java.util.Hashtable.Entry.

而在替换键的现有值的情况下，它只需将新值分配给value现有Entry实例中的引用。

2 回答 2