Hashtables

Question 1

a bad example of a way to hash phone numbers

Answer 1

using the first three digits

Question 2

a good example of a way to hash phone numbers

Answer 2

last three deigits

Question 3

what does the hashCode() method return

Answer 3

an int

Question 4

what is an equality requirement of hash function

Answer 4

x.equals(y)

then x.hashCode() == y.hashCode()

Question 5

what is highly desirable when it comes to equality and the hashCode() function

Answer 5

if !x.equals(y)
then
x.hashCode != y.hashCode()

Question 6

what is the deafault implementation of hashCode

Answer 6

using memory address of the object

Question 7

if a null object is sent into the hashCode function what should be returned

Answer 7

0

Question 8

if an array is sent into the hashCode function how is it hashed

Answer 8

each array entry is hashed

Question 9

the int returned must be between

Answer 9

-2^31 and 2^31 -1

Question 10

how to convert if the key is not in the range

Answer 10

get abs value

Question 11

what is the uniform hashing assumption

Answer 11

each key is equally likely to has to an integer between 0 and M-1

Question 12

after how many insertions do we expect two keys in the same index

Answer 12

sq root (pi*M /2)

Question 13

how many keys do we need to put in for all the indexes to be used

Answer 13

MlgM insertions

Question 14

what do we expect the height of the most loaded index to ve

Answer 14

logM / loglogM

Question 15

two methods for dealing with collisions

Answer 15

linear probing

separate chaining

Question 16

what is a collision

Answer 16

when two keys hash at the same index

Question 17

what is the separate chaining approach to dealing with collisions

Answer 17

have a linked list in every index of the array

Question 18

when keys are inserted in the linked list implementation, where are they inserted, at the head or tail

Answer 18

head

Question 19

what is the cost of inserting at the head of the linked list

Answer 19

constant

Question 20

how to search for key in separate chaining approach

Answer 20

go to hash index

search through linked list

Question 21

worst case search using linked list approach

Answer 21

length of linked list

searches every node in the list

Question 22

what will the length of the longest linked list be

Answer 22

logM / loglogM

Question 23

if the number of indexes is too large in comparison to the number of items we want to hash, what is the problem

Answer 23

too many empty chains

Question 24

if the number of indexes is too small in comparison to the number of items we want to hash, what is the problem

Answer 24

chains are too long

Question 25

what is the best ratio of items to indexes for best run time

Answer 25

items/indexes = 4

Question 26

when should the hash array be resized in separate chaining

Answer 26

doubled when n/m >= 8

halved when n/m <= 2

remember to rehash all keys when resizinf

Question 27

how do delete a key in separate chaining hash table

Answer 27

delete key from linked list

Question 28

what is linear probing also known as

Answer 28

open addressing

Question 29

how does linear probing work

Answer 29

when a key collides, find the next empty slot and put it in there

Question 30

how does search work in linear probing

Answer 30

search where the hash index is, if not there try the next and so on

Question 31

why is clustering common in linear probing

Answer 31

new keys are likely to be added in clusters as it will continuosly try the next space until a free one is found

Question 32

what is a requirement to use the linear probing algorithms

Answer 32

must always be one emmpty slot in the table

Question 33

which is better
many small clusters
few larger clustesr

Answer 33

many small clusters as searching will take less time if a blank space is found sooner

Question 34

on average how many indexes must you move to find the next empty space when the array is half full

Answer 34

M/2 spaces

Question 35

on average how many indexes must you move to find the next empty space when the array is full

Answer 35

M spaces

Question 36

if the number of indexes in the array in linear probing is too large why is this bad

Answer 36

takes up too much space

Question 37

resizing array parameters for linear probing

Answer 37

double when n/m > 1/2

halve when n.m < 1/4

Question 38

how to delete keys in linear probing hash table

Answer 38

delete and rehash everything after

Question 39

why must everything after be rehashed when deleting from a linear probing array

Answer 39

it will break the search function if there is an empty space

Question 40

what is the worst case scenario of linear probing

Answer 40

all the values are in one big cluster

Question 41

why is security often talked about with hash tables

Answer 41

values can be chosen in a way that keys will be added to the same index of the array, or same cluster, grinding performance to a halt

Question 42

why is hashing used

Answer 42

to distribute entries uniformly across an array

Question 43

by using the key to search for an element, what is the runtime of such a sprt

Answer 43

constant run time

Question 44

what are the values returned from a hash function called

Answer 44

hash values
hash codes
hashes

Question 45

what three things are we looking for from a hash function

Answer 45

easy to compute (should not be a huge algorithm in itself)

uniform distribution across hash table

as little collisions as possible

Question 46

uses of hash tables

Answer 46

database indexing