CMPT 225 Lecture Notes - Perfect Hash Function, Hash Table, Prime Number
4 Sep 2013
School
Department
Course
Professor
Document Summary
Data needs to be accessed really really quickly, but does not have to be maintained in order. Order is not important, don"t care about adjacent values or anything. Don"t want to print out a bunch of stuff in order. Balanced bst - but maintain data in order, which we don"t care about or need. Arrays - if we know index of data, lookup can be performed in constant time. Sum the letters not very good for that. Multiple letter"s value by 26^i, which is position of letter in word. Then sum letters dog = 4*26^2 + 15*26^1 + 7*26^0 = 3101. Vast majority are random letters showed together and are not actually people"s names. Not practical to create an array large enough to store all possible strings. But we want an array to take advantage of constant time lookup! Fix array size based on amount of data actually want to store. Map key value to int index for array.
