# Linear Hashing: A New Tool for File and Table Addressing

@inproceedings{Litwin1980LinearHA, title={Linear Hashing: A New Tool for File and Table Addressing}, author={Witold Litwin}, booktitle={VLDB}, year={1980} }

Linear hashing is a hashing in which the address space may grow or shrink dynamically. A file or a table may then support any number of insertions or deletions without access or memory load performance deterioration. A record in the file is, in general, found in one access, while the load may stay practically constant up to 90 %. A record in a table is found in a mean of 1.7 accesses, while the load is constantly 80 %. No other algorithms attaining such a performance are known.Â

#### 524 Citations

A Single-File Version of Linear Hashing with Partial Expansions

- Computer Science
- VLDB
- 1982

An improved version of linear hashing with partial expansions is presented, which instead of having a separate overflow area, the storage area for overflow records is incorporated into the main file. Expand

Linear Hashing with Partial Expansions

- Computer Science
- VLDB
- 1980

A new method for organising dynamic files is presented and its performance is analysed, revealing that an average search length in the range 1.1 - 1.2 accesses can easily be achieved, even for storage utilisation as high as 85-90 per cent. Expand

Concurrency and linear hashing

- Computer Science
- PODS '85
- 1985

This paper presents a solution to allow for concurrency in linear hash files that is based on locking protocols and minor modifications in the data structure and addresses the problem of adapting this technique for use in a distributed system. Expand

Trie hashing

- Computer Science
- SIGMOD '81
- 1981

A new algorithm for hashing that stores the records in order, and search for a record is performed in only one disk access, for files attaining millions of records. Expand

Linear hashing with separatorsâ€”a dynamic hashing scheme achieving one-access

- Computer Science
- TODS
- 1988

The new method is the first practical method offering one-access retrieval for large dynamic files, and its most outstanding feature is that any record can be retrieved in exactly one disk access. Expand

File organization using composite perfect hashing

- Computer Science
- ACM Trans. Database Syst.
- 1989

This work proposes and analyzes a composite perfect hashing scheme for large external files that guarantees retrieval of any record in a single disk access and supports efficient range searches in addition to being a completely dynamic file organization scheme. Expand

Linear hashing with overflow-handling by linear probing

- Computer Science
- TODS
- 1985

A new, simple method for handling overflow records in connection with linear hashing is proposed, based on linear probing and does not rely on chaining, which is competitive with that of other variants of linear hashing. Expand

Linear hashing with Priority Splitting: A method for improving the retrieval performance of linear hashing

- Computer Science
- 1987 IEEE Third International Conference on Data Engineering
- 1987

A straightforward modification of linear hashing is presented which, according to experimental results, significantly reduces the average number of retrieval probes in almost aft cases when compared with standard linear hashing. Expand

Concurrency in Extendible Hashing

- Computer Science
- Inf. Syst.
- 1988

This paper presents a solution to allow for concurrency in one of these dynamic hashing data structures, namely extendible hashfiles, based on locking protocols and minor modifications in the data structure. Expand

Linear Spiral Hashing for Expansible Files

- Computer Science
- IEEE Trans. Knowl. Data Eng.
- 1999

This work proposes a new scheme for dynamic hashing in which the growth of a file occurs at a rate of n+k/n per full expansion, where n is the number of pages of the file and k is a given integer constant which is smaller than n, as compared to a rates of two in linear hashing. Expand

#### References

SHOWING 1-10 OF 21 REFERENCES

Linear Hashing with Partial Expansions

- Computer Science
- VLDB
- 1980

A new method for organising dynamic files is presented and its performance is analysed, revealing that an average search length in the range 1.1 - 1.2 accesses can easily be achieved, even for storage utilisation as high as 85-90 per cent. Expand

Virtual Hashing: A Dynamically Changing Hashing

- Computer Science
- VLDB
- 1978

This work defines virtual hashings which practically independently of the number of such records find in one disk access almost each record of the file, such that several accesses would be needed if the function initially chosen for the file was used. Expand

Extendible hashingâ€”a fast access method for dynamic files

- Computer Science
- ACM Trans. Database Syst.
- 1979

This work studies, by analysis and simulation, the performance of extendible hashing and indicates that it provides an attractive alternative to other access methods, such as balanced trees. Expand

Dynamic hashing

- Computer Science
- BIT
- 1978

A new file organisation called dynamic hashing is presented. The organisation is based on normal hashing, but the allocated storage space can easily be increased and decreased without reorganisingâ€¦ Expand

The reallocation of hash-coded tables

- Computer Science
- CACM
- 1973

The technique can be used to eliminate previously flagged deletions from any hash-coded table, or to change from one hashing method to another, and can be utilized in conjunction with a linear reallocation of the table being rescattered. Expand

Perfect hashing functions: a single probe retrieving method for static sets

- Computer Science
- CACM
- 1977

A refinement of hashing which allows retrieval of an item in a static table with a single probe is considered, and a rough comparison with ordinary hashing is given which shows that this method can be used conveniently in several practical applications. Expand

Analysis of Collisions when Hashing by Division

- Computer Science
- Inf. Syst.
- 1975

Using simple formulas derived for the calculation of overflow records when the division method is used for hashing keys in the following distributions, it is shown that the division methods indeed produces less collisions then the theoretically perfect randomization method. Expand

Hashing Schemes for Extendible Arrays

- Computer Science
- JACM
- 1977

It is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely hashing schemes that utilize storage too conservatively are inevitably poor in expected access time. Expand

Big Buckets Are (Are Not) Better!

- Computer Science
- JACM
- 1977

The relationship between certain techniques for the storage of information in a computer and a cell occupancy problem is shown and the distribution and expected value of the number of comparisons and in particular the behavior as n-~ ~ are determined. Expand

General performance analysis of key-to-address transformation methods using an abstract file concept

- Computer Science
- CACM
- 1973

This paper presents a new approach to the analysis of performance of the various key-to-address transformation methods. In this approach the keys in a file are assumed to have been selected from theâ€¦ Expand