Linear hashing: Difference between revisions

Revision as of 21:16, 23 October 2005

Latest revision as of 21:36, 9 August 2025

(185 intermediate revisions by 82 users not shown)

Line 1:

'''Linear hashing''' ('''LH''') is a dynamic data structure which implements a [[hash table]] and grows or shrinks one bucket at a time. It was invented by Witold Litwin in 1980.<ref name=WL80>{{Citation | first1=Witold | last1=Litwin | title=Linear hashing: A new tool for file and table addressing | journal=Proc. 6th Conference on Very Large Databases | pages=212–223 | year=1980 | url=https://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF}}</ref>

{{wikify}}

<ref name=Ellis>

GROWTH METHODOLOGY

{{Citation | first1 = Carla Schlatter | last1=Ellis | title=Concurrency in Linear Hashing | journal=ACM Transactions on Database Systems | volume=12 | number=2 | pages=195–217 | date=June 1987| doi=10.1145/22952.22954 | s2cid=14260177 | doi-access=free }}

</ref> It has been analyzed by Baeza-Yates and Soza-Pollman.<ref name=BS>{{Citation | first1=Ricardo | last1=Baeza-Yates | first2=Hector | last2=Soza-Pollman | title=Analysis of Linear Hashing Revised | journal=Nordic Journal of Computing | pages=70–85 | year=1998 | s2cid=7497598 | url=http://pdfs.semanticscholar.org/e6cd/667fef7cd377ed8d417cc648d3d578675ad5.pdf | archive-url=https://web.archive.org/web/20190307204217/http://pdfs.semanticscholar.org/e6cd/667fef7cd377ed8d417cc648d3d578675ad5.pdf | url-status=dead | archive-date=2019-03-07 }}</ref> It is the first in a number of schemes known as dynamic hashing<ref name=BS/>

<ref name=RD>{{Citation | first1=Richard | last1=Enbody | first2 = HC | last2 = Du | title=Dynamic hashing schemes | journal=ACM Computing Surveys | pages=85–113 | date=June 1988 | volume=20 | number=2 | doi=10.1145/46157.330532 | s2cid=1437123 | doi-access=free }}</ref> such as Larson's Linear Hashing with Partial Extensions, <ref name=AL>{{Citation | first1=Per-Åke | last1=Larson | title=Dynamic Hash Tables | journal=Communications of the ACM | pages=446–457 | date=April 1988 | volume=31 | number=4 | doi=10.1145/42404.42410| s2cid=207548097 | doi-access=free }}</ref> Linear Hashing with Priority Splitting,<ref name=ruchte>

{{Citation | first1 = Willard | last1 = Ruchte | first2 = Alan | last2 = Tharp |

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

journal = IEEE Third International Conference on Data Engineering |

date = Feb 1987 | pages=2–9}}

</ref> Linear Hashing with Partial Expansions and Priority Splitting,<ref>

{{Citation | first1 = Yannis | last1 = Manolopoulos | first2 = N. | last2 = Lorentzos |

title = Performance of linear hashing schemes for primary key retrieval |

journal = Information Systems | volume = 19 | number = 5 |date = 1994 | pages =433–446| doi = 10.1016/0306-4379(94)90005-1 }}

</ref> or Recursive Linear Hashing.<ref name=RS>

{{Citation | first1 = K. |last1 = Ramamohanarao | first2 = R. | last2 = Sacks-Davis |

title = Recursive linear hashing |

journal = ACM Transactions on Database Systems|

volume=9 | number=3 |date=Sep 1984 | pages=369–391|doi = 10.1145/1270.1285 |s2cid = 18577730 |doi-access = free }}

</ref>

The file structure of a dynamic hashing data structure adapts itself to changes in the size of the file, so expensive periodic file reorganization is avoided.<ref name=RD/> A Linear Hashing file expands by splitting a predetermined bucket into two and shrinks by merging two predetermined buckets into one. The trigger for a reconstruction depends on the flavor of the scheme; it could be an overflow at a bucket or [[load factor (computer science)|load factor]] (i.e., the number of records divided by the number of buckets) moving outside of a predetermined range.<ref name=WL80 /> In Linear Hashing there are two types of buckets, those that are to be split and those already split. While extendible hashing splits only overflowing buckets, [[spiral Hashing|spiral hashing]] (a.k.a. spiral storage) distributes records unevenly over the buckets such that buckets with high costs of insertion, deletion, or retrieval are earliest in line for a split.<ref name=AL/>

Linear hashing expands the address space for the hashing function in an iterative process. One full iteration of the expansion doubles the size of the address space.

The essence of linear hashing is that records are located as if the file was fully expanded. The hashing algorithm recognizes how much of the file currently exists and accounts for this in its selection of the appropriate bucket in which to store a given record.

If the necessary bucket exists, the record is written to that bucket. If the bucket has not yet been created, the system walks backward through the number of buckets that do exist until it finds a bucket to which the record can be added. When the bucket to which the record correctly hashes is created, the bucket in which it has been placed temporarily is visited, and the record is moved to its true home.

Linear Hashing has also been made into a scalable distributed data structure, '''LH*'''. In LH*, each bucket resides at a different server.<ref name=WL93>

When a frame is full, additional records assigned to the frame are stored in the overflow file. The overflow file is also divided into the same size frames. When the initial overflow frame is full, a link is established to another free frame in the overflow file.

{{Citation | first1=Witold | last1=Litwin | first2=Marie-Anne |last2 = Neimat |

first3 = Donavan A. | last3 = Schneider | title=LH: Linear Hashing for distributed files | journal=ACM SIGMOD Record |

pages = 327–336 | date = 1993| volume=22 | issue=2 | doi=10.1145/170036.170084 | s2cid=259938726 }}

</ref> LH* itself has been expanded to provide data availability in the presence of failed buckets.<ref name=LMS>

{{Citation | first1=Witold | last1=Litwin | first2 = Rim | last2 = Moussa |

first3 = Thomas | last3 = Schwarz | title=LH*RS - a highly-available scalable distributed data structure |journal=ACM Transactions on Database Systems | volume=30 | number=3 | pages=769–811 | date=Sep 2005| doi=10.1145/1093382.1093386 | s2cid=1802386 | url=https://basepub.dauphine.fr/handle/123456789/15124 }}

</ref> Key based operations (inserts, deletes, updates, reads) in LH and LH* take maximum constant time independent of the number of buckets and hence of records.<ref name = WL80/><ref name=LMS/>

==Algorithm details==

When the percentage of primary space occupied by data exceeds the threshold, the table automatically expands by one group. Once this group has been added, a portion of the rows in up to three of the old groups are redistributed to the new group. Likewise, when primary space utilization falls too far below the resize threshold (10 to 20 percent, depending on the number of groups in the table), the table automatically contracts.

Records in LH or LH* consists of a key and a content, the latter basically all the other attributes of the record.<ref name=WL80/><ref name=LMS/> They are stored in buckets. For example, in Ellis' implementation, a bucket is a linked list of records.<ref name=Ellis/> The file allows the key based CRUD operations create or insert, read, update, and delete as well as a scan operations that scans all records, for example to do a database select operation on a non-key attribute.<ref name=LMS/> Records are stored in buckets whose numbering starts with 0.<ref name=LMS/>

***

The key distinction from schemes such as Fagin's extendible hashing is that as the file expands due to insertions, only one bucket is split at a time, and the order in which buckets are split is already predetermined.<ref name="Fagin">

{{Citation |last1=Fagin |first1=Ronald |title=Extendible Hashing - A Fast Access Method for Dynamic Files |date=Sep 1979 |url=http://dl.acm.org/citation.cfm?doid=320083.320092 |journal=ACM Transactions on Database Systems |volume=4 |number=2 |pages=315–344 |doi=10.1145/320083.320092 |s2cid=2723596 |last2=Nievergelt |first2=Jurg |last3=Pippenger |first3=Nicholas |last4=Strong |first4=Raymond}}

</ref>

===Hash functions===

Linear Hashing

The hash function <math>h_i(c)</math> returns the 0-based index of the bucket that contains the record with key <math>c</math>. When a bucket which uses the hash function <math>h_i</math> is split into two new buckets, the hash function <math>h_i</math> is replaced with <math>h_{i+1}</math> for both of those new buckets. At any time, at most two hash functions <math>h_l</math> and <math>h_{l+1}</math> are used; such that <math>l</math> corresponds to the current '''level'''. The family of hash functions <math> h_i(c)</math> is also referred to as the dynamic hash function.

--------------

Linear hashing grew out of the work of many individuals who were searching for a method to dynamically extend the fixed address space of hashing functions.

Typically, the value of <math>i</math> in <math>h_i</math> corresponds to the number of rightmost binary digits of the key <math>c</math> that are used to segregate the buckets. This dynamic hash function can be expressed arithmetically as <math display="inline"> h_i(c) \mapsto (c \bmod 2^i) </math>. Note that when the total number of buckets is equal to one, <math>i=0</math>.

***

Linear hashing expands the address space for the hashing function in an iterative process. One full iteration of the expansion doubles the size of the address space.

The essence of linear hashing is that records are located as if the file was fully expanded. The hashing algorithm recognizes how much of the file currently exists and accounts for this in its selection of the appropriate bucket in which to store a given record.

If the necessary bucket exists, the record is written to that bucket. If the bucket has not yet been created, the system walks backward through the number of buckets that do exist until it finds a bucket to which the record can be added. When the bucket to which the record correctly hashes is created, the bucket in which it has been placed temporarily is visited, and the record is moved to its true home.

***

Complete the calculations below to determine the correct hashing function for the given hashing key <math>c</math>.<ref name="LMS" /><syntaxhighlight lang="python">

# l represents the current level

# s represents the split pointer index

a = h_l(c)

if (a < s): a = h_{l+1}(c)

</syntaxhighlight>

===Split control===

OpenInsight's Linear Hash

Linear hashing algorithms may use only controlled splits or both controlled and uncontrolled splits.

-------------------------

OpenInsight stores data in a primary table file (the primary address space) and an overflow file. The operating system file names are REVnnnnn.LK for the primary frame file and REVnnnnn.OV for the overflow file (where nnnnn represents a five-digit integer, which is the same for a given .LK and .OV pair).

The primary address space is divided into fixed length frames. The default frame size is 1024 bytes. In order for the table to be optimized, frame size is of secondary importance to the number of records per frame. It is recommended that frames not contain more than 20 records. Because OpenInsight must search a frame sequentially for a given record, more records per frame can lead to a degradation in performance. When fine tuning the database application, the frame size can be altered. For example, when the median record size exceeds 50 bytes, testing the data table with a larger frame size may improve performance. Estimating record size for variable length data records is more an art than a science, as is estimating the best performing frame size. It is also recommended that frame size not exceed 4 kilobytes as performance degrades in this case as well.

'''Controlled splitting''' occurs if a split is performed whenever the [[load factor (computer science)|load factor]], which is monitored by the file, exceeds a predetermined threshold.<ref name="LMS" /> If the hash index uses controlled splitting, the buckets are allowed to overflow by using linked overflow blocks. When the ''load factor'' surpasses a set threshold, the ''split pointer's'' designated bucket is split. Instead of using the load factor, this threshold can also be expressed as an occupancy percentage, in which case, the maximum number of records in the hash index equals (occupancy percentage)*(max records per non-overflowed bucket)*(number of buckets).<ref name=":0">{{Cite book |last1=Silberschatz |first1=Abraham |title=Database system concepts |last2=Korth |first2=Henry F. |last3=Sudarshan |first3=S. |date=2020 |publisher=McGraw-Hill Education |isbn=978-1-260-08450-4 |edition=Seventh |___location=New York, NY}}</ref>

***

When a frame is full, additional records assigned to the frame are stored in the overflow file. The overflow file is also divided into the same size frames. When the initial overflow frame is full, a link is established to another free frame in the overflow file.

***

An '''uncontrolled split''' occurs when a split is performed whenever a bucket overflows, in which case that bucket would be split into two separate buckets.

In OpenInsight, a group is defined as the primary frame (located in the primary address space) plus all the additional, linked overflow frames. Group is analogous to "buckets" in the hashing algorithm example discussed above. The overflow frames are allocated, whenever possible, so that frames of the same group are contiguous. Overflow frames may later be emptied when the table resizes or rows are deleted. Empty frames occurring at the end of the overflow file are truncated.

The first frame of the overflow file contains the first frame of the overflow frame free list, which helps to efficiently manage the overflow. This list is a sorted list of pointers to empty overflow frames. As frames are emptied, corresponding pointers are added to the free list. If the size of the free list exceeds one frame, the filing system creates links to other frames in the overflow file, where the list is continued.

As overflow frames are added or removed from a group, the forward and skip pointers in the effected groups are updated. The forward pointer points to the next overflow frame. The skip pointer points to the overflow frame where the next record begins. When record size is small, forward and skip pointers may point to the same frame. When record size exceeds frame size, the frame pointer and skip pointer point to different overflow frames. When the system searches a group for a record, the skip pointer points beyond the overflow frames containing the overflow of the current record, optimizing record searches in overflowing files.

'''File contraction''' occurs in some LH algorithm implementations if a controlled split causes the load factor to sink below a threshold. In this case, a merge operation would be triggered which would undo the last split, and reset the file state.<ref name="LMS" />

===Split pointer===

Automatic Table Sizing

The index of the next bucket to be split is part of the file state and called the '''split pointer''' <math>s</math>. The split pointer corresponds to the first bucket that uses the hash function <math>h_l</math> instead of <math>h_{l+1}</math>.<ref name="LMS" />

The greater the number of records assigned to a group, the slower the access time when overflow exists. As mentioned above, this is due to the sequential access process required to locate a specific record in a group. For example, to locate a record the primary table needs to be accessed, then the overflow file needs to be accessed, looking sequentially from one frame to the next in the group, until the specified record is found.

To resolve this problem, linear hash tables automatically resize themselves when primary space gets too full, thereby reducing the number of overflow frames and also the average number of records per frame. This automatic resizing is controlled by the resize threshold.

For example, if numerical records are inserted into the hash index according to their farthest right binary digits, the bucket corresponding with the appended bucket will be split. Thus, if we have the buckets labelled as 000, 001, 10, 11, 100, 101, we would split the bucket 10 because we are appending and creating the next sequential bucket 110. This would give us the buckets 000, 001, 010, 11, 100, 101, 110.<ref name=":0" />

***

When the percentage of primary space occupied by data exceeds the threshold, the table automatically expands by one group. Once this group has been added, a portion of the rows in up to three of the old groups are redistributed to the new group. Likewise, when primary space utilization falls too far below the resize threshold (10 to 20 percent, depending on the number of groups in the table), the table automatically contracts.

When a bucket is split, split pointer and possibly the level are updated according to the following, such that the level is 0 when the linear hashing index only has 1 bucket.<ref name="LMS" /><syntaxhighlight lang="python">

***

# l represents the current level

# s represents the split pointer index

In essence, the threshold setting is an indicator of the table's ability to add rows with minimum overflow. Adjusting the threshold also requires some experimentation and should be examined in the context of other parameters as well, such as average number of records per frame. A low threshold on a steadily growing table allows faster access to data since there are fewer rows in each group. A higher threshold allows more primary space to be used before resizing, which is suitable for a more static table. A threshold of 80 percent for the filled capacity of the primary address space is a good indicator that expansion is called for. The threshold value is set from the Database Manager tool. This is discussed later in this chapter.

s = s + 1

if (s >= 2^l):

l = l + 1

s = 0

</syntaxhighlight>

===LH*===

The main contribution of LH* is to allow a client of an LH* file to find the bucket where

the record resides even if the client does not know the file state. Clients in fact store

their version of the file state, which is initially just the knowledge of the first bucket, namely Bucket 0. Based on their file state, a client calculates the address of a

key and sends a request to that bucket. At the bucket, the request is checked and if

the record is not at the bucket, it is forwarded. In a reasonably stable system, that is,

if there is only one split or merge going on while the request is processed, it can

be shown that there are at most two forwards. After a forward, the final bucket sends an

Image Adjustment Message to the client whose state is now closer to the state of the distributed file.<ref name="LMS" /> While forwards are reasonably rare for active clients,

their number can be even further reduced by additional information exchange between

servers and clients <ref name="CS">

{{Citation |last1=Chabkinian |first1=Juan |title=Fast LH* |date=2016 |journal=International Journal of Parallel Programming |volume=44 |number=4 |pages=709–734 |doi=10.1007/s10766-015-0371-8 |s2cid=7448240 |last2=Schwarz |first2=Thomas}}

</ref>

== Other properties ==

===File state calculation===

The file state consists of split pointer <math>s</math> and level <math>l</math>. If the original file started with <math>N=1</math> buckets, then the number of buckets <math>n</math> and the file state are related via

<ref name="CS" />

<math>n = 2^l+s </math>.

==Adoption in language systems==

Griswold and Townsend <ref>{{Citation | title=The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon | first1=William G. | last1=Griswold | author1-link = Bill Griswold | first2=Gregg M. | last2=Townsend | journal=Software: Practice and Experience | volume=23 | issue=4 | date=April 1993 | pages=351–367 | doi=10.1002/spe.4380230402 | s2cid=11595927 | url=http://citeseer.ist.psu.edu/griswold93design.html}}</ref> discussed the adoption of linear hashing in the [[Icon language]]. They discussed the implementation alternatives of [[dynamic array]] algorithm used in linear hashing, and presented performance comparisons using a list of Icon benchmark applications.

==Adoption in database systems==

Linear hashing is used in the [[Berkeley DB|Berkeley database system (BDB)]], which in turn is used by many software systems, using a C implementation derived from the [[Communications of the ACM|CACM]] article and first published on the Usenet in 1988 by Esmond Pitt.

==References==

{{Reflist}}

==External links==

* [https://tommyds.sourceforge.net/ TommyDS, C implementation of a Linear Hashtable]

* [http://hackthology.com/an-in-memory-go-implementation-of-linear-hashing.html An in Memory Go Implementation with Explanation]

* [https://github.com/KevinStern/index-cpp/blob/master/src/linear_hashing_table.h A C++ Implementation of Linear Hashtable which Supports Both Filesystem and In-Memory storage]

==See also==

* [[Extendible hashing]]

* [[Consistent hashing]]

* [[Spiral Hashing]]

[[Category:Search algorithms]]

[[Category:Hashing]]