Data Structures

Question 1

What are the functions of a Hash Table?

Answer 1

Search, Insert, Delete

Question 2

What are the running times of Hash Table functions?

Answer 2

Search O(1). Insert O(1). Delete O(1).

Question 3

Why is it called a hash table?

Answer 3

A hash function is used on key k to compute the destination slot.

Question 4

What is the linked-list collisions resolution called?

Answer 4

Chaining

Question 5

What are the differences between an ArrayList and a Vector?

Answer 5

An ArrayList is not thread-safe, while the Vector is. However, this means that the ArrayList may be a faster data structure. The ArrayList doubles in size when mas size is reached, which means it grows exponentially. The Vector grows by a specified, constant size.

Question 6

What is the running time for an ArrayList?

Answer 6

The ArrayList provides constant time access O(1), amortized over time. The reason being that it is doubled every time space runs out. Therefore the frequency of resizing drops substantially.

Question 7

When might you want to use StringBuffer?

Answer 7

When you plan on doing an operation that will require making many copies of a string. Such as repeated concatenation to the end of the same string. Since Java strings are immutable, the string would have to be copied for every concatenation