COMPSCI 61B Lecture Notes - Lecture 23: Pigeonhole Principle, Linked List
28 Aug 2017
School
Department
Course
Professor
Document Summary
Approach two: use whole string (base 27 number) How do we convert arbitrary data to an index: hashcode. Pigeonhole principle: if you have more items than boxes, multiple items will share the same box. External (separate) chaining: storing all items that map to h in a linked list. If n items are distributed across m buckets, average time grows with n/m = l, also known as the load factor. [note] x % y is not absolute value mod; use math. oormod(x, y) Every item is mapped to a bucket number using a hash function. Typically, computing hash function consists of two steps: Computing a hashcode (integer between -2^31 and 2^31 - 1) Resolve ambiguity when multiple items map to the same bucket. External chaining (creating a list for each bucket) Java"s actual hashcode() function for strings: h(s) = s0 * 31^n-1 + s1 * 31^n-2 + + sn-1.
