Hashing
Prof. Dr. Mirco Schoenfeld
Recap
Remember searching?
Implementation
Search
Insert
Delete
sorted array
\(O( \log n)\)
\(O(n)\)
\(O(n)\)
unsorted list
\(O(n)\)
\(O(1)\)
\(O(n)\)
binary search tree
\(O(h)\)
\(O(h)\)
\(O(h)\)
REALLY FAST searches
There is a data structure which allows
inserting in
\(O(1)\)
,
deleting in
\(O(1)\)
, and
searching in
\(O(1)\)
Too good to be true?
