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: movetofront hash chains
Quote: vocabulary accumulation by movetofront hash chains; 99% of searches at first node in chain [»heinS4_2002]
 Quote: movetofront works well for hash tables; better than extendible hashing; effective for vocabulary accumulation at 80 strings per slot [»zobeJ12_2001]
 Subtopic: multilevel, adaptive hashing
Quote: multilevel adaptive hashing is so effective that needed to design a bad input for the animation [»browMH12_1992]
 Quote: constanttime lookup by parallel access, multilevel 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)
