1	Hash Tables Chapter 11 discusses several ways of storing information in an array, and later searching for the information. Hash tables are a common approach to the storing/searching problem. This presentation introduces hash tables.
2	What is a Hash Table ? The simplest kind of hash table is an array of records. This example has 701 records.
3	What is a Hash Table ? Each record has a special field, called its key. In this example, the key is a long integer field called Number.
4	What is a Hash Table ? The number might be a person's identification number, and the rest of the record has information about the person.
5	What is a Hash Table ? When a hash table is in use, some spots contain valid records, and other spots are "empty".
6	Inserting a New Record In order to insert a new record, the key must somehow be converted to an array index. The index is called the hash value of the key.
7	Inserting a New Record Typical way create a hash value:
8	Inserting a New Record Typical way to create a hash value:
9	Inserting a New Record The hash value is used for the location of the new record.
10	Inserting a New Record The hash value is used for the location of the new record.
11	Collisions Here is another new record to insert, with a hash value of 2.
12	Collisions This is called a collision, because there is already another valid record at [2].
13	Collisions This is called a collision, because there is already another valid record at [2].
14	Collisions This is called a collision, because there is already another valid record at [2].
15	Collisions This is called a collision, because there is already another valid record at [2].
16	A Quiz Where would you be placed in this table, if there is no collision? Use your social security number or some other favorite number.
17	Searching for a Key The data that's attached to a key can be found fairly quickly.
18	Searching for a Key Calculate the hash value. Check that location of the array for the key.
19	Searching for a Key Keep moving forward until you find the key, or you reach an empty spot.
20	Searching for a Key Keep moving forward until you find the key, or you reach an empty spot.
21	Searching for a Key Keep moving forward until you find the key, or you reach an empty spot.
22	Searching for a Key When the item is found, the information can be copied to the necessary location.
23	Deleting a Record Records may also be deleted from a hash table.
24	Deleting a Record Records may also be deleted from a hash table. But the location must not be left as an ordinary "empty spot" since that could interfere with searches.
25	Deleting a Record Records may also be deleted from a hash table. But the location must not be left as an ordinary "empty spot" since that could interfere with searches. The location must be marked in some special way so that a search can tell that the spot used to have something in it.
26	Summary Hash tables store a collection of records with keys. The location of a record depends on the hash value of the record's key. When a collision occurs, the next available location is used. Searching for a particular key is generally quick. When an item is deleted, the location must be marked in a special way, so that the searches know that the spot used to be used.
27
28
29
30
31
32	THE END