CS 2150 Lecture Notes - Lecture 12: Abstract Data Type, Double Hashing, Linked List
18 Feb 2016
School
Department
Course
Professor
Document Summary
Lecture 12: hashing and hash tables: adts so far, lists: three main operations for any abstract data structure are find, insert, and remove, running times. If we want a lot of find kth, use an array but if you want to insert a lot of items, use a linked list because it"s constant time due to arrays having to adjust in size. 1: list implementation: array, list implementation: linked list. Insert: o(n) or o(1: find: o(n) b, remove: o(n, find kth: o(1, find: o(n) b. Key-value pairs: if you are looking for the word set in a dictionary, many definitions are going to be returned: hash tables. Hash function is specifically designed to take in a thing and returns an integer that is in the range of the table. Keys are stored in the array by their hash function. Properties: must be deterministic, must return same value for same thing.
