Java Basic Data Structure

What is hashtable?

Hashtable is a data structure, which can map keys to values. 

A hash function is used to compute an index of an array, from which the correct value can be found.

两种实现方式(collision resolution): Open hashing & Closed hashing

区别: whether the collisions are stored outside of the table or at other slots inside the table

Open hashing(separate chaining): Easier to implement; more efficient for large records or sparse tables; Typically, table index = hash(key) % array_length.

Closed hashing(open addressing): More complex but can be more efficient, esp for small data records. (Searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table)

What is linkedlist?
Each
 node 
in 
a
 linked
list
 contains
 an
 element
 and
 a 
pointer 
to
 the
 next 
node
 in
 the 
linked
list.

 A
 list
 may
also 
be 
doubly 
linked,
 in which 
case
 each
 node
 also
 has
 a 
pointer
 to 
the
 previous
 node.


It
 takes 
constant
(O(1))
 time to
 add
 a
 node
 to 
or
 remove
 a
 node
 from
 a
 linked
list. It
 takes
 O(n) 
time
 to
look
 up 
an
 element
 in
 a
 linked
list(doesn’t support random access).

What is array?
array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index.

Static arrays have a size that is fixed when they are created, and doesn't allow insert and remove.

Both store and select take (deterministic worst case) constant time. Arrays take linear (O(n)) space in the number of elements n that they hold.

What is vetor?

Dynamic array.  Support random access, fast element insertion or removal at the end.

Difference between vector and arraylist:

Vector is synchronized

Explain Hashtable, HashMap, TreeMap, ConcurrentHashMap, LinkedHashMap.
Hashtable:
· It didn’t allow null for both key and value. You will get NullPointerException if you add null value.
· It is synchronized. So it comes with its cost. Only one thread can access in one time
HashMap:
· It allows null for both key and value
· It is unsynchronized. So come up with better performance
HashSet:
· HashSet does not allow duplicate values. It provides add method rather put method.
TreeMap:
· TreeMap provides guaranteed O(log n) lookup time (and insertion etc), whereas HashMap provides O(1) lookup time if the hash code disperses keys appropriately. Not thread safe.
· The values are sorted.
ConcurrentHashMap:
· The ConcurrentHashMap uses very sophisticated techniques to reduce the need for synchronization and allow parallel read access by multiple threads without synchronization.
LinkedHashMap:
· LinkedHashMap will iterate in the order in which the entries were put into the map