WK 6 Hashing + Map

What is the internal structure of a HashSet?

An array of buckets containing lists of hashes

How does the HashSet add() method work? (4 steps)

Calls hashCode() on the value, calculate bucket index, check for duplicates, if none then add

HashSets can have duplicate values (t/f)

False

In hashSets, how do you calculate bucket index?

hash%arrayLength

What is the internal structure of hashMap?

An array of buckets where each bucket stores key-value pairs, where only the key is hashed

In a hashMap, which part of the key-value pair gets hashed?

key

If a.equals(b) is true, then a.hashCode() == b.hashCode() must also be true. (t/f)

true

Hashing transforms ___ search into ___ lookup (Big-O notation)

O(n), O(1)

Hashset stores ___________, while hashmap stores ___________

unique values, key-value pairs

How do hashsets/hashmaps handle collisions?

Chaining

Every java object has a hashCode() method which returns a ____________ which represents it.

32-bit integer

Custom objects need to override hashCode() if they override equals(), otherwise they will break in hashsets/hashmaps (t/f)

true

Hashset/hashmap has O(1) time complexity for most common functions, but it doesn’t have ________, _________, and doesn’t allow ___________.

order, index, duplicates

After adding objects to the hashset/hashmap you can still modify them. (t/f)

false

What is a real-world example of hashing methods?

Libraries, phonebooks