Hash Tables: Storing and Searching

• This chapter discusses various methods for storing and searching information in an array.
• Hash tables are a common approach to solving storing/searching problems.

What is a Hash Table?

• The simplest kind of hash table is an array of records, this example has 701 records.
• Each record has a special field, called its key.
• In this example, the key is a long integer field called "Number".
• The number might be someone's identification number, and the remainder of the record includes details about the individual.
• When a hash table is in use, certain spots hold valid records, while others are "empty".

Inserting a New Record

• The key must be converted to an array index to insert a new record.
• The hash value of the key refers to the index.
• A typical method to create a hash value is: (Number mod 701).
• Hash value is used for the new record's location.

Collisions

• Collision occurs when a new record is being inserted, but the hash value of 2 already has a record in place.
• When a collision occurs, proceed forward until an empty spot is found.

Collision Resolution

• If an element hashes to the same value as one already inserted, a collision occurs and needs resolving.
• Several methods exist for dealing with collision resolution, for example:
  • Separate chaining
  • Open addressing

Collision Resolution with Separate Chaining

• The list of all elements that hash to the same value is kept as part of the idea.
• Array elements point to the lists' first nodes.
• Insertion of a new item is performed at the front of the list.
• Advantages include:
  • Superior space utilization for substantial items.
  • Simple handling of collisions by searching a linked list.
  • Overflow: It is possible to store more items than the hash table size.
  • Quick and easy deletion performed from the linked list.

Example

• Keys: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81
• hash(key) = key % 10

Collision Resolution with Open Addressing

• The disadvantage of using linked lists exists when separate chaining is used.
• Implementation of a second data structure is required.
• All data is stored inside the table with open addressing hashing.
• A bigger table is needed.
• Alternative cells will be used until an empty cell is available, if a collision happens.

Open Addressing - Searching for a Key

• Open addressing makes it fairly quick to find the data attached to a key.
• Begin by calculating the hash value.
• Determine the location of the key in the array.
• Keep moving forward if the key is not at the location until you find it, or you reach an empty spot.
• The information can be moved to the required area once the item has been located.

Deleting a Record

• Records can also be removed from a hash table.
• Because this may disrupt searches, the location cannot merely be left as an ordinary “empty spot."
• The location needs to be marked in a specific way so that searches can recognize that it once contained something.

Summary

• Hash tables store a collection of records with keys.
• A record's location depends on the hash value of its key.
• When a collision occurs, the next available location is utilized either by chaining, or by open addressing.
• In general, it is quick to look up a specific key.
• When an item is removed, the location needs to be marked in a specific way so that the searches are aware that the spot was formerly in use.