HashTable in the state of a Web Service


Designing a web service that uses a login and keeps all user data and passwords in memory (does not use any database) have raised doubts when it comes to ensuring a decent level of efficiency:

First, what data structure to choose to save this information. While I think that a HashMap would be a good option, where the usernames would be the keys and the rest of the information (or just the password) would be the values, I would like to know if there are other data structures that fit better.

Also, in the specific case of HashMap , would it be better to use separateChainnig or LinearProbing as a conflict resolution strategy? In the case of separateChaining we are faced with one of the lists of the "holes" of the hashMap was very long and the complexity was linear order in the worst case, but with LinearProbing could be many rehashes.

What do you think?

asked by Jesús Pérez Melero 05.05.2016 в 16:30

2 answers


The structure HashMap already has auto-size mechanisms to avoid falling into linear searches as you indicate. This is explained in another answer: How does HashSet work internally? , where, in summary, a HashMap has an array of nodes, and these nodes can form a linked list or a black red tree, according to the number of elements that that hash has. By knowing this, you can understand that it is not necessary to apply separate chaining or linear probing to solve your problem.

Since you want to store the information in memory, I would rather tell you that you need to consider other things when choosing the appropriate structure:

  • If you only need to preload the users and passwords and then your service will be only for consultation for the login, then you should use HashMap .
  • If additional to the searches you need to add elements to your structure, I recommend that you use ConcurrentHashMap instead of HashMap since the first one already has support included for multiple transactions in parallel, while the second does not have it and you may get an error of ConcurrentModificationException at runtime.
  • You may need to apply other policies to this structure, so I recommend that instead of manually creating and adapting the structure to what you need, evaluate using a cache such as EhCache or Hazelcast or perhaps a NoSQL database key value such as Hazelcast or Redis, which are more complete products and that provide many more features than trying to automate manually.
  • answered by 05.05.2016 в 16:43

    I smell a long way off premature optimization . In 99.9999% of the cases, it is irrelevant to ask for the details of internal operation of a HashMap . And I think that is your case.

    More should worry about how you're going to have a user map => keys in memory ... those keys are unencrypted? From where they come? In general, it is dangerous to have the keys stored (in database, files or memory), it is recommended to have only one hash .

    answered by 05.05.2016 в 16:43