4.2.6 Hash Tables

What is a hash table?

Data structure that creates a mapping between keys and values

What is a hashing algorithm?

An algorithm which takes an input and returns an unique hash which cannot be reversed

How are elements looked up in a hash table?

- Key is hashed

- Corresponding hash is queried

- Desired information is located

What is a collision?

When a hashing algorithm generates the same address for two different keys

How can collisions be resolved?

• Placing the item in the next address

• Implementation of a skip value

How can errors be avoided?

• Ensure that the load factor is not greater than about 50-70% of the table size

• Using a prime number as the table size

What are the three key hashing algorithms?

• Mid-square

• Folding

• Mod

How does the mid-square method work?

• Square the item

• Extract the middle of the resulting digits

• Hash = result MOD number of addresses

How does the folding method work?

• Divide item into equal pieces

• Sum pieces together

• MOD by table size

How can alphanumeric data be hashed?

• Convert with ASCII code

• Apply hashing algorithm