Data Structures > Data Structures 1 > Flashcards

Data Structures 1 Flashcards

(91 cards)

Study These Flashcards
1
Q

What is the goal of Hashing?

A

Do faster than O(LogN) time complexity for: lookup, insert, and remove operations. To achieve O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What kind of Collection is Hashing?

A

value-orientated.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How does Hashing work?

A
  1. you have a key for the item.2. the item’s key gets churned within the hash function to form the Hash index.3. The hash index can be applied to the data array, and so, the specific data is found.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

hash Table:

A

An array that stores a collection of items.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Table Size(TS)

A

The Array’s Length

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Load Factor (LF)

A

Number of items/Table size. For instance, a load factor of 1 = 100% of the items are used.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Key

A

Information in items that is used to determine where the item goes into the table.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Hash Function

A

A function that takes in the key to compute a specific Hash Index.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What would the Perfect Hash Function be?

A

Each Key maps to an unique Hash Index.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How do you delete a value within the hash table?

A

You just set Table[hash(Key)] = null

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How do you look up a value within the hash table?

A

return Table[Hash(key)];

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How do you insert a value within the hash table?

A

Table[Hash(key)]=data;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the worst case time complexity for: Insert, lookup, and delete, for hash functions?

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

If we have UW-Madison student ID’s, and we wanted the ideal hash functions, how would we do it, and why would there be a problem

A

-> We’d simply count each one as an index-> Hash table would be huge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Collisions:

A

When the Hash Function returns the same index for different keys.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Good Hash Function qualities:

A
  1. Must be deterministic:-> Key must ALWAYS generate the same Hash Index (excluding rehashing).2. Must achieve uniformity-> Keys should be distributed evenly across hash table.3. FAST/EASY to compute-> only use parts of the key that DISTINGUISH THE ITEMS FROM EACH OTHER4. Minimize collisions:
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Extraction:

A

Breaking keys into parts and using the parts that uniquely identify with the item. 379452 = 394121267 = 112

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Folding:

A

Combining parts of the key using operations like + and bitwise operations such as exclusive or.Key: 123456789 123 456 789 — 1368 ( 1 is discarded)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Weighting:

A

Emphasizing some parts of the key over another.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Compressing:

A

Ensuring the hash code is a valid index for the table size.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

The more items a table can hold, the () likely a collision will happen.

A

less

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Load Factor

A

Approximately how it’s full… 0.7-0.8.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Why do we use prime numbers for table size?

A

