A hash table is a data structure that can implement a function whose domain is a finite set. An element of the domain is called a key. The hash table stores the key-value pairs in such a way that when presented with a key, the corresponding value can be quickly recovered.

We use the operator # to obtain values from the phone book.

The operator #? can be used to tell us whether a given key has an entry in the hash table.

We have implemented the notion of set via hash tables in which every value is the number 1.

There is a type of hash table that is mutable, i.e., a hash table whose entries can be changed. They are changed with assignment statements of the form `x#key=value`.

When a mutable hash table is printed, its contents are not displayed. This prevents infinite loops in printing routines.

Use peek to see the contents of a mutable hash table.

A variant of # is .. It takes only global symbols as keys, and ignores their values.

A dictionary could be implemented as a hash table: the keys would be the words in the language, and the values could be the definitions of the words.

A phone book could also be implemented as a hash table: the keys would be the names of the subscribers, and the values could be the corresponding phone numbers. (We exclude the possibility of two subscribers with the same name.)

As an example we implement a phone book.

i1 : book = new HashTable from { "Joe" => "344-5567", "Sarah" => "567-4223", "John" => "322-1456"} o1 = HashTable{Joe => 344-5567 } John => 322-1456 Sarah => 567-4223 o1 : HashTable |

i2 : book#"Sarah" o2 = 567-4223 |

i3 : book#?"Mary" o3 = false |

i4 : x = set {a,b,c,r,t} o4 = set {a, b, c, r, t} o4 : Set |

i5 : peek x o5 = Set{a => 1} b => 1 c => 1 r => 1 t => 1 |

i6 : x#?a o6 = true |

i7 : x#?4 o7 = false |

i8 : x = new MutableHashTable; |

i9 : x#"Joe" = "344-5567"; |

i10 : x#3 = {a,b,c}; |

i11 : x#{1,2} = 44; |

i12 : x#3 o12 = {a, b, c} o12 : List |

i13 : x#?4 o13 = false |

i14 : x o14 = MutableHashTable{...3...} o14 : MutableHashTable |

i15 : peek x o15 = MutableHashTable{{1, 2} => 44 } 3 => {a, b, c} Joe => 344-5567 |

i16 : p=4; |

i17 : x.p = 444; |

i18 : x.p o18 = 444 |

i19 : x#?4 o19 = false |

- copy -- copy an object
- hashTable -- make a hash table
- keys -- keys used in a hash table
- values -- values in a hash table
- pairs -- list the pairs in a hash table, dictionary, or basic list
- mutable -- whether something may be modified
- remove -- remove an entry from a mutable hash table
- applyKeys -- apply a function to each key in a hash table
- applyValues -- apply a function to each value in a hash table
- applyPairs -- apply a function to each pair in a hash table
- merge -- merge two hash tables
- combine -- combine hash tables

- hashing
- HashTable -- the class of all hash tables
- MutableHashTable -- the class of all mutable hash tables