Data Structures for hashMap, List and Set

Can any one please guide me to look in depth about t开发者_开发知识库he Data Structures used and how is it implemented in the List, Set and Maps of Util Collection page.

In Interviews most of the questions will be on the Algorithms, but I never saw anywhere the implementation details, Can any one please share the information.

---

To learn how Java implements collections, the definitive place to go is the source code itself, freely available. Generally, Lists are implemented as either arrays (ArrayList) or linked lists (LinkedList); sets are either hashtables (HashSet) or trees (TreeSet); and maps are hashtables (HashMap).

Algorithms for manipulating arrays, linked lists, hashtables, and binary or n-ary trees (add, remove, search, sort) are complex enough in themselves that an entire course is necessary to cover them all. Anyone doing their own program design typically needs to understand these algorithms and their performance tradeoffs by heart. There's no substitute here for textbook study and/or practice.

---

The source code of the API is available, get a JDK and open up the src.zip file from the installation folder.

---

ArrayList: array

LinkedList: doubly linked list (Entry objects)

HashMap: array of Entry objects each Entry pointing to singly linked list

HashSet: internally uses HashMap, stores data as Key and dummy Object (of class Object) as Value in the map.

TreeMap: Red-Black tree implementation of Entry objects.

TreeSet: internally uses TreeMap. Key as data and dummy object as value.

*Entry: is an internal class in these collections and generally has Key, Value, references for other Entry objects etc.

---

You can always open the source files, it's all there, however, I wouldn't recommend it as usually they are quite hard to understand. Instead, I'd try finding the underlying data structure, and looking it up. Wikipedia contains most of the information you want to know on these subjects, and google contains the absolute rest.
List is just a dynamic array,
Set is a... set,
And maps are usually hash tables keyed by the key's hash, and stored as key-value pair.
If you're going to dive into the source code, I'd recommend familiarizing yourself with "how-it-probably-works", cause otherwise it will be hard to understand, especially the hash table.