We mod often, and prime numbers give us the most unique numbers. (2*ts+1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Steps to resizing:

A
  1. Double table size to nearest prime number2. Re-hash items from old table into the new table.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Rehashing Complexity:
O(N)-- costly. Carefully select initial TS to avoid re-hashing.
26
Collesion handeling:
How you handle the collisions so each element in the hittable stores only one item.
27
Idea of probing:
If you have a collision, search somewhere else on the table.
28
Linear Probing:
Step size is 1. Find the index, and keep incrementing by one until you find a free space.
29
Quadratic Probing:
Probe Sequence is (Hk+1)^2.Minimizes clusteringbetter at distinguishing items across table.
30
Probe Hashing:
-> Hash it, and if it leads to a collision, use a separate equation to determine the step size and use that step size to find a new site.
31
Collision Hashing using Buckets
-Each element can solre than one item.-throw collisions into a bucket.-buckets aren't sorted.
32
Array Bucket
-- a bucket of arrays. -Fixed in size.-size of about 3 work usually well.
33
Chained bucket:
+--easy to implement+-- buckets can't overfill+-- buckets won't waste time.+-- buckets are dynamically sized.
34
Tree Buckets
+--WC = O(logN)+--no wasting space+--dynamically sized-- more complicated than what's needed. --> insert with dups= O(1)--> W/o dups = O(N)
35
HashCode Method:
-method of OBJECT class-Returns an int-default hash code is BAD-- computed from Object's memory address. --> must override
36
HashTable & HashMap class
java.utilimplements map interfaceK-- type paramater for key and v-- type parameter for associated valueOperations: lookup, insert, delete.Constructor lets you set init capacity and load factorhandles collisions with chained bucketshash map only allows null for keys and values
37
TreeMap underlying Structure:
RBT
38
Treemap complexity of basic operations:
O(logN)
39
TreeMap complexity for iterating over associated values:
O(N)
40
HashMap underlying structure:
HashTable with chained buckets
41
HashMap complexity of basic operations:
O(1)
42
Complexity for iterating over associated values:
O(T.S + N) --> worst case.
43
data structure
a particular scheme organizing related data items.
44
linked list
A sequence of zero or more nodes containing some data and pointers to other nodes of the list.
45
list
a collection of data items arranged in a certain linear order
46
stack
LIFO list in which insertions/deletions are only done at one end.
47
queue
FIFO list in which elements are added from one end of the structure and deleted from the other end.
48
priority queue
collection of data items from a totally ordered universe
49
graph (formal)
G = (V,E). V: finite, nonempty set of vertices. E: set of pairs of V, called edges.
50
If a graph's edges are unordered [ (u,v) == (v,u)], then the vertices u and v are
adjacent
51
If a graph's edges are unordered [ (u,v) == (v,u)], then the vertices u and v are connected by
an undirected edge (u,v).
52
The vertices u and v of the undirected edge(u,v) are the _ of the edge
endpoints
53
The vertices u and v of the undirected edge(u,v) are _ to the edge
incident
54
A graph is undirected if
every edge in it is undirected.
55
If a graph's edges are ordered [ (u,v) != (v,u)], then the edge (u,v) is _ from _ to _
directed from u to v
56
digraph
A graph whose every edge is directed
57
for the directed edge (u,v), u is the _ and v is the _
u is the tail, v is the head.
58
complete graph
a graph with every pair of its vertices connected by an edge
59
dense graph
A graph with very few possible edges missing
60
sparse graph
A graph with few edges relative to the number of vertices
61
weighted graph
A graph with numbers assigned to its edges.
62
weight/cost matrix
Adjacency matrix of a weighted graph.
63
A path from vertex u to vertex v
a sequence of adjacent vertices that starts with u and ends with v
64
simple path
A path in which all vertices are distinct
65
length of a path
The total number of vertices in the vertex sequence defining the path - 1.
66
directed path
A sequence of vertices (v1,v2,v3,...) such that v1->v2, v2->v3,v3->... for a directed graph.
67
connected graph
A graph such that for all vertices u and v, there exists a path from u to v.
68
cycle
A path of positive length that starts and ends at the same vertex and does not traverse the same edge more than once.
69
acyclic graph
A graph with no cycles.
70
tree
A connected, acyclic graph
71
forest
A graph that has no cycles, but not necessarily connected
72
The number of edges in a tree
One less than the number of vertices
73
Q: For every vertices u, v in a tree, there exists:
A: Exactly one simple path from u to v.
74
tree root
top level vertex
75
Ancestors of a vertex v in a tree
All vertices on the simple path from the root to v
76
Proper ancestors of a vertex v in a tree
All vertices on the simple path from the root to v, but excluding v itself.
77
if (u,v) is the last edge of the simple path from the root to vertex v, u is the _ of v
parent
78
if (u,v) is the last edge of the simple path from the root to vertex v, v is the _ of u
child
79
siblings
Vertices of a tree that have the same parent.
80
leaf
A vertex with no children
81
parental
A vertex with at least one child
82
descendants of v
All vertices for which v is an ancestor in a tree
83
subtree of T rooted at v
All descendants of a vertex v
84
proper descendants
All vertices for which v is an ancestor in a tree, excluding v itself.
85
depth of a vertex v
The length of the simple path from the root to v
86
height of a tree
the length of the longest simple path from the root to a leaf
87
ordered tree
A rooted tree in which all children of each vertex are ordered. (Usually left to right)
88
binary tree
An ordered tree in which every vertex has no more than two children, with each child designated as a left or right child. Potentially empty.
89
binary search tree
A binary tree with the property that for all parent nodes, the left subtree contains only values less than the parent, and the right subtree contains only values greater than the parent.
90
first child-next sibling representation
Representation used for ordered trees with a potentially varying amount of children per parent node.
91
set
An unordered collection (possibly empty) of distinct items called elements of the set.
Data Structures
flashcards
Decks in class (14)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions