Content deleted Content added
m Reverted edit by 154.125.195.226 (talk) to last version by Skynxnex |
m →External links: HTTP to HTTPS for SourceForge |
||
| (One intermediate revision by one other user not shown) | |||
Line 15:
{{Citation | first1 = K. |last1 = Ramamohanarao | first2 = R. | last2 = Sacks-Davis |
title = Recursive linear hashing |
journal = ACM Transactions on
volume=9 | number=3 |date=Sep 1984 | pages=369–391|doi = 10.1145/1270.1285 |s2cid = 18577730 |doi-access = free }}
</ref>
Line 53:
Linear hashing algorithms may use only controlled splits or both controlled and uncontrolled splits.
'''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 |
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.
Line 105:
==External links==
* [
* [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]
| |||