r/javahelp • • May 07 '20

Codeless Java Developers: what are the common data structures you usually use on production

To professional java dev here, what are the common data structure youve been using and which data structure you strongly suggest for beginners, like me, to study carefully

40 Upvotes

38 comments sorted by

2

u/[deleted] May 07 '20 edited May 07 '20

Which datastructure should be used hardly depends on which use-case you got.

Data structures do have advantages or disadvantages when it comes to accessing / inserting / deletion and searching (of) values.

You will mostly try to determine based on the use-case which of this operations is the most crucial in your case and you select a datastructure which is fitting your needs and gives you the best performance overall.(Performance in this case can be a better time or space complexity depending on what you need for your application )

You can determine this by using the BigO Notation which tells you pretty much which data structure is the best choice for your use case.

I think if you take a look at the big o cheat sheet you can pretty much see all the commonly used data structures and i think its not a bad idea to implement them once for yourself so you have a better picture of what is happening behind the scenes.(I had to do that in my course at university back in the day as cs student and i can say it comes in handy when you try to implement algorithms like for example a dijkstra algorithm or anything like this when you are familiar with graphs and graph theory .)

You should definitly know how linked lists work , how stacks work and queues.Also it is pretty good to know about graph theory and graphs in general and know how to implement a B-Tree a binary tree an AVL tree and stuff like that.Also you should know about Hash tables and how they are implemented. It is not crucial to know about this stuff to use them but it will definitly give you a good understanding about why and how they are used in the most useful way.

You should take a look at this cheat sheet ( https://miro.medium.com/max/1400/1*wv3W3jYq7EHCDiwYVaCXrA.png ) and look at the left side where data structures are displayed and the worst case and average complexity. Also knowing about BigO Notation comes in very handy when it comes to determine which data structure is the right one for your use-case.

Experienced java dev here btw.

(Edit:

I want to add this youtube link for you for the big o notation , i think

this dude explains it quite well.

https://www.youtube.com/watch?v=D6xkbGLQesk.

Also here is a series of the same guy on data structures which the big o notation

video is a part of.

https://www.youtube.com/watch?v=bum_19loj9A

To also answer your question somehow:

Lists and maps are heavily used.Also sets and arrays ofc.

Which ones?

That depends on the use case because the implementation of different lists give you different results when it comes to space and time complexity.

)

Have fun learning ! :)

2

u/[deleted] May 08 '20

Cs Dojo is a cool man. :) been watching some of his videos but not yet encountered these links. Thanks btw

34

u/ObscureCulturalMeme May 07 '20 edited May 08 '20
  1. The built-in Collections framework goes a long, long way. Even when it comes time to roll a custom structure, basing it off one of those gets you a very solid start.

  2. I believe that a pair of Countdown Latch objects, properly applied, can solve all communication problems including peace in the Middle East.

  3. What I've found myself missing is not so much a data structure exactly, but the ability to return more than one thing from a function, the way (for example) Lua can. The way to do that in Java (and its parent languages) is to build an aggregate structure and return that "one" thing, but it's tedious no matter how you implement the aggregates. I'm looking forward to someday working with java 14 and its records, for this reason.

6

u/Sputtrosa May 07 '20

What I've found myself missing is (...) the ability to return more than one thing from a function

That's interesting. I've never worked with a language that returns more than one thing. Do you have some real-life examples on when it would be particularly useful and Java doesn't have trivial workarounds?

6

u/99shadow25 May 07 '20

The workarounds may be trivial, but they're still annoying when there's just a simpler way to do it in many languages. MATLAB, for example:

function [x, y, z] = find3dPoint(c)

you can call this and declare the three variables:

[a, b, c] = find3dPoint(15)

Python similarly natively supports tuples and destructuring them, with a similar syntax

(angle, magnitude) = create_vector()

In Java you NEED to write the class definition for and then instantiate a specific object. Personally, I think supporting tuples is the cleanest way, but I'm not sure how difficult the static typing system would make incorporating this.

6

u/ObscureCulturalMeme May 07 '20

