Best way to initialize a HashMap

I usually do e.g.

HashMap<String,String> dictionary = new HashMap<String,String>();

I started to think about it, and as far as I know a HashMap is implemented under the hood via a hash table.

The objects are stored in the table using a hash to find where they should be stored in t开发者_开发百科he table.

Does the fact that I do not set a size on the construction of the dictionary makes the performace decrease?

I.e. what would be the size of the hash table during construction? Would it need to allocate new memory for the table as elements increase?

Or I am confused on the concept here?

Are the default capacity and load adequate or should I be spending time for the actual numbers?

---

The nice thing about Java is that it is open-source, so you can pull up the source code, which answers a number of questions:

1. No, there is no relationship between HashMap and HashTable. HashMap derives from AbstractMap, and does not internally use a HashTable for managing data.

2. Whether or not omitting an explicit size will decrease performance will depend upon your usage model (or more specifically, how many things you put into the map). The map will automatically double in size every time a certain threshold is hit (0.75 * <current map capacity>), and the doubling operation is expensive. So if you know approximately how many elements will be going into the map, you can specify a size and prevent it from ever needing to allocate additional space.

3. The default capacity of the map, if none is specified using the constructor, is 16. So it will double its capacity to 32 when the 12th element is added to the map. And then again on the 24th, and so on.

4. Yes, it needs to allocate new memory when the capacity increases. And it's a fairly costly operation (see the resize() and transfer() functions).

Unrelated to your question but still worth noting, I would recommend declaring/instantiating your map like:

Map<String,String> dictionary = new HashMap<String,String>();

...and of course, if you happen to know how many elements will be placed in the map, you should specify that as well.

---

Does the fact that I do not set a size on the construction of the dictionary makes the performace decrease?

Depends on how much you're going to store in the HashMap and how your code will use it afterward. If you can give it a ballpark figure up front, it might be faster, but: "it's very important not to set the initial capacity too high [...] if iteration performance is important" 1 because iteration time is proportional to the capacity.

Doing this in non-performance-critical pieces of code would be considered premature optimization. If you're going to outsmart the JDK authors, make sure you have measurements that show that your optimization matters.

what would be the size of the hash table during construction?

According to the API docs, 16.

Would it need to allocate new memory for the table as elements increase?

Yes. Every time it's fuller than the load factor (default = .75), it reallocates.

Are the default capacity and load adequate

Only you can tell. Profile your program to see whether it's spending too much time in HashMap.put. If it's not, don't bother.

---

Hashmap would automatically increase the size if it needs to. The best way to initialize is if you have some sort of anticipating how much elements you might needs and if the figure is large just set it to a number which would not require constant resizing. Furthermore if you read the JavaDoc for Hashmap you would see that the default size is 16 and load factor is 0.75 which means that once the hashmap is 75% full it will automatically resize. So if you expect to hold 1million elements it is natural you want a larger size than the default one

---

I would declare it as interface Map first of all.

Map<String,String> dictionary = new HashMap<String,String>();

Does the fact that I do not set a size on the construction of the dictionary makes the performace decrease?

Yes, initial capacity should be set for better performance.

Would it need to allocate new memory for the table as elements increase

Yes, load factor also effects performance.

More detail in docs

---

As stated here, the default initial capacity is 16 and the default load factor is 0.75. You can change either one with different c'tors, and this depends on your usage (though these are generally good for general purposes).