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 uniform distribution of hash values. This means that every value has an equal probability of being generated. ● minimise clustering; this will arise when many different keys produce the same hash value. Where two or more different keys produce the same hash value, we say a ‘collision’ has occurred. ● be very fast to compute. 3 Implementing the hash table Like what we have learnt under data structures, we need to be able to perform CRUD -Create, Read, Update and Delete operations. 3.1 Defining a hash function A Hash Function is a function that converts a given numeric or alphanumeric key to a small practical integer value such that the value can be used as the index to access the hash table directly. An example of a simple hashing function that gives addresses between 0 and n is shown below: FUNCTION hash (key) RETURNS INTEGER // generate address using modulo operator address key MOD (n + 1) RETURN address ENDFUNCTION 3

VJC/H2Computing/9569 Let’s use customer records as an example to illustrate calculating addresses in a hash table. Assume we want to store customer records into a 1D array hash table and each customer has a unique customer ID, an integer in the range 10001 to 99999. For illustrative purposes, let n be 9. The hashing function will be: index customerID MOD 10 Customer IDs to store are in this sequence: 45876 , 32390 and 95312 Using the hashing function, 45876 will give an index 6 , 32390 will give an index 0 and 95312 will give an index 2 . The customer IDs are then stored in the hash table using the index calculated from the hashing function. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 32390 95312 45876 4

VJC/H2Computing/9569 3.2 Implementing insert, search and delete functions An insertion into the table can be easily performed as follows: PROCEDURE insert (data) // hash function returns the address to insert data index hash (key of data) hashtable[index] data ENDPROCEDURE One can search for the data in the hashtable using the following algorithm: FUNCTION search (data) RETURNS INTEGER // Returns index of data if found // Else return -1 if not found index hash (key of data) IF hashtable[index] = data THEN OUTPUT 'Data found at index ', index RETURN index ELSE OUTPUT 'Data not found in hashtable.' RETURN -1 ENDIF ENDFUNCTION Similarly, the pseudocode for the deletion operation is as follows: FUNCTION delete (data) RETURNS BOOLEAN // Deletes data and return True if data found in hashtable // Else return False if data not found Index hash (key of data) IF hashtable[index] = data THEN Delete data from hashtable[index] RETURN TRUE ENDIF RETURN FALSE ENDFUNCTION The average complexity to search, insert, and delete data in a hash table is O(1) — a constant time. It means that, on average, a single hash table lookup is sufficient to find the desired data. 5

VJC/H2Computing/9569 4 Handling collisions Finding a hashing function that will give a unique address from a unique key value is very difficult. Collisions happen when two (or more) different key values hash to the same address. There are two ways to handle collisions: 1) Closed addressing 2) Open addressing 4.1 Closed addressing For Closed Addressing, the data is always stored in the same position it is hashed to. Collisions are dealt with using separate data structures to store all the data at the calculated address. One way to implement this is the use the idea of separate chaining . Separate chaining can be implemented using linked lists. When multiple elements are hashed to the same index of the hash table, these elements are inserted into a singly-linked list which is known as a chain. Using the previous example of storing customer IDs, supposed we want to store one more customer ID 64636 , which will give an index of 6 using the hashing function, this will cause a collision with the previous customer ID 45876 already stored at index 6 . The diagram below shows an illustration of close addressing using separate chaining implementation. 6

VJC/H2Computing/9569 4.2 Open add