Hello!!

Here, I'd like to talk about some info we have pay attention of some data structure to decide which is the best choice in your scenario. Some kind of knowledge that many times we don't pay attention in day-by-day.

HashMap

HashMap is a data structure that map keys to values. In Java, it is a collection class which implements Map interface.

  • Key: HashMap (1) can have only unique keys, (2) only one 'null' key.
  • Value: It can be mapped to many keys,.
  • This structure only store object references, not primitive.

The HashMap is not thread-safe, so, if you need to synchronize the object, you can use Collections.synchronizedMap(hashMap), which will control all the structure (all operations - read and write), or you can use ConcurrentHashMap that will control only write operations. It happens because the last one locks only a portion of the object and the method synchronizedMap lock the whole map. The HashTable is the legacy when you needed to have a synchronized object.

How it works

This sort of structure use hash principle to converts an object into an integer form. Each value resulted from the hash function will represent a position in the HashMap array. That position is an element called 'Bucket'. Then, when is given a key the process will calculate the index of the array:

  index = hashCode(key) & (n-1) //n is the size of the array

The pair key-value is stored such a node, which in Java is an instance of the inner class HashMap.Entry. The Bucket can have more than one node related. It happens in case of a collision. In that case, a linked list structure is used. From Java 8, when the number of nodes becomes larger, the structure used is a balanced tree to improve the performance.

In terms of methods, It uses hashCode to find the position and uses equal to find the key in the linked list. If the key exists and the operation is to add new value, the old value is replaced. If not exist a new node is created. If the operation is to retrieve the value, it will find the key and get the value. The operation to retrieve value is O(1). The worst case using a linked list is O(n) and using a balanced tree is O(logn). The tree uses less space since is not necessary to allocate a large array.

You can try this structure using this animation.

ArrayList

In some languages, arrays and list are resizable.  In Java, an array's size is defined when it is created. The ArrayList is the dynamic resizing array. The access is O(1), but when you add a new value it can have some complexity. If the array is full another one is created with the double of the size and all the elements are copied to the new array, then it can be O(n).

Comparing with LinkedList, ArrayList is batter to retrieve values. If you will have many operations to add new values is better to use LinkedList.


You can try the LinkedList using this animation

String

Strings are immutable and always create a new object. Each new String object is stored in the pool to the application reuse the objects.

  String str = "abc"; //the object in the pool is used
  String str2 = new String("abcd"); // create a reference</pre>

from post: What is Java String Pool


If you need to update the same object many times you should use String Builder. It updates the existing object value.

String Builder and String Buffer use the same instance to update the object. The difference between them is that the Spring Buffer is synchronized (thread-safe).

Stacks and Queues

Stack: LIFO (last-in, first-out) | pop, push, peek: O(1) | lookup: O(n)

Queues: FIFO (first-in, first-out) | enqueue, dequeue, peek: O(1) | lookup: O(n)

The LinkedList has complexity of O(1) to insert and delete elements. It makes that structure a good choice to implement (stack and queue structures.


Big O Common Data Structure



You can see more detail about that in Big O Cheat Sheet


Which structure to use: Set, Map or List

Sometimes is hard to decide which structure is the best to each case. One image can explain better. In the stackOverflow discussion, someone create an image that can help it.



StackOverflow: Which Java Collection should I use?
This image was created for that answer in StackOverflow and is licensed under a Creative Commons Attribution 4.0 International License. The simplest attribution is by linking to either that question or the answer.


References