CSE 274 Chapter Notes - Chapter 21: Hash Table, Hash Function, Array Data Structure
12 Nov 2018
School
Department
Course
Professor
Document Summary
Technique that determines index of an entry in an array using only the entry"s search key, without searching. This array is called a hash table. Hash function: takes search key and produces integer index of element in the hash table. Ideal hashing/perfect hash function example: a small town with telephone numbers all starting with 555 uses a hash function h to convert the telephone to its last four digits. This is then the index where the value will be stored, and in order to get this value, we can use the hash function again to get the index of the key and return it. This is an ideal hash function if every phone number in the town needs to be used, but if only 500 of the 10000 are used, it wastes a lot of space. Can develop different hash function that takes last four of phone number and finds the remainder with the table size.
