VJC Chapter 16 Hash Table

VJC/H2Computing/9569 Chapter 16 Hash Table Contents 1 Introduction to Hash table 2 Components of a hash table 3 Implementing the hash table 3.1 Defining a hash function 3.2 Implementing insert, search and delete functions 4 Handling collisions 4.1 Closed addressing 4.2 Open addressing 4.3 Comparisons Between Open and Closed Addressing 4.3.1 Advantages and Disadvantages of Closed Addressing 4.3.2 Advantages and Disadvantages of Open Addressing 5 Good Hash Table 5.1 Size of hash table 5.2 Good hash function Syllabus Learning Outcomes 1.2 Fundamental Algorithms 1.2.3 Implement search algorithms. – Linear search – Binary search – Hash table search 1.2.4 Use examples to explain search algorithms. 1.2.5 Compare and describe the efficiencies of the search algorithms using Big-O notation for time complexity (worst case). Exclude space complexity 2.3 Implementing Algorithms and Data Structures 2.3.2 Implement search programs. – Linear search – Binary search – Hash table search 1

VJC/H2Computing/9569 1 Introduction to Hash table A hash table is a data structure that store data in an array and have direct access to the records. An address (the array index) is calculated from the key value of the data and the data is then stored at this address in the array. To search for a data, the address is calculated from the key and we can look up the array using the calculated address to find the data. Calculating an address from a key is called hashing. A key, which could be part of the data item or the entire data item, is parsed into a hash function to generate an address/index/hash value, which points to a location in a table (array) where the data is stored. This enables the data to be accessed directly. The positions where data can be stored are sometimes known as buckets. 2

VJC/H2Computing/9569 2 Components of a hash table There are 2 components that we will need: 1. Hash table The hash table holds all the data entries in an array (implemented using a python list). The size of the array should be set according to the amount of data expected. 2. Hash function The hash function is an algorithm that converts a key to a value which is the address/index. Choosing an efficient hash function is a crucial part of creating a good hash table. The main requirements of a hash function are that it must: ● always produce the same hash value for the same key. ● provide a unif