Hash table / insert a new key & value

Question

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.

The second operation does not add a value to a key that already exists, it replaces it. — Perception
– Perception, Commented Feb 28, 2013 at 14:43

Christophe Roussy · Accepted Answer · 2013-02-28 14:53:01Z

3

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

edited Feb 28, 2013 at 14:53

answered Feb 28, 2013 at 14:43

Christophe Roussy

17.2k5 gold badges94 silver badges87 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

sssss700121 Over a year ago

But what with the case that you add a new key (not just value), it doesn't take more time?

Christophe Roussy Over a year ago

Adding a new key can take more time if there is not enough room left, depends on the underlying implementation and initial settings (capacity, ...). Read the Wikipedia article and you will start to understand how it works.

RudolphEst Over a year ago

Finding the right slot in a hashtable for a key is functionally the same whether inserting or updating the value.

Christophe Roussy Over a year ago

If the key already exists there is less work to do because the map now already contains the required structures (list, capacity...)

user2030471 · Accepted Answer · 2013-02-28 14:55:08Z

0

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.

answered Feb 28, 2013 at 14:55

user2030471

2 Comments

sssss700121 Over a year ago

Thank you, and what the time complexity of create a new instance of java.util.Hashtable.Entry?

Christophe Roussy Over a year ago

More or less constant (depends on the JVM, available memory, GC ...)

Collectives™ on Stack Overflow

Hash table / insert a new key & value

2 Answers 2

4 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related