From ce1f797f4af5aee2574a021fd24c0c7405870f45 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 9 Aug 2020 15:37:11 -0600 Subject: Start notes on open addressing --- doc/mit-ocw/hash.md | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) diff --git a/doc/mit-ocw/hash.md b/doc/mit-ocw/hash.md index f1aaa13..b38efcd 100644 --- a/doc/mit-ocw/hash.md +++ b/doc/mit-ocw/hash.md @@ -159,4 +159,68 @@ Amortization: > spread out the high cost so that it's cheap on average all the time. +## Open Adressing + +* no chaining +* use arrays +* m: # of slots in the table +* m >= # of elements + +```plaintext +---------- +| item 1 | +---------- +| item 2 | +---------- +| | +---------- +| | +---------- +``` + +probing: try to see if we can insert something into the hashtable. +if we fail, we will compute a slightly different hash until we +find an empty slot that we can insert into this table. + +Hash function specifies the order of slots to probe +for a key. (for insert/search/delete) + +hash function `h(U, trial_count)` + +* U: universe of keys +* trial_count: integer between 0 -> m-1 + +`h(k,1)` +arbitrary key k + +h(k,1), h(k,2), ... h(k, m-1) + +to be a permutation of 0,1 ... m-1 + +```plaintext + ---------- +0 | | + ---------- +1 | | + ---------- +2 | | + ---------- +3 | | + ---------- +4 | | + ---------- +5 | | + ---------- +6 | | + ---------- +7 | | + ---------- +``` + +* `insert(k,v)`: keep probing until an empty slot is found. insert item when found. +* `search(k)`: As long as the slots encountered are occupied by keys != k. keep probing until you either encounter k or find an empty slot. + +## Cryptographic Hash + + [mit-ocw]: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-8-hashing-with-chaining/ -- cgit v1.2.3