Dictionaries and Hash Tables

Question 1

What is a hash table?

Answer 1

A data structure that stores a key/value pair based on an index calculated from a hashing algorithm

Question 2

What is a collision in hash tables?

Answer 2

When two key values compute to the same hash value

Question 3

What are properties of good hash functions?

Answer 3

• Make use of all info provided by the key
• Uniformly distribute output across table to reduce clustering
• Maps similar keys to very different hash values
• Always give same hash value for a key
• Make use of only computationally fast operations
• Handle keys of any data type

Question 4

How can collisions be dealt with?

Answer 4

• (Rehashing)?
• Linear probing
• Seperate Chaining

Question 5

What is linear probing and what are its disadvantages?

Answer 5

• Look for the next available index in hash and insert item there
• However increases potential for further collisions and can promote clustering
• no known association between key and its location so linear search needs to be used to find item

Question 6

What is clustering in hash tables?

Answer 6

Nearby indexes are not randomly or evenly distributed

Question 7

What is separate chaining?

Answer 7

Storing a list at each location in the hash table, rather than single key value pairs.

When item is inserted into hash table, it is appended to the list stored at the location indicated by the hash value of the key.

Allows multiple key-value pairs to be stored at the same hash table index

Question 8

What is rehashing?

Answer 8

Process of increasing the size of a hash table and redistributing the elements to new indexes based on their new hash values

reduces likelihood of collisions as there are now more buckets/locations for key value pairs to be in

Question 9

What are the uses of hash tables?

Answer 9

• Databases: quick storage and retrieval of data based on primary keys
• Cache memory: determining the memory address for a given item of data
• Operating Systems: store locations of its programs and utilities for quick access
  (Encryption)

Question 10

How do hash tables work?

Answer 10

• When an item is added, its key is processed by a hashing algorithm that returns a hash value
• Items are placed in indexes specified by the hash value
• To search for an item, key is processed again and the resulting index is checked for the item, if it does not exist we can confidently say it is not in the table

Question 11

What are the advantages of using hash tables to store data?

Answer 11

• Faster to lookup a record
• Time complexity of O(1) for retrieval

Question 12

What are the advantages of storing data in a dictionary?

Answer 12

• More compact file as there are no empty records
• Produce a sorted list
• Do not have to design a hash algorithm so easier to design
• No need to deal with collisions

Question 13

How are records added to a hash table?

Answer 13

• Hashing algorithm is applied to a key
• Result is the location in the table where the record should be stored
• If location is not empty then use next free location

Question 14

Benefits of separate chaining over linear probing

Answer 14

You can keep adding items without causing clustering or increasing likelihood of collisions

Key value pairs can still be found in known locations - no need search whole table to find item

Question 15

Drawbacks of separate chaining

Answer 15

The appropriate list still needs to be linear searched when accessing an item

Question 16

When is rehashing performed

Answer 16

When a hash table load factor exceeds a predetermined load threshold.

The load factor is the ratio of stored key-value pairs to locations/buckets within the hash table.