We process these keys via a hash function and the result we get from that is basically the location of the bucket where we store our data. Unlike a direct address table where we take the key as indices of the address table, we use keys in different way. It cannot handle the case where two keys are equal and contain different data.ĭirect addressing has serious disadvantages, making it not suitable for the practical usage of current world scenarios, which is why we make use of Hash Tables. It is not recommended using the direct address table if the key values are very large. Searching in O(1) time: Searching an element takes linear time ( O(1)) as we can easily access an element in an array in linear time if we already know the index of that element. Insertion in O(1) time : Inserting an element in a direct address table is the same as inserting an element in an array, hence we can do that in O(1) time as we already know the index(via key).ĭeletion in O(1) time: Deleting an element from a direct address table is the same as deleting from an array, hence the O(1) time. Though direct addressing does facilitate fast searching, fast inserting and fast deletion operations, but at a cost.Ĭonsider the pictorial representation below: It uses the keys as indexes of the buckets and then store the values at those bucket locations. It is a technique in which we make use of direct address tables to map the values with their keys. The size of the array should be set accordingly to the number of key-value pairs we will have. The array(buckets) are used to hold the key-value pairs. we should be able to get the hash value from the key and not vice versa.Īlso, it should avoid producing the same hash for different keys. It is always recommended that we should choose a good hash function for creating a good hash table.īesides a good hash function, it should be a one-way function, i.e. Internally a hash table contains buckets, and the location of which bucket to use for a particular key is determined by the key's hash function.Ĭonsider the visual representation below:Ī hash table comprises two components in total, these are: Hash function:Ī hash function is used to determine the index of the key-value pair. The resulting value we get after the operation is the index of the hash table where we store the key-value pairs in the table. The key present in the hash table are used to index the values, as we take this key and pass it to a hash function which in turn performs some arithmetic operation on it. A Hash table is a data structure that is used to store the data in key-value pairs.Įach key in the hash table is mapped to a value that is present in the hash table.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |