You can make your own Custom Data Structures!
Data Structures which are provided by the JDK or third party libraries often are designed to fit a multitude of use cases. This creates complexity and reduces performance.
To reduce complexity and maximise performance we need to think about what we care about:
Memory
Read
Write
Delete
A library Data Structure component is often used for a lot of use cases and is trying to be the Jack of all Trades - this may mean that it is not streamlined to reduce memory, read, write and delete times.
A custom Data Structure however can be optimised specifically for one of: read, write, delete or memory. It does not attempt to be Jack of All Trades.
A custom Data Structure may do something like block on get waiting for another thread to put something in the map. Enter the world of Custom Data Structures.
Data Structures use basic primitives like:
Arrays
Linked Nodes
Some use a combination of both. For example a Concurrent Map may create chained Nodes leading off a slot in the array.
When an array is running out of space you start chaining nodes off the index.
This leads us to consider Spring Cleaning - when an array has chained nodes leading of its slots (as a result of having insufficient slots) it may do something similar to Stop the World Garbage Collection Pauses. It may decide to resize the entire underlying Array and copy all the values into it. This is going to cause a sudden decrease in performance which may not be acceptable if the Data Structure is used in an extremely low latency trading platform.
Coding for Extreme low latency
Trading Platforms often care about consistency of performance so they meet their Service Level Agreements. For this we may end up designing the Data Structure so that it does a bit of Spring Cleaning as it goes along so that performance is more evened out over the life of the JVM.
Alternatively we may add lots of RAM to the server and design it in such a way we never need a Stop the World Garbage Collection Pause. So instead of doing incremental Spring Cleaning we simply reboot the JVM at certain times of the day. For example with World Trading Systems there are 1 or 2 hours in the 24 hour cycle where all Trading Systems are not trading. This is usually the time that upgrades are made to the software. They could for example reboot the service to release memory.
In fact some Data Structure designs are used for VERY low latency and only EVER instantiate Java objects at start up of the server. All instances are kept a reference to for the ENTIRE life of the JVM. There will NEVER be a stop the world pause as references to the java objects are never released so they will never be garbaged collected. In fact there is even a Garbage Collector you can use which is called the ZERO Garbage Collector - it basically does nothing - and if you do not code your application well you will run out of Memory.
When designing Data Structures which never instantiate an object after application Start up, you code fore re-use of the object. Typically you will have arrays of objects where fields in the object indicate whether the object is in use or not. Once it is free for usage, its fields are reset and a flag is marked that it is available for usage. This is VERY HARD core data structure design and is used where NANO seconds matter. Sometimes companies will lay optical cable through a mountain at great expense so that their traffic will have less distance to travel than competitor optical cable. This gives a saving of one nano second per meter of optical cable.
Note that a nano second ins one billionth of a second. ie there are 1 billion nano seconds in a second. Or it is a 1 with 9 zero after it. Food for thought.
For the Latency Ball project I coded:
To explain some of the principles of multi threading for Medium Thread Contention environments I coded:
Medium Thread Contention environments use CAS (Compare and Swap) - look at the ConcurrentMap example for an explanation of CAS.