COMP 2402 Chapter Notes - Chapter 5: Hash Table, Linear Search, Open Addressing
27 Dec 2014
School
Department
Course
Professor
Document Summary
Hash tables are an efficient method of storing a small number of integers from a large range. When hash tables can store non-integer data types by associating an integer hash code with each item. Uses hashing with chaining to store data as an array, t, of lists. Integer n keeps track of the total number of items in all lists. The hash value of a data item x, denoted hash(x), is a value in the range [0,,t. length-1] All items with hash value i are stored in the list at t[i] n t. length so that lists don"t get too long. So the average # of elements stored in one of these lists is n/t. length 1. Add(x) - first check if the length of t" needs to be increased and if so grow it. Then hash x to get an integer i.
