COMS W3134 Lecture Notes - Lecture 17: Hash Table, Linked List, Prime Number
13 Nov 2016
School
Department
Course
Professor
Document Summary
Announcements: can start on hw4 after this class. In object class, there exists a function called hashcode, this applies some sort of hash function to a java object. equals method works via hashcodes, should return true if hashed to the same value: secure hash functions vs insecure (reversible vs not-reversible) Insertion into hash table, reversibility isnt a problem: hash code for characters is ascii value for the character, no collisions. Integer or double or wrapper classes, hash code evaluates to underlying number. Big-o is o(n: load factor is ratio of number of elements in table to table size. Have to move to another location in a predictible manner: probing schemes: gives multiple locations that a particular value could appear in. For insert method, want a series of locations h# , h" , are a set of probes that are applied, if h# isn"t free then move to h" , etc.
