Data Structures Flashcards
What’s the difference between a Vecor and an Array list?
What is the difference between ArrayList and HashSet?
- ArrayList is backed by an array while HashSet is backed by a hashmap.*
- ArrayList allows duplicates, HashSet does not.*
- ArrayList insert by the order of insertion. HashSet inserts randomly.*
- ArrayList is index-based(get,set), while HashSet is object-set*
- HashSet is a Set while ArrayList is a List*
When should we prefer an ArrayList over LinkedList and vice versa?
ArrayList - when we more freuently need to search for elements rather than add/remove elements.
LinkedList - when we more frequently need to add/remove elements rather than search for elements.
What are the similarities and dissimilarities between HashMap and ArrayList?
Similarities:
- Both are not synchronized
- Both iterators are fail-test. Thas is, if they detect any structural change they will throw an error.
- Both allow Null
- Both allow duplication
- Both are internally implemented using an Array
- Both get method take O(1)
Dissimilarities
- HashMap implements Map interface
- ArrayList Implements List interface
- HashMap stores two objects - key and value
- ArrayList stores only a value
- Keys of HashMap must implement equal and hasCode methods.
- ArrayList does not have to but it’s recommended it to have equal method because its contain method uses it.
- HashMap doesn’t support ordering
- ArrayList supports ordering
- HashMap doesn’t allow key duplicates
- ArrayList get() is always O(1). HashMap is O(n) in the worstcase.
What’s the difference between Set, List and Map?
These are interfaces
- List - ordered, indexed, duplicates
- Set - unordered, no duplicates
- Map - unordered, duplicates only with values.
When to use
- List - we need order and duplicates and it’s find for us to search using an index.
- Set - we don’t want duplicates
- Map - we want to find elements using a key. For instance, looking for a student using its ID
What’s the difference between an HashMap and HashTable?
Similarities
- Both implement Map Interface
- Both work on the principal of Hashing
- Both satisfy put and get in O(1) if objects are distributed uniformly
- They are part of the Collection framework
Dissimilarities
- HashMap is not thread-safe. HashTable is
- Since HashMap is not thread-safe, it outperforms HashTable.
- HashTable is obsolete. ConcurrentHashMap is better
HashMap and ConcurrentHashMap differences.
- HasMap is not thread-safe. CHashMap is.
- We can make HashMap synchronized by wrapping it with Collections.synchornizedMap(HashMap) which returns a Collection almost equivalent to HashTable. That is, every modification follows a lock of the Map object. On the other hand, ConcurrentHashMap divides the map and locks only parts of it. It is less safe, but of better performance.
- With single threaded both are comparable while HashMap is slightly better
What is Scalability?
An application has good scalability if it can maintain its performance while its volume of data or requests increase.
What’s the difference between HashTable, Concurrent HashMap and ConcurrentHashMap?
- HashTable locks the Map on iteration which causes a degrade on performance when data is large. ConcurrentHashMap uses segmentation. How large it becomes only parts of it are locked while readers can access the other parts.
- ConcurrentHashMap does not allow null values.
Differences between HashMap and LinkedHashMap
- Both are similar in performance
- LinkedHashMap extends HashMap
- LinkedHashMap maintains an order. Default is order by insertion though by access is also optional.
- Access order is of course affected by the methods get, put and putall. When an entry is accessed it moves towards the end of the doubly Linked list. It is used to implement an LRU cache.
It is a good compromise between HashMap and TreeMap. With TreeMap we get increased cost of iteration due to sorting and performance drops to log(n). With LinkedHashMap time is constant.
Differences between HashMap and TreeMap
- TreeMap maintains by default a natural increasing order over the keys, though it is possible to define a comparator. We can use methods that will sort from a given name A to a given name Y(at attahed)
*
Describe the SortedSet interface
Extends Set interface to handle sorted sets in ascending order.
important methods:
- headSet(Object start) - all elements <= start
- tailSet(Object end) - all elements >= end
- subSet(Object start, Object end) - all between
What’s the purpose of the Map.Entry interface?
I have a Map and i want to recieve a set of the combined object <key> to get information about and possibly change.</key>
- The method entrySet() returns a set of object of this type.
- methods:
- getValue
- getKey
- setValue
- compare
- hashCode
