# Performance of Linear and Spiral Hashing Algorithms
## 2 Background
### Linear Hashing
During a split, all records in the bucket to be split are rehashedwith the new partial hash function \(h_{l+1}\) and accordingly either remain in the same bucket or are moved to the new bucket. We can also implement merge operations to adjust to a decrease in the number of records. A merge always undoes the last split. We use a numerical example to illustrate LH and its operations. Figure 1 (top) shows the state of an LH file with five buckets. Since \(5=2^{2}+1\), the split pointer is one and the level is two. Instead of showing complete records, the figure only shows the keys, which we assume to be natural numbers between 0 and 100. Our hash function \(h\) is simply the identity in this example. Thus, \(h_{l}(c)\) for a key \(c\) is just \(c\pmod{2^{i}}\) or, equivalently, the last \(i\) bits of \(c\). We started out with one bucket, Bucket 0. All records in this bucket were placed there because \(h_{0}\) is always 0. The file has now grown to five buckets, so we use \(h_{2}\) and \(h_{3}\) for addressing. There are currently 15 records in five buckets, so the load factor is 3. To calculate the address of the record with key 84, we calculate \(h_{2}(84)=84\pmod{4}=0\). Since this address is smaller than the split pointer, we recalculate with the next hash function and obtain \(h_{3}(84)=84\pmod{8}=4\). This means that the record with key 84 is in Bucket 4. An alternative reasoning involves looking at the binary representation of 84, which is 0b1010100. The address is formed by either the last two or three bits because the level is two. The record with key 48 has an address calculated from \(h_{2}(48)=48\pmod{4}=0,h_{3}(48)=48\pmod{8}=0\), and, therefore, resides in Bucket 0. To continue the example, we assume that we insert a record with key 12. Since \(h_{2}(12)=12\pmod{4}=0\) and \(h_{3}(12)=12\pmod{8}=4\), the record is placed into Bucket 4. With the insertion of this record, the load factor, i.e., the average capacity of the buckets, exceeds 3, which, in our example, triggers a split. The bucket to be split is the one given by the split pointer, namely Bucket 1. In an Extensible Hashing scheme, we would split because we try to insert into an overflowing bucket and then split that bucket. However, LH uses a predefined order of splits, and the turn of Bucket 3 will come only after another intervening split. LH creates a new Bucket 5. It then rehashes all the records in Bucket 1 using the new file state. As a simple optimization, the address recalculation can skip the evaluation using \(h_{2}\) since we know that its value has to be \(1\) because otherwise, the record would not reside in Bucket 1. Thus, calculating \(h_{3}(53)=53\pmod{8}=5\), \(h_{3}(29)=29\pmod{8}=5\), and \(h_{3}(45)=45\pmod{8}=5\) has LH move the three records into the new bucket. If we were to recalculate the addresses of all other records in the data structure, they would not change, as the only change in the execution of the addressing calculation is  
Figure 1: Linear Hashing example with \(b=5\) and \(b=6\). the comparison with the split pointer. The lower part of Figure 1 shows the state of the LH file after the split as well as the split.