Flashcards
Maps
Cards in this deck (13)
- 1define a map
- 2name the Map ADT operationsput(key, value)--returns the previous value is there was already that key, else null
get(key)--returns the value else null
remove(key)--returns the value if the key was present, else null - 3What data structure to use and when?arraylist or a linked list
if the keys are comparable, binary search tree or sorted arraylist
not a heap.
for small integer values k, array to access in O(1) - 4String.hashCode()
- 5define hashingwe need to define a function — called a hash function — that maps the keys to the range 0; 1;... ;m-1. Then, we will put the two maps together: the hash function maps from keys to a small range of integer values, and from this small range of integer values to the corresponding values v.
- 6define hash function
- 7define collisionsit can happen that two keys k1 and k2 map to the same hash value.
two keys might have the same hash code, or two keys might have different hash codes, but these two different hash codes map (compress) to the same hash value. - 8how to allow for collisions?Use a linked list of pairs (k; v) at each slot of our array. These linked lists are called buckets.
Then we examine each entry (k; v) in the linked list and check if the search key equals the key in that entry. - 9what's a good hash function?If possible, there is at most one pair per bucket. This is only possible if the number of entries in the hash map is less than or equal to the number of buckets. We define the load factor of a hash map to be the number of entries (k; v) in the map divided by the number of slots in the array (m). A load factor that is slightly less than one is recommended for good performance.
- 10worst case of hash functionall the keys in the collection hash to the same bucket, and then we would have one linked list only and access is O(n)
- 11define HashMap classclass implements the hash map that we have been describing. The hashCode() method for the key class K is composed with the “mod m" (and absolute value) compression function where m is the capacity of an underlying array, and it is an array of linked lists.
linked lists hold (K,V) pairs.
In Java, the default maximum load factor for the hash map is than 0,75 and there is a default array capacity as well. - 12define hashCode() and equals()Bottom line: if you write a class which uses the hashCode() method and you want to override either the Object class'es hashCode() or equals() methods, then you should ensure this: if k1.equals(k2) returns true or false, then k1.hashCode() == k2.hashCode() should return true of false, respectively. This may require that you override both of them.
- 13define HashSet classsimilar to a HashMap except that it only holds objects of type , not key/value pairs. It uses the hashCode() method of the type T
implements the Set interface
Information
- Description
- Computer Science Flashcards on Maps, created by Virginie Gagné on 15/04/2022.
- Created by
- Virginie Gagné
- Views
- 1
- Rating