datatype 'a bucket = Empty | Deleted | Filled of 'a;

     (* search for x starting at bucket i, but not passing bucket j.
        Here and elsewhere, n is the number of buckets. *)
     fun lookup1(A,i,j,n,x) =
             if Array.sub(A,i) = Filled(x) then true
             else if Array.sub(A,i) = Empty then false
             else if i=j then false (* we have searched the whole
                                       hash table *)
             else lookup1(A,(i+1) mod n,j,n,x);

     (* lookup x in hash table A of n buckets, using hash function h *)
     fun lookup(A,h,n,x) = lookup1(A,h(x),(h(x)-1) mod n,n,x);

     (* delete1 deletes x from A; parameters are as for lookup1 *)
     fun delete1(A,i,j,n,x) =
             if Array.sub(A,i) = Filled(x) then
                 Array.update(A,i,Deleted)
             else if Array.sub(A,i) = Empty then () (* x cannot be
                             in the hash table *)
             else if i=j then () (* we have searched all buckets and
                             not found x *)
             else delete1(A,(i+1) mod n,j,n,x);

     (* delete takes parameters like lookup *)
     fun delete(A,h,n,x) = delete1(A,h(x),(h(x)-1) mod n,n,x);

     exception NoMoreRoom;

     (* insert1 is analogous to lookup1 *)
     fun insert1(A,i,j,n,x) =
             if Array.sub(A,i) = Empty orelse Array.sub(A,i) = Deleted then
                     Array.update(A,i,Filled(x))
             else if i=j then raise NoMoreRoom
             else insert1(A,(i+1) mod n,j,n,x);

     (* insert is analogous to lookup *)
     fun insert(A,h,n,x) = insert1(A,h(x),(h(x)-1) mod n,n,x);