The workarounds may be trivial, but they're still annoying when there's just a simpler way to do it in many languages.

Exactly this. All of the "real world" examples have equivalent workarounds in Java, but they all boil down to: (1) create some object that can handle all the information you want to communicate, (2) populate it, then (3) return it so that calling code can (4) take it back apart.

Whereas languages like Python and Lua allow the programmer to simply write (2) inside the function and (4) outside it.

It might be "only syntactic sugar" but that kind of thing matters, and changes how we think about data handling. If it did not, we'd still be using PEEK and POKE because everything else is just syntactic sugar...

2

u/Sputtrosa May 07 '20

Thank you for the great reply. :)

Going to have to give that a bit of thought.

1

u/[deleted] May 08 '20

The least annoying way to do this that we've created where I work is we have generic classes set up in a library: Pair<X, Y>, Triple<X, Y, Z> and so on, all the way to I think 10 elements. They have a static generic creation method, E.G. Pair.get(firstVariable, secondVariable), but whoever receives this as a return still has to do Pair.getA() then Pair.getB(), for example.

3

u/wildjokers May 07 '20

but the ability to return more than one thing from a function, the way (for example) Lua can

This is absolutely the thing I miss most in Java after working in groovy and kotlin.

When I was first learning groovy and I saw it allowed multiple return values I was like "why would I ever need that?". Oh, how naive I was. I ended up using it all the time. Then when I would switch back to Java I missed it greatly (and still do everyday).

2

u/philipwhiuk Employed Java Developer May 07 '20

The built-in Collections framework goes a long, long way. Even when it comes time to roll a custom structure, basing it off one of those gets you a very solid start.

And you should only bother when there's a really sizeable need to IMO.

3

u/MrSquicky May 07 '20

I believe that a pair of Countdown Latch objects, properly applied, can solve all communication problems including peace in the Middle East.

I'd love to hear more about this. I'm using Spring's DeferredResult in what I think is a similar context. I'm aware of CountDownLatches, but I've never used them.

1

u/Yithar Intermediate Brewer May 08 '20 edited May 08 '20

I have used them in combination before. Hmm, thinking about it, maybe they're not so different.

I see DeferredResult a sort of like callbacks in Javascript with the event loop. Like frontend JS often involves fetching JSON or something.

I feel CountdownLatch is more of like you're waiting for a certain number of things to happen, like maybe you need to get 2 messages back before something that can happen. I can't go into too much detail I think, but basically I was waiting for 2 requests I sent over the messaging protocol, to respond back. And then the logic would execute to process the responses so the GraphQL server could respond to the request it originally received.

It seems to me as similar to race conditions and data races. You can have a race condition without a data race, for example.

0

u/DepletedSensation May 07 '20

Im not 100% sure what he might mean here. But like JavaScript can return more than one object from a list based off of a filter or value. (Say if price is less than 5$, or if title starts with "A")

To my knowledge there is no built in function for this in Java, you have to write a stream or your own method that returns a list with this desired filter applied.

3

u/MrSquicky May 07 '20

Oh, no, that I get and totally agree with. He's looking for a decomposable tuple return. Me too.

So like you could return ("foo", 10) from a function and read that as (text, count) and have text = "foo" and count = 10.

Python does this really nicely. Kotlin has it too, but it's not quite as nice because, as far as I know, it needs to be typed (although I can't imagine wanting to return more than 3 things from a function anyway). It kind of sucks to return Object[] and then need to read it out of it.

---

CountDownLatches are used with Threads for controlling concurrent access. I'm aware of the concept, sort of. If my understanding is right, they're sort of like Futures with a numeric countdown you can attach to it so that when the countdown goes to zero, it completes. I've never used them and would be interested in learning how other people are using them. I love finding out cool usages of parts of a languages that I didn't know about.

I found myself in a situation where we're doing real time messaging, but not able to use web sockets because of technical limitations, so I'm using long polling by leveraging Spring's DeferredResult and I'm not sure if we're talking in the same area or not.

1

u/DepletedSensation May 14 '20

Yea I mean the way I would handle that is by using Pairs and stuff.

