A hashing database system that efficiently handles collisions comprises a list of data blocks divided into a plurality of stages, each of which is geometrically smaller than the preceding stage. The key of the data to be stored or retrieved (the "desired key") is hashed and, along with the stage number, used as an input into a staging algorithm to derive an offset into the list. One or more data blocks in the list surrounding the hashed-to data block are checked to determine whether the key field in the data block matches the desired key. If the keys match, then the desired data block is found. If the desired key is not found, then the hashed key is again used as an input into a staging algorithm along with the stage, and a new offset is derived and used as an index into the next stage of the index list. These steps are repeated until the key is found or the last stage is reached. The last stage is an overflow where the data is guaranteed to be found or space is guaranteed to be found for insertion of new data if not found in one of the stages.

An updatable and expandable directory structure and resultant access procedures emulating a write-once or indelible record medium to a rewriteable record medium as to accessing characteristics. The directory is indexed; one directory header for a first set of files indexes another set of files. Sector clusters or data extents are managed such that random recording from any file proceeds independently of write-once characteristics. The directory is stored on the medium as data is recorded. Each directory entry contains an archival history of recording of a related data file in the medium. Both logical and physical addressing is employable.

A method for improving the execution of significant bit scans on a data entity in a computer system is provided. The data entity is examined in a number of iterations equal to the base two logarithm of the size of the data entity in bits, N. Initially, half of the data entity is examined to determine if the significant bit is present. If not, the other half of the data entity is examined. The half within which the significant data entity resides is then iteratively halved and examined in each successive iteration of the method until the number of bits examined is equal to one.

The retrieval of stored data by means of a search word or search key by using, a hashing method. For this purpose, the search key is resolved into a polynomial having the form of ##EQU1## where i=control variable, k=its maximum value, w.sub.i =polynomial coefficient, p=a power of 2, m=number of search keys in an address table stored in the memory (7). The search process occurs by means of a recursive hashing function having the form of ##EQU2## using hashing function tables and address sub-tables stored in the memory. The address compared circuit, having three temporary memories for the polynomial coefficients w.sub.i, a multiplexer, the memory, an adder registers, a comparator, an edge-triggered JK-type flip-flop with an AND gate connected to its output, and a control unit makes it possible to achieve an inexpensive hardware implementation of the search method.

A method is disclosed for converting operator inputs into control commands in a computer-controlled interlocking system. For standard inputs, a search method is used instead of a complicated and time-consuming syntax analysis. Using a pseudorandom technique, a search code is determined from the text entered into an input device. With the aid of this search code, the control command assigned to the input text is found in a previously compiled list of all control commands. Before being processed, the control command found is checked for agreement with the input by a direct comparison.