5
I was doing a project and one of my colleagues mentioned that iterate hashmaps is something to avoid and instead of using hashmap should wear Linked lists.
However I think the versatility of the hashmap can save strings as key allows you to do things like:
hash_distrito->hash_cidade->array_coordenadas(x, y, z)
11
When someone tells you what to do, ask for justification.
Iterating any data structure with a data set is no problem at all in general.
If you want to iterate in a specific way, in a specific structure, and you want a specific result, then you may have a problem.
Essentially all basic data structures can be iterated into complexity Linear o(n). Only it would not be so some very complex and very specific structure that practically nobody uses. You can’t do it in less time than that, and it won’t take any more. So much so that no one puts what the complexity is for this algorithm, it is "always" the same.
Do you want to iterate in a specific order? Does it need to be in the order the elements were entered? Or does it need a specific classification? If you need something like this it is better to use another structure if you can. Maps usually do not have defined order. There are even implementations that allow order, but can only be used in specific circumstances, most maps use scattering tables, which do not allow order.
If you need the order use a array or structure based on it. It’s great in the vast majority of needs.
If you need the sorted data then it should be more interesting to use a tree, which is a linked list that has more than one path to follow in the sequence.
It is very rare for the pure linked list to be useful, usually only when it does not need to be manipulated after being created, except at the (s) tip(s) and also does not need random access, which makes other structures also suitable.
Linked lists, as learned in the course of computing, are essentially not used in the "real world". More sophisticated implementations, probably combined with other structures, may be useful in certain scenarios.
It is very common for people to think that inserting and removing an element from a linked list can be done in constant complexity, because the operation itself is really constant. But you almost always need to get to the point where the element will be inserted or removed, and then the complexity is linear.
I must be one of the few people who use linked list in database under certain circumstances. I used where it gave me some advantage over the normal index that DB already has. Although today it is rare that I have this need. It has to weigh everything to decide which is the best structure.
I’ve seen people turn one array on a map to be able to index in constant time instead of linear. I am not saying that this is useless in all cases, but almost always the complexity has become O(n + k) in the best case, that is only disadvantage. The person forgets to count the time of the copy of the structure. If he had done in the array would be O(n) in the worst case and O(1) in the best.
Perhaps your problem is more suitable for a linked list, but we are not sure what that problem would be. It may require the joint use of more than one structure, and one of them is a linked list (maybe non-traditional).
"I must be one of the few people who use linked list in database under certain circumstances". Aroused my curiosity :)
In modern banks it is less necessary than for extreme optimization. In older banks it is also for optimization. If you have a data that can have an undefined size, can have multiple instances of it and conceptual normalization is not necessary (the data will never be accessed independently of its owner), one way is to normalize physically just to meet the demand of the mechanism, then you need an index in the table to access quickly, which takes up space and costs to make updates. The linked list there eliminates the need for the index (at bottom it is an index that I control)
Of course, it is only useful in a database whose tables are structured as a array (hj Dbs are usually linked lists, even if in tree form), and need to iterate the whole list directly and still not have many elements.
Got it. In this case what you’re calling a linked list in the comics is implemented as a foreign key + index?
No, it is the opposite, it has no index, only the list, it works as an index, but it is not. The point is that today in Dbs every table is an index, so it does not need anything, before they had Dbs that ñ was like this, so it needs a table + index to quickly access what it wants. This way only needs the table, IE, I do in old DB q the new do internally. I do this in NF, the items are LL whose header is in NF and the footer is 0. And the items do the same c/ the description lines of it. It has app q needs the items conceptually normalized, then LL ñ helps (but helps c/ description)
Each item is a row and each one has a column pointing to the next or NULL, is that it? I meant something like that when I said FK, not necessarily a formal key in the bank.
That’s right. I get it.
Browser other questions tagged java performance chain-list hashmap iterator
You are not signed in. Login or sign up in order to post.
Your colleague is probably considering these data structures in an abstract way. A linked list, conceptually, is a structure suitable for iteration, but potentially slow for access to specific items. Hashmap is more efficient than the linked list for access to specific items, which does not mean it is slow to iterate. Actually it will depend on the implementation. In a quick search, I found no references to avoid hashmap iteration.
– bfavaretto
Thank you but if I belong to the structure given as an example. Would you have to create a linkedlist to get the data? or hashmap iteration time is negligible?
– João Marques
Why not just get the key list and iterate with a for normal or Iterator? It seems that you are worried about microtimizations.
– bfavaretto
I would just like to know all the possible solutions to determine whether they are relevant or not. I can only know if the x option is better in order to understand why the other y and z are not so good. To that end I would like to understand my colleague’s point of view.
– João Marques