Also, about the Future and Threads, well it's so rarely we get to use them unless we really need to right? It kind of sucks. I can deffinitely recommend a book, "Java Concurrency In Practice" by Goetz. He helped design the Concurrency package in Java 6. :)

1

u/Yithar Intermediate Brewer May 08 '20

What I've found myself missing is not so much a data structure exactly, but the ability to return more than one thing from a function, the way (for example) Lua can. The way to do that in Java (and its parent languages) is to build an aggregate structure and return that "one" thing, but it's tedious no matter how you implement the aggregates.

Yeah this is one of the reasons I love Scala. And Scala also supports pattern matching as well.

https://docs.scala-lang.org/tour/tuples.html

1

u/[deleted] Jun 06 '20

How will records imrove that? As transfer objects?

1

u/ObscureCulturalMeme Jun 06 '20

Reduces the tedium

2

u/[deleted] May 08 '20

[removed] — view removed comment

2

u/ObscureCulturalMeme May 08 '20

Hadn't seen that one before, thanks! I'm a big fan of the idea of compile-time annotation processors. (In practice they've always been a pain in the ass to get running with Ant or Gradle, but everything improves with time.)

11

u/Camel-Kid 18 year old gamer May 07 '20

I've only done small work in an enterprise environment for summer job but to me it looked as if the normal collections like any implementations of list,set,maps are used ... Learn collection framework and you'll be fine.

11

u/PrinceValkyr May 07 '20

Mainly arrayLists, sets and Maps occasionally.

8

u/StateVsProps May 07 '20

What you use on the job and what is required for interviews is (infamously, unfortunately, sadly) very different.

5

u/MrSquicky May 07 '20

Everyone is going to tell you to use the the standard Collections framework. It's really good, to the point that I forget that it is not a built in part of languages and get frustrated when I'm working with languages that don't have it. You're mostly going to use Lists for basically extensible arrays and Maps for associated data, and sometimes Sets for when you want a unique collection of something and don't care about accessing by index (although you can with the the right subclass).

Coupled with that, learn how to use Streams, which are built to work very well with Collections.

A few other useful structures are:

  1. Map<Key, List<Values>> - great for grouping a list of items based on some criteria. I used to use Guava's Multimap for this, but with streams, I'm usually using the Collectors.groupingBy, which goes right to the Map and it is awesome. Also with streams, you can chain your Collectors.groupingBy to have as many layers of grouping that you want, so like Map<Year, Map<Month, Map<Region, Records>>> or whatever.

  2. A counting set or bag. Basically a map from objects to how many times it occurs. Guava's Multiset is still my go to for this.

  3. A Range. If you ever find yourself writing a startX and endX as separate properties in a model, you're probably doing something wrong. Ranges are a much superior solution, in large part because they encapsulate the logic you want for a range in them. Also really important, they can be used in things like RangeMaps, which let you register ranges for your keys but do lookups based on a single value. So, like you could create a scheduling thing that has an entry for 9:00-11:30, 2:00-2:15, 9:00am-5:00pm and then just enter a time and it will show you all the ongoing events. I think there are implementations out there, but I wrote my own for this that at some point or another I'll put up on Github because I was frustrated with what was out there.

  4. A nested set model. When I wrote this, I called it a boundary tree, but I've found that the accepted name is nested set. The idea here is that you can easily determine where something falls in a hierarchy by checking additional number boundary properties. So, each item has a range that marks its start and end and each level of the hierarchy is expanded when something is added to it. So, if I have an item that starts at say 60 and ends at 75, I can tell immediately what all of its parents are as they all have to contain 60 and I know that all of its children are contained in 60 - 75. This lets you do a single lookup instead of chaining lookup parent, lookup parent, lookup parent, etc.

---

Outside of those, if you're talking about data modelling, you want to consider your relationships and your total object graph.

These are both really large topics in and of themselves. The basic concept is to understand the semantic type of your relationships, not just their physical structure and consider how they make up coherent graphs of objects. I actually disagree with a fair bit of it, but Eric Evan's Domain Driven Design is still the best resource I've seen for understanding this.

2

u/Yithar Intermediate Brewer May 08 '20

3) A Range. If you ever find yourself writing a startX and endX as separate properties in a model, you're probably doing something wrong. Ranges are a much superior solution, in large part because they encapsulate the logic you want for a range in them. Also really important, they can be used in things like RangeMaps, which let you register ranges for your keys but do lookups based on a single value. So, like you could create a scheduling thing that has an entry for 9:00-11:30, 2:00-2:15, 9:00am-5:00pm and then just enter a time and it will show you all the ongoing events. I think there are implementations out there, but I wrote my own for this that at some point or another I'll put up on Github because I was frustrated with what was out there.

