Dynamic hashing in external searching

PPL code for linear hashing

PROCEDURE Add_Key1(New_Key : Key_Data)

-- All identifiers are assumed global
-- ALOS is the Average Length Of Search, and ALOS_MAX is its maximum value.
-- BUCKET() is the array of buckets
-- B is the number of keys in a primary area bucket
-- S0 is the initial size of the hash table. The actual size is calculated
--    using the following S = S0 * 2^(Doubling_factor)
-- Doubling_factor is used to expand the hash table size, and is initially
--    set equal to zero.
-- Next_Bucket is used to indicate the next bucket to be split as ALOS
--    exceeds its maximum allowable value. Initially equal zero.

BEGIN
    INITIALIZE: Calculate ALOS
                Update_Flag = FALSE
    LOOP
    BEGIN  IF ALOS > ALOS_MAX THEN   EXIT END IF
        IF keys in BUCKET(Next Bucket) > 1
        THEN
            Create BUCKET(S0 + Next_Bucket)
            Move last (B/2) keys from BUCKET(Next_Bucket)
                                 to BUCKET(S0 + Next_Bucket)
            Calculate new ALOS value
        END IF
        Next_Bucket += 1
        Update_Flag = TRUE
    END LOOP
    TERMINATE: ADDRESS = Hash_function(New_Key,Doubling_factor,S0)
               -- Update factor for new range of addresses
               IF Update_Flag THEN Doubling factor +=1 END IF
END Add_Key1

PPL code for searching in a linear hashing scheme

FUNCTION Search_Key1(Sought_Key : Key_Data; S0 : INTEGER;

BEGIN
    IF Doubling_factor = 0
    THEN
        ADDRESS = Hash_function(Sought_Key,Doubling_factor,S0)

    ELSE -- Assume key is located in a bucket that was not split
      ADDRESS = Hash_function(Sought_Key,(Doubling_factor - 1),S0)
      IF (ADDRESS < Next_bucket) AND (Sought_Key is not in BUCKET(ADDRESS))
      THEN
          ADDRESS = Hash_function(Sought_Key,Doubling_factor,S0)
      END IF
    END IF
    RETURN (ADDRESS)
END Search_Key1

PPL code for linear hashing with two partial expansions

PROCEDURE Expand;
-- Two-stage partial expansion scheme
-- SH =  (number of initial buckets) / 2

BEGIN
    INITIALIZE: SH = S0 / 2
    LOOP
    BEGIN   FOR I = 1 TO SH
        N = 2 * SH + I
        Create BUCKET(N)
        Move selected keys from BUCKET(I - 1) to BUCKET(N)
        Move selected keys from BUCKET(SH + I - 1) to BUCKET(N)
    END LOOP
    TERMINATE: None

    INITIALIZE: None
    LOOP
    BEGIN   FOR I = 1 TO SH
        N = 3 * SH + I
        Create BUCKET(N)
        Move selected keys from BUCKET(I - 1) to BUCKET(N)
        Move selected keys from BUCKET(SH + I - 1) to BUCKET(N)
        Move selected keys from BUCKET(2 * SH + I - 1) to BUCKET(N)
    END LOOP
    TERMINATE: SO *= 2     -- double table size.
END Expand

PPL code for virtual hashing

PROCEDURE Add_Key2(New_Key : Key_Data)

-- Identifiers used are similar to those in Add_Key1.
-- Used_Flag() is an array of bits or flags to indicate if a bucket is
--             occupied by at least one key.

BEGIN
    INITIALIZE: ADDRESS = Search_Key2(Sought_Key,Doubling_factor,S0,N)
    LOOP
    BEGIN IF BUCKET(ADDRESS) is not full THEN EXIT END IF
        IF N = Doubling_factor
        THEN
            IF ALOS > ALOS_MAX THEN Doubling_factor += 1
                               ELSE -- no need to double size, yet
                                    Obtain overflow address
            END IF
        END IF
        Used_Flag( ADDRESS + 2^N * S0) = TRUE
        N += 1
        Rehash keys in BUCKET(ADDRESS) and linked overflow buckets, using N
        ADDRESS = Hash_function(Sought_Key,N,S0)
    END LOOP
    TERMINATE: Add New_Key to BUCKET(ADDRESS)
END Add_Key2

PPL code for searching in a virtual hasing scheme

FUNCTION Search_Key2(Sought_Key : Key_Data; Doubling_factor, S0 : INTEGER;
                                          VAR N : INTEGER) return INTEGER

BEGIN
    N = Doubling_factor
    INITIALIZE: ADDRESS = Hash_function(Sought_Key,N,S0)
    LOOP
    BEGIN IF Used_Flag(N) THEN EXIT END IF
        N -= 1;
        ADDRESS = Hash_function(Sought_Key,N,S0)
    END LOOP
    TERMINATE: RETURN(ADDRESS)
END Search_Key2

Adding keys to a dynamic hashing scheme

PROCEDURE Add_Key3(New_Key : Key_Data)

-- Add a new key using dynamic hashing scheme

BEGIN
    ADDRESS = Hash_function(New_Key,Hash_Table_Size)
    IF Tree_ptr(ADDRESS) is nul
    THEN -- Hash table address points to bucket directly
        Process_Bucket
    ELSE -- Hash table address is a root for a split tree
        Search_Bucket -- obtain bucket address
        Process_Bucket
    END IF
END Add_Rey3

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

PROCEDURE Search_Bucket

-- Search for a bucket by traversing a split tree

BEGIN
    INITIALIZE: ROOT = Hash_Ptr(ADDRESS)
    LOOP <Traverse>
    BEGIN
        ADR = Hash_function2(New_Key)
        IF Leaf(ROOT ADR).Type is terminal THEN EXIT <Traverse> END IF
        ROOT = Leaf(R0OT,ADR).Ptr
    END LOOP <Traverse>
    TERMINATE: ADDRESS = Leaf(ROOT,ADR).Ptr
END Search_Bucket

PROCEDURE Process_Bucket

BEGIN
    READ Bucket_File,ADDRESS,BUCKET
    IF BUCKET.Count_Key = MAX_KEY
    THEN -- BUCKET(ADDRESS) is full
        Split_Bucket
    ELSE -- Simply add key
        BUCKET.Count_Key += 1
        BUCKET.Key(BUCKET.Count_Key) = New_Key
    END IF

END Process_Bucket

PROCEDURE Split_Bucket

BEGIN
    Num_Bucket += 1
    BUCKET.Key(MAX_KEY+1) = New_Key
    INITIALIZE: BUCKET.Count_Key = 0
                NEWBUCKET.Count_Key = 0
    LOOP
    BEGIN FOR i = 1 to MAX_KEY + 1
        ADR = Hash_Function2(BUCKET.Key(i)) -- 0/1 function
        IF ADR = 0
        THEN BUCKET.Count_Key += 1
            BUCKET.Key(BUCKET.Count_Key) = BUCKET.Key(i)
        ELSE
            NEWBUCKET,Count_Key += 1
            NEWBUCKET.Key(BUCKET Count_Key) = BUCKET.Key(i)
        END IF
    END LOOP
    TERMINATE: WRITE Bucket_File,ADDRESS,BUCKET
               WRITE Bucket_File,Num_Bucket,NEWBUCKET
               Create leaves in memory and link them hash table
               Set leaf pointers to ADDRESS and Num_Bucket
END Split_Bucket