CMSC 132A Lecture 29: A new Data Structure, the Hash table
9 May 2018
School
Department
Course
Professor
CMSC132A Lecture 29: A new Data Structure, the Hash table
Today we will be exploring a new data structure similar to a map.
We are talking about the hash table. It is a mutable data structure. We will mutate the
object when we add a key-value association to it.
//Hashtable to map Key k to Value v
Interface HT<K,V>{
//look up the value associated with k
Optional<V> get(K k);
//EFFECT: update the table to map k to v
//produces the previous value mapped to k if any
Optional<V> put(K k, V v):
}
Void testHTList(tester.Tester t){
HT<Integer, String> ht = new HTList<Integer, String>();
t.checkExpect(ht.get(0).isPresent(), false);
ht.put(0, “zero”);
t.checkExpect(ht.get(0).isPresent(), true);
t.checkExpect(ht.get(0).get(), “zero”);
t.checkExpect(ht.put(0, “nil”).get(), “zero”);
t.checkExpect(ht.get(0).isPresent(), true);
t.checkExpect(ht.get(0).get(), “nil”);
}
We have just updated the table’s value from zero to nil.
Document Summary
Cmsc132a lecture 29: a new data structure, the hash table. Today we will be exploring a new data structure similar to a map. We will mutate the object when we add a key-value association to it. //hashtable to map key k to value v. //effect: update the table to map k to v. //produces the previous value mapped to k if any. Ht ht = new htlist(); t. checkexpect(ht. get(0). ispresent(), false); ht. put(0, zero ); t. checkexpect(ht. get(0). ispresent(), true); t. checkexpect(ht. get(0). get(), zero ); t. checkexpect(ht. put(0, nil ). get(), zero ); t. checkexpect(ht. get(0). ispresent(), true); t. checkexpect(ht. get(0). get(), nil ); We have just updated the table"s value from zero to nil. Let"s talk about get operation in the hash table it has a linear cost. If we have a million put statements, it will take a million units of time. It has this property that if you want to jump to the middle of the list, it is constant time to do so.
