CSE 214 Lecture Notes - Lecture 77: Hash Table, Double Hashing, Linear Probing
28 Nov 2016
School
Department
Course
Professor
Document Summary
Data records are stored in a hash table. Position of a data record in the has table is determined by its key. A hash function maps the keys to positions in the hash table. If a has function has 2 keys in the same position, a collision occurs. Key k is a string(or object) k. hashcode() % tablesize. During insert of key k to position p. If position p contains a different key, check p+1 etc. If position p contains a different key then do p+1, p+4, p+9. Load factor of a hash table is given by the formula. = number of elements in a table/size of table. If a key is removed , leave the boolean value set at true so we can search past it. If hash table is full, it costs a lot to resize and rehash every single object. Return several digits in the middle of the result. Multiply the integer by a constant less than 1.
