Understanding of Java Collections
From the first look, Java Collection is a set of structures that fit different problems. But in practice, Java Collection interfaces represent notions from discrete math.
Join the DZone community and get the full member experience.Join For Free
Java Collection is a pretty favorite subject in Java articles. But here, I'll share my personal thoughts and ideas that you might not know.
Discrete Math and Java Collection
From the first look, Java Collection is a set of structures that fit different problems, like quick data search. But in practice, Java Collection interfaces are representing notions from discrete math.
Discrete Math Set Concept
Basically, every data structure is set but with specific characteristics. Each set can be represented as a figure, for example, a set on numbers might be drawn like this:
Well in Java Collection we have something similar:
Discrete Math Set Concept and Java Collection
Java Collection interface declares the mandatory method for all its children. Almost all methods existent in the Collection interface are corresponding to discrete math notions, let's write well-known expressions:
Element belongs to set:
The same expression in Java:
In set theory, we should be able to indicate/iterate all elements that belong to a set.
In a collection, this functionality is implemented using mandatory iterator for each collection:
In the same way, Java Collection provides methods like size/add/remove/etc that also have matches in Discrete Math Set notion.
As was previously shown Java Collection is the parent for all Java Collection implementations, so we next expression will be successfully compiled:
Such expression cast all implementation to the collection and recognize them as Set from Discrete Math. I hardly believe that you would use the Collection interface that way and this example used only for explanation purposes.
Heirs of Java Collection
Java Collection interface is the parent interface for all collection and it's inheritor also represent data structure from Discreet math:
- List interface corresponding to a data structure with random access like get(5) but under the hood, it has 2 implementations - based on an array (or also known as a sequence) and on a linked list.
- Set interface corresponding to a data structure with unique elements.
- Queue interface is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.
Java Collection What is Under The Hood
Well, the first part of the article was a rather theoretical approach to interpret the Java Collection idea. But what are all Java Collection's implementations based on? Knowing the number of Java Collection heirs, you might think there are many different structures, but in reality, there are only 2 principal way to represent data:
Array or Sequence
The array data structure, or also known as a sequence, is the most popular data structure and can be easily recognized if the data structure has the prefix 'Hash' or 'Array.' e.g., HashMap, HashSet, ArrayList. This structure is used to create structures with quick access to data, quick set.
Example of the implementation is pretty easy:
Reference Is Based Structure for All Linked List or Tree Structures
Well, it's difficult to name reference as a data structure, but it's principally the only one different from array way to persist the data. The idea of the reference is to have kept the reference between objects inside your structure. Such structures have the advantages of a quick search, quick inserting, and some others. Practically there are 2 main structures that are built on top of it:
1. Linked List; let's write a simple example of it:
So if we draw it - it would like like this:
2. Tree Structure is also a reference-based structure and the only difference from Linked List is that it should have 3 references instead of only one:
So if we draw it, it would looks like this:
Instead of Conclusion
I hope this article helped you to understand the Java Collection structure and its basic implementation ideas. Might be the implementation of Java Collection isn't perfect but many other languages only dream about such user-friendly and yet performant structures. Thank you for reading.
Opinions expressed by DZone contributors are their own.