EXAM Flashcards
What is a hash function?
A function that can be used to map data of arbitrary size to fixed-size values
What are 3 names for values returned by hash functions?
- Hash Values
- Hash Codes
- Digests
What are hash values used for?
Index fixed-size table
What is the table indexed by a hash function called?
Hash table
What is it called when you index a hash table?
Hashing or Scatter Storage Addressing
What is necessary to create a perfect hash function?
Table/map has to contain at least as many positions as number of elements being hashed
With hashing what is collision?
Non-unique keys being made
What are 5 types of hashing?
- Division
- Folding
- Mid-square function
- Extraction
- Radix Transformation
Which hashing method is preferred if little is known about the keys?
Division
What are 2 kinds of Folding with Hashing?
- Shift Folding
- Boundary Folding
What are 2 methods for reducing collissions?
- Increase size of table
- Changing the hash function
What is bucket addressing with hashing?
Each element in a hash table can hold multiple elements
What do Maps store?
Key Value Pairs
What are key value pairs called?
Entries
What is the difference between Maps and Dictionaries?
Maps must have unique keys, whereas dictionaries can have repeated keys
What is a set?
A collection of distinct objects
How are sets usually implemented?
Trees
In a tree, what node has no parents?
The Root
Which node has no children?
Leaves
What are the links between nodes in a tree called?
Edges/arcs
What is the length of a path in a tree?
The number of edges
What are the 2 categories of trees?
- Unordered
- Ordered
What makes a binary tree a binary search tree?
All nodes to the left of the root are <= the root
What is a red-black tree?
Self balancing search tree