Topic:
hash table and hash functions
Topic:
search algorithms
| |
Summary
A hash table works well for indexed lookups. The main problem is filling up the hash table. If full, a hash lookup becomes a linear scan of a hash chain. Adaptive hashing adjusts the size of the hash table dynamically. Alternatively, frequently accessed data may be moved to the front of the hash chain. Multiple hash tables may be used. (cbb 10/07)
Subtopic: move-to-front hash chains 
| Quote: vocabulary accumulation by move-to-front hash chains; 99% of searches at first node in chain [»heinS4_2002]
| | Quote: move-to-front works well for hash tables; better than extendible hashing; effective for vocabulary accumulation at 80 strings per slot [»zobeJ12_2001]
|
Subtopic: multi-level, adaptive hashing
| Quote: multi-level adaptive hashing is so effective that needed to design a bad input for the animation [»browMH12_1992]
| | Quote: constant-time lookup by parallel access, multi-level adaptive hashing; rehash when too many hash collisions [»browMH12_1992]
|
Subtopic: extendible hasing
| Quote: extendible hashing by separating hash table from directory; at most two page faults per key [»fagiR9_1979]
|
Subtopic: linear hashing
| Quote: linear hashing: no tables; split buckets in a linear order, as needed; use overflow buckets [»litwW10_1980]
| | Quote: linear hashing is faster and simpler than spiral storage; faster than binary trees and similar to double hashing [»larsPA4_1988]
| | Quote: linear hashing is simpler than trees, much faster, easier locking for concurrency control [»litwW10_1980]
| | Quote: dynamic, linear hashing; 1.7 accesses per record while maintaining an 80% load [»litwW10_1980]
| | Quote: linear hashing uses less memory than extendible hashing; the overflow chains are generally short [»ratha2_1991]
| | Quote: bucket size does not affect the performance of linear hashing and extendible hashing
|
Subtopic: linear hashing with separators
| Quote: linear hashing with separators gives single disk access to data; small memory table, dynamic sizing, high storage utilization [»larsPA9_1988]
| | Quote: linear hashing with separators probes an internal table to identify disk block with data [»larsPA9_1988]
| | Quote: linear hashing with separators uses a linear probe sequence; insertions by force records to next page, etc. [»larsPA9_1988]
|
Subtopic: linear hasing with partial expansion
| Quote: by partial expansions, a linear hash file can achieve 85% utilization and 1.05 disk accesses per retrieval [»larsPA10_1980]
| | Quote: linear hashing with partial expansions by expanding pairs of buckets [»larsPA10_1980]
| | Quote: linear hashing with partial expansions and priority splitting; 80% storage utilization, 1 block access per search, and 8% overflow space [»manoY5_1994]
|
Subtopic: climbing hashing
| Quote: use climbing hashing to increase the storage utilization of linear hashing. It reduces the size of each level [»chanYI9_1995]
|
Subtopic: linear spiral hashing
Quote: at most 2 disk access for linear spiral hashing with 97% storage utilization(78% for linear hashing); in core, separators table
[»chanYI11_1999]
|
Related Topics
Topic: hash table and hash functions (41 items)
Topic: search algorithms
(40 items)
|
