CODEWITHSUNDEEP
javahashtime-complexity
sssss700121
sssss700121

Reputation: 51

Hash table / insert a new key & value

As I understand, there is a option in java to insert a new key to HashTable. This done by:

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

Where donald is the key, and Trump is the value. If I want to add the value "TrumpY" to "Donald", than I use the same operation:

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

I have a question about the time complexity of this operation. As I understand the time complexity is O(1). But this is relavant for the first and the second operation? because the first need to add a new key to the hash table, and the second need to add only a value to key that already exists.

Upvotes: 1

Views: 3612

Answers (2)

user2030471
user2030471

Reputation:

Inserting a key for the first time is going to take more time as it must create a new instance of java.util.Hashtable.Entry.

Whereas in the case of replacing the existing value for a key, it only has to assign the new value to the value reference in the already existing Entry instance.

Upvotes: 0

Christophe Roussy
Christophe Roussy

Reputation: 16999

To find the slot where the value has to be added, the Map must find the position of this slot. To do this it uses the hashcode of the key. Depending on the underlying implementation there may be collision handling (chaining), ... So if the key already exists the second operation usually takes the time of hash computation + lookup + setting of the value requires.

Read more about the subject: http://en.wikipedia.org/wiki/Hash_table

Upvotes: 3

Related Questions