CS 106B Lecture Notes - Lecture 22: Edward Snowden, Linear Search, Hash Function
16 Nov 2016
School
Department
Course
Professor
Document Summary
First idea: put everything in a gigantic vector. But sometimes two objects are assigned to the same index. Wiki stores using article ** data (an array of linked lists: first * is dynamic array, second * is for linked lists, hashmap algorithm summary. Make a large array of linked lists. Run linear search/ add to linked list. Jump directly to the bucket head: hash function template. Get a large number, then convert it to something within range of array. Add values of the characters of a string, then divide it by the number of buckets there are ( % num_buckets) If we weight each index by 31^i, we get an even distribution of elements within buckets. Get(function) if number of buckets is comparable to. Many applications of hashing number of elements is o(1: edward snowden told fbi to use hashing, which allowed them to read e-mails in seconds to minutes, shazam.
