Final Flashcards
The classes that implement the _______ interface are all indexed collections
List
Set objects:
are not indexed do not reveal the order of insertion of items
Denable efficient search and retrieval of information
allow removal of elements without moving other elements around
Relative to a Set, Map objects provide efficient _____ and ______ of entries that contain pairs of objects (a unique key and the information)
search
retrieval
Hash tables (used to implement a Map or Set ) store objects at arbitrary locations and offer an average constant time for ______,_______,_______.
insertion, removal, and searching
is a collection that contains no duplicate elements and at most one null element
A set
Required methods for set interface and methods:
testing set ,
testing for an empty set,
determining set size,
creating an iterator over the set
Additional methods for adding an element and removing an element (the add method does not allow _________________ ).
duplicate items to be inserted
Constructors that enforce the “________________” rule
no duplicate members
Required method: __________ tests the subset relationship
containsAll
Union:
Intersection:
Difference:
addAll
retainAll
removeAll
Unlike the List.add method, the Set.add method returns false if you attempt to:
insert a duplicate item
Unlike a List, a Set does not have a ____ method elements cannot be accessed by index
get
You can iterate through all elements in a Set using an __________ object, but the elements will be accessed in arbitrary order
Iterator
Returns an iterator over the elements in this set.
iterator()
Collections implementing the ____ interface must contain unique elements
Set
Unlike the ______ method, the _____ method returns _____ if you attempt to insert a duplicate item
List.add. Set.add. false
Unlike a _____, a_____ does not have a ____ method-elements cannot be accessed by index
List. Set. get
You can iterate through all elements in a _____ using an ________ object , but the elements will be accessed in arbitrary order
Set. Iterator
The Map is related to the
Set
Mathematically , a _____ is a set of ordered pairs whose elements are known as the key and the value
Map
The collection of all keys is known as the
keySet
The collection of all values is known as the
valueSet
All the elements of ________ have a corresponding member in key Set
valueSet
The goal of hash table is to
be able to access an entry based on its key value, not its location
Using a hash table enables us to find elements
as quickly as possible
The basis of hashing is to transform the item’s key value into an _________________ which is then transformed into a table index
integer value (its hash code)
The hash function calculation is simply:
int index = asciiChar;
If you assume that on average 100 characters were used, you could use a table of 200 characters and compute the index by :
int index = uniChar % 200
If two hashcodes are the same indices this is called
A collision
To resolve collisions, ___________ can be used to store or access an item in a hash table
linear probing
another way of solving collisions:
Chaining
What is the calculations for load factor?
Load factor = number of filled cells / table size
What does load factor percentage tell us?
Performance
With load factor the lower it is the
better there performance as there is a smaller chance of collision
In hash tables, If there are no collisions, items can
be added or retrieved without searching, regardless of table size
With a hash table you cannot
traverse a hash table in a meaningful way since the sequence of stored values is arbitrary
Unlike lists, trees are ________ and
___________
nonlinear
hierarchical
Trees can represent hierarchical organizations of information:
class hierarchy disk directory and subdirectories
Trees can be defined and processed ___________
recursively
A binary tree consists of a collection of elements or nodes , with each node linked to _____________ successors
at most two
What is the root of a tree hierarchy?
The node at the top of the tree
The successors of a tree node called it’s
children
Each node in a tree has exactly _____ parent except for the root node which has no parent
one
node that has no children is called a
Leaf node
In recursive fashion, the child of a node is considered the root of a ________ of that node
subtree
Three common kinds of tree traversal
Inorder
Preorder
Postorder
In a preorder traversal the first node we visit is always
The root
In a postorder traversal the last node we visit is always
The root
In a binary search tree, all elements in the left subtree _________ those in the right subtree
Precede
A binary search tree is an “________” tree, which never has to be sorted because its elements always satisfy the “________” requirement
ordered
When new elements are inserted (or removed) properly, the binary search tree _________ its property
maintains
The TreeSet class implements the Set interface by storing elements in a
balanced Binary Search Tree
As elements are added to / removed from the TreeSet, the class may __________ nodes so that the tree remains balanced
rearrange
A class of objects added to a ________ must provide a way to “compare” objects
TreeSet
Given an object to be added to a TreeSet or TreeMap , we must be able to determine if the new object is
- Equal to the object at the root
- Less than the object at the root
- Greater than the object at the root
Therefore, the objects must be comparable
Classes (such as String) that implement the Comparable interface must define a ___________ method
compareTo
Method obji.compareTo (obj2) returns an integer with the following values
Negative if obj1 < obj2
Zero obj1=obj2
Positive if obj1>obj2
Implementing the __________ interface provides a way to compare objects during a search
Comparable
