Algorithms & Data Structures - 2015
Many applications require a dynamic set that support only the dictionary operations such as insert, search, and delete.
A hash table is an effective data structure for implementing dictionaries. Although searching for an element in a hash table can take as long as searching for an element in a linked list - O(n) time in the worst case - in practice, hashing performs extremely well.
Under reasonable assumptions, the average time to search for an element in a hash table is O(1).
A hash table generalizes the simpler notion of an ordinary array.
Directly addressing into an ordinary array makes effective use of our ability to examine an arbitrary position in an array in O(1) time.
When the number of keys actually stored is small relative to the total number of possible keys, hash table becomes an effective alternative to directly addressing an array, since a hash table typically uses an array of size proportional to the number of keys actually stored. Instead of using the keys as an array index directly, the array index is computed from the key.
Implementing hash table involves couple of ideas such as chaining as a way to handle collisions in which more than one key map to the same array index and open addressing which is another way to deal with collisions, and perfect hashing which gives us O(1) worst-case search time.
Check an example for Hash Table from K&R.
More on hashing Hash Map Sample codes
Comparison: Hash Table vs Tree
Examples of application: 1. De-duplication
- Removing duplicates from a stream of objects such as linear scan through a huge file or object arriving in real time (packets).
- Keep track of unique objects.
- reports unique visitors to web site
- avoid duplicates in search results
- How?
When a new object x arrives, lookup x in hash table. If not found, insert x into hash table.
- Input: unsorted array of n integers. Target sum t with any two numbers in the array.
- Goal: Determine whether or not there are two numbers x, y in the array with x+y = t.
- symbol tables in compilers
- blocking network traffic
- search algorithms (e.g., game tree exploration)
In a heap, the records are stored in an array so that each key is guaranteed to be larger than its two children keys. So, no node in a heap-ordered tree has a key larger than the key at the root.
The basic operations are:
- insert - adding a new object to the heap, O(log(n))
- extract - extracting max (or min) value, O(log(n))
- heapify - n batched inserts, O(n)
- delete - O(log(n))
A spatial data structure is one that organized geometry in two- and three- dimensional hierarchical structures. So, the structure is nested and of recursive nature.
Read full article from Algorithms & Data Structures - 2015
No comments:
Post a Comment