Topic: adaptive hash table

topics > computer science > information > Group: information retrieval

hash table and hash functions
search algorithms


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 up

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 up

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 up

Quote: extendible hashing by separating hash table from directory; at most two page faults per key [»fagiR9_1979]

Subtopic: linear hashing up

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 up

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 up

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 up

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 up

Quote: at most 2 disk access for linear spiral hashing with 97% storage utilization(78% for linear hashing); in core, separators table

Related Topics up

Topic: hash table and hash functions (41 items)
Topic: search algorithms
(40 items)

Updated barberCB 3/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.