CSCA48H3 Lecture Notes - Lecture 18: Init, Hash Table, Hash Function
17 Apr 2018
School
Department
Course
Professor
Document Summary
Csca48 - lecture 18 - hashing code + explanation. Hashing would provide an o(1), constant time search technique. Hash table: collection of items, where each position of the table is called a slot (numbered from 0 to m-1, where m is the size of the hash table) Hash function: maps item to slot -> h(item) = (item) % (m), where h(item) is the hash value (slot # ) of the item. Collision : two or more items technically belong in the same spot. Linear probing: look sequentially, slot by slot, until we find an open position. Rehashing: the process of looking for another slot after a collision -> rehash(pos) = (pos. + 1) % sizeoftable from week4_sll import * class hashtable(): """ a very basic hash table that stores integer numbers assuming that collision never happens!""" def __init__(self, n): """(hashtable, int) ->nonetype creates an empty list of length n""" self. _array = [none]*n self. _length = n.