I know this is r/javahelp, but I just wanted to state that Scala has Ranges built-in, just like it has Tuples built-in.

https://scastie.scala-lang.org/ZfqD4yR2Tk6VvcuzUGNTQw
https://www.scala-lang.org/api/2.12.2/scala/collection/immutable/Range.html

1

u/knoam May 08 '20

I haven't used nested sets before, but otherwise this comment is like you read my mind.

8

u/Ryuuji159 May 07 '20

I mostly use ArrayLists and when I fell fancy I sprinkle some HashMaps here and there

3

u/Orbitaliser May 07 '20

All of the collection framework. You want to learn the inheritance hierarchy and use interface types as parameters/declarations as often as possible.

List<String> strings = new ArrayList<>();

So you can swap between the implementations as required. Only use a specific structure if you need a specific feature in one of the subclasses e.g. TreeSet#tailSet but always start as general as possible.

Learn generics thoroughly as well so you know how to make your own customised structure if the need arises.

3

u/jocularamity May 07 '20

Lists, Maps, Trees, and Queues.

As a beginner, get a general sense of each and when it should be used.

2

u/firsthour Profressional developer since 2006 May 07 '20

99% of the time it's a Map, List, or Set. Very, very seldom a Bag.

You have to know exactly when to use a Map, List, or Set. Understand the difference between them because most of the job is just moving things around in those structures.

For specific implementations, 95% of the time it's a HashMap, ArrayList, or HashSet.

1

u/sweepsz Decaf Captain May 07 '20

ArrayList, HashSet, Hashmap, LinkedList, ConcurrentHashMap are going to be your daily drivers. There others like binary search tree but are more niche in their usage. Most libraries you would be using abstract all that away from you under the implementation.

1

u/DepletedSensation May 07 '20

Imo, use hashmaps more than you normally would! In the past id write a class that holds a list, but its far more concise to have maps with say lists within them.

Thats the only collection I see used now that I underestimated as a student. Perhaps i was the only one but i doubt it. :)

1

u/snot3353 COMPUTERS!!! May 07 '20

99.81627% of the time it’s just an ArrayList or HashMap. Occasionally other implementations or data structures are relevant but it’s rare. Only twice can I think of a scenario where the standard libs didn’t have what I needed and in those cases I was able to to Guava to provide them.

1

u/Yithar Intermediate Brewer May 08 '20 edited May 08 '20

I think most people would agree that Maps are used fairly often. But I would agree the Collections framework goes a long way.

That being said, it's important to understand how your data structures work.

Also don't use LinkedList over ArrayList unless you know you need a LinkedList for what you're doing.

1

u/de_vel_oper Jul 19 '20

Red black trees

-1

u/SpoilerAlertsAhead Extreme Brewer:hamster: May 07 '20

Kotlin has Pair (commonly referred to as Tuple in other languages) that in write when I’m stuck in Java land.

-3

u/wsppan May 07 '20

Mostly use the Spring Framework and all its associated design patterns and abstractions. Most notably, Dependency Injection and Spring Data. We also use AOP for cross cutting concerns like security and logging. Most data structure concerns are built into the language via Java Collections so we use Enums for constants, Lists for dynamic arrays, and Maps for hashes. We mostly focus on design patterns and associated abstractions as that is more important than the underlying data structures because those come free are already optimized and (most) built for concurrency.