Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Filing 284

Response to CLAIM CONSTRUCTION BRIEF filed by AOL Inc, Amazon.com Inc., Google Inc., Match.Com LLC, MySpace Inc., Softlayer Technologies, Inc., Yahoo! Inc.. (Attachments: #1 Affidavit, #2 Exhibit 1, #3 Exhibit 2, #4 Exhibit 3, #5 Exhibit 4, #6 Exhibit 5-1, #7 Exhibit 5-2, #8 Exhibit 5-3, #9 Exhibit 5-4, #10 Exhibit 5-5, #11 Exhibit 5-6, #12 Exhibit 6)(Chaikovsky, Yar)

Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Doc. 284 Att. 5

EXHIBIT 4

Dockets.Justia.com

111111

11111111

III

11111

11111

11111

lIft

11111

1110

11111

11111

11110111

11111

III

US005287499A

United States Patent
Nemes
FOR METHODS AND APPARATUS STORAGE AND INFORMATION METHOD OF RETRIEVAL UTILIZING AND DIFFERENT COLLISION HASHING AVOIDANCE SCHEMES DEPENDING UPON CLUSTERING IN THE HASH TABLE
Inventor Assignee Richard
Bell

Patent

Number
of Patent

5287499
Feb 15 1994

Date

4695949 4764863 4866712 4922417 4961139 4979105 4996663

9/1987 8/1988 9/1989 5/1990 10/1990 12/1990 2/1991

Thatte

et

al III et at

364/200 364/200 371/5.1

Silverthorn

Chao Churm Hong
et et al

364/200 364/200 395/575 364/900

al al

Daly ci Nemes

Nemes

Brooklyn Research

N.Y
Inc Knuth
Sorting

OTHER PUBLICATIONS
The Art of Computer Programming vol and Searching

Communications

Livingston Notice

N.J
of the term of this patent
to

AddisonWesley
and

Reading Pren

The

portion

Mass

subsequent disclaimed

Feb

26 2008

has

been

1973 pp 506549 Kruse Data Structures

Program

Design

ticeHall

Appi
Filed

No

702444
Types

Englewood Cliffs N.J 1984 PP 112126 Stubbs et al Data Structures with Abstract Data and Pascal BrooksCole Publishing Monterey
1985

May 16
Related of

1991

Calif

pp

10336

U.S
Ser

Application

Data

Continuation

No

326976

Mar 22 1989 aban

Lee Primaiy ExaminerThomas Assistant ExaminerPaul Harrity or FirmLeonard Charles Suchyta Attorney Agent James Falk

doned Int
Cl.5

GO6F
395/600 371/5.1 364/962 364/962.1

12/00

ABSTRACr An
apparatus for

U.S

Cl

395/700 364/963

performing system
In
is

storage

and

retrieval

in

an
the

information

364/DIG
hashing
Field of

storage

disclosed to

which

uses

technique
operation

order

provide
loading

efficient

and

Search

395/700 364/900

600 800
371/5.1

graceful the

under

varying
collision

conditions

system shifts between

avoidance
the load

by
is

linear

References

Cited

probing with open threshold and
load

addressing

when

below
chaining deletion

U.S
3704363 4339657 4380067 4564944 4638426 4663620 4680700 4680703

PATENT
7/1982 4/1983 1/1986 1/1987 5/1987 7/1987 7/1987

DOCUMENTS
et ci al et al
al al

collision
is

avoidance threshold
are

by external
Insertion to

when
371/5.1 371/5.1

the

above

11/1972

Salmassy Larson

and retrieval
cally the the

operations the

arranged

switch dynami stratagems measured
as

between
local

two

collision

avoidance system
to the as

Beardsley Arnold
et et al Ct

al

371/11.2 371/37

loading factor of
records

on

the

by

number

hashed

same

Chang
Paul
et

364/200 340/825.5 crosses preselected

address

thresholds

Hester Kriz

al

364/200 364/200
DELETE

Claims

Drawing

Sheets

DEF00004O5O

U.S

Patent

Feb 15 1994

Sheet

of

5287499

FIG

15

I0

FIG

DEF00004O51

U.S

Patent

Feb 15 1994

Sheet

of

5287499

FIG
RETRIEVE

NO

DEF00004052

U.S

Patent

Feb 15 1994

Sheet

of

5287499

FIG
INSERT

YES

NO

58

DEF00004053

U.S

Patent

Feb 15 1994

Sheet

of

5287499

FIG
DELETE

AR
-6O
HASH

SEARCH
KEY
-61

DECREMENT
CELL

COUNT
-62

-__NOER
TABLE DELETE

YES

REMOVE RECORD

RECORD
-68

FROM LIST

NO

COU

65

YES

CHANGE TO
TABLE

FORMAT
67

DEF00004054

5287499
cord
position
is

encountered

results

in

removal

of the

AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL UTILIZING METHOD OF HASHING AND
DIFFERENT DEPENDING COLLISION AVOIDANCE SCHEMES UPON CLUSTERING IN THE HASH TABLE
is filed

METHODS

record to be deleted Deletion problems
discussed
in

of this type are
Structures

considerable

detail

in

Data

and

Program

Design by

wood
tures

Cliffs

N.J

1984

Kruse Prentice-Hall and Data pp 112126
Types and

Engle
Struc by

with Abstract Data and Calif

PASCAL

Stubbs

Webre
1985 technique
for this
all

Brooks/Cole

Publishing

Monterey
This application
continuation

pp 310336
resolving collisions
is

of application

Ser
10

Another
external position

called table

No

07/326976

Mar 22

1989

now

abandoned

chaining
is

In store

technique

each
to

hash
that store

TECHNICAL FIELD
This
retrieval invention relates to information storage to the to

able

to

records hashing
linked
list is

loca
the table

tion More and
actual

particularly

used

to

records outside then
list is

of the

hash

table to

The hash
the

systems and of
the

more

particularly information

dynamic
optimize
15

entry
linked

no

more than
list is

pointer
itself

head

of the

reorganization access in

stored

The

linked

searched

sequentially
is

such

systems

when

retrieving

or storing
pointers
list

record
to

Deletion

accom
deleted

BACKGROUND
Information
storage particular or data

OF THE INVENTION
stored
in

plished

by

adjusting the linked

eliminate

the

record from

computer-controlled by searching
for 20

The
has the

linear

mechanism key in the matching

can

be retrieved records
search require

advantages

probing with open of simplicity disadvantages if records of the
are of

addressing

technique
storage

and

minimal

stored the

The
is

stored

record

accesses but the
deleted records the

contamination marked
deletion the

due to
as

with Such

key

key

then

retrieved accesses or

merely

de

searching into In the

techniques storage

repeated to

leted
rithms 25

overhead
as

more complex
and under high load of

algo

probes

mechanism and

perform key systems
search

com
such algo

such

Knuths
has the

algorithm

precipitous factors

parisons searching
rithrns sive

large
if

storage

retrieval

degradation
ternal

of operation

Ex

even
as of

augmented search

by

efficient

chaining

advantages
storage factors

simple

deletion

such

binary

often

requires

an exces

algorithms
operation

readily

extendible load
all is

size

and graceful
neither

amount

time and

under
is

high

Thus
the

ap
and

Another
storing involves

well-known
retrieving use

much

faster

method

for store 30

proach

and

information so-called also

from computer

optimum for The problem then
of access
little

storage to

and

retrieval

systems

provide

simplicity

the

of
are

hashing
called In

techniques
scatter-stor

speed
involving the

of linear
or

probing
but

techniques taking

for loads

These

techniques

sometimes techniques upon

no collisions
operation

advantage
chaining to
rise

of

age or key-transformation hashing tion to called
to the

system using hashing
storage
is

more
for

graceful loads

of external
collisions

tech above

key

is

operated
storage

by
in

func space used with
or
in

niques 35

which

cause

produce
the

address

the

some
It

preselected
is

threshold
that the

hash
the

table
desired accesses

This storage
storage or

address

then

also

well-known
is

frequency

of retrieval
this

access

location than are

directly sequential described

of some quency

records data
in is

fewer
binary the puter

storage

probes
techniques entitled

much higher than others If known ahead of time the data
storage

fre be

can
the

searches
text

Hashing by

organized
40 trieval

the

system

to

minimize

re
for

classic

Knuth

The Art of

Com

time of the by placing
or
at

most frequently such records chain

accessed
at

records
initial

Programming 506549
functions

Volume
are

Sorting

and Searching

example
position optimal priori 45 real

the

hashing such an

pp
verse

Addison-Wesley

Reading
to

Mass
translate

1973
the

the

head

of the

Unfortunately system requires
of retrieval

Hashing of

designed

uni

organization

of the storage of the frequency and

keys
the

into

addresses table

uniformly hashing

distributed operations

knowledge problem

statistics
is

throughout
include

hash

Typical

in storage

retrieval

systems

the

truncation

folding

transposition

and

modulo
is

optimal
priori

organization
is

of the
available

storage

space
the

when

no

arithmetic

disadvantage one
causing

of hashing
into

techniques the

that

knowledge

concerning

frequency

more

than

key

can

translate
in

same or

storage retrieval strategy so

of retrieval

statistics

address

collisions

storage

operations sometimes vided forward empty
latter
is

Some form of
called the
initial

collision-resolution

SUMMARY
In

OF THE INVENTION
illustrative

rehashing
simple storage will

must

therefore

be pro
searching the
first

accordance
these

with the and
other

embodiment
are

of the by can or
for

For

example
the

strategy address the

of
to

invention
using dual

problems

overcome which
stored

from

storage

organization

techniques
data
is

storage

location
is

resolve

collision If the

This
55

be

selected
in

on
the

the

fly while
space hashed to
In

being

technique
to

called

linear so to

probing
that

hash table
the table

accessed

storage
is

particular

the position

key

considered
of the

be circular

addresses

beyond
of the

each new hash same
sion 60 table

record
If

particular

in the to that colli

end

table

map back
probing
is

the

beginning

the
is

number

of records

hashing

then the i.e with event

linear the

done
table

with
as

open

addressing space
in the
is

position
is

below

preselected

threshold open
to

the

entire

hash

overflow

resolved the

by linear

probing under

address
that

that

collision

occurs
the

Deletion record
deletion as as

of

records

ing

Once
to

number of records hashing
above
the

same

accomplished
leaving
it

by marking place
or

deleted

but

position

rises

threshold
are

all

of

the

records
the

in

by some

algorithm

One

hashing
table to 65 the the

that

position

removed

from
leaving

hash

such

deletion

algorithm

known

Knuths

deletion

and

linked

by external
chain
in

chaining
the

pointer

algorithm
ate

operates

by recursively encountered

moving

an appropri record

head

of the

hashed

position

When
below
that
is

one

of

the

next

occupied
deleted
as

number
threshold

of records in the external

chain drops same
threshold

positions tion

into

the

now
that

empty
next until the

record posi

not
the

necessarily

the the

and

marking
this

record position
first

empty
re

caused
stroyed

external

chaining

external to the

chain hash

de
and

Iterating

procedure

unoccupied

and

records returned

table

DEF00004055

5287499
the

records

stored

there

using the
this

linear

probing record

under

Central accesses cesses units

Processing
disk

Unit

CPU
unit 12

10

also

controls
in

and

open

addressing can be

Any
used

of
in

known

deletion

controller stored storage are

which
or In

turn

ac

techniques dual storage

dynamically
in

combined hash
table to the

digital

data disk data

on
unit stored

one

more normal

disk

storage

system
contain

Each
either chain

position

the

such

as

13
on
this disk for

operation
unit 13

therefore

can an

record or which can be

pointer

programs
until

and

disk

storage

head
for

of

external

distinguished

required data are

by

CPU
in

10 At
from
11

time

such

programs
unit 13
in

example

by

one

bit

flag

and by maintaining holding the hashing
therefore
in

retrieved

The above
each
position

system can be simplified
of the

blocks

and

stored

RAM
Unit

storage rapid 10

access
also controls in

hash table
records table

field

count
to that 10

Central

Processing

of the
position sents old
is

number
in

of

heretofore

Input-Output
vides access ray to

10
tube such
for

CPU
14

an

controller

which
devices well as

turn
as

pro

the

hash

This count
chain

repre thresh

plurality terminal

of input

such

CRT
of

the

length

of the

external

when

the

cathode

15

as

plurality 15

exceeded
reorganization

output devices of the
the of storage space

as printer

16 Terminal
operator to
the

provides in of

This dynamic
storage

of
15

mechanism
structions

computer
into

introduce system
other

and

retrieval the

system has
time the

decided

advantage of

and and such

commands may
be card and
readers printer results

computer with

of optimizing
load tered load linear factors

retrieval

records regardless overhead
until

FIG
devices

supplemented
tape

input

Moreover

higher
is

encoun
higher
that

as

readers remotely located other types of input

with external
factor

chaining

avoided
collisions

the

terminals vices
20

optical

and 16

de
for

higher

number of
will for

suggests

Similarly the

provides
operation

mechanism of the

probing times
loadings

deteriorate

substantially the

The
overall

displaying

of the

computer
16

threshold niques

switching
selected

between
to

two tech

system of
similarly tube other 25

FIG

for the

computer

user Printer

may
ray

are

of

course
of the

optimize

the

be supplemented

by line printers
graphical

cathode
plotters

performance

combined

system

displays types of

phototypesetters output devices of the

and

BRIEF DESCRIPTION
complete understanding by
considering

OF THE DRAWING
of the the present following the invention detailed

The
and
art

constituents

computer
are

system

of

FIG
in

their

cooperative
typical of

operation
all

well-known systems frame

the

may

be

gained
in in

and

are

computer main of no such

from small

description

conjunction

with

accompanying

personal architecture

computers and
since not there

to

large

systems
are present

The
well-

drawing

which
general

operation

systems of the here

FIG
storage

shows

block
in

diagram which

of
the

computer
information invention

30

known
vention
In

and
will

they form be further
is

part

in

system hardware and

arrangement system

described graphical for

retrieval

of the

present

FIG
as that

shown

representation

of

can

be implemented shows
general

typical

software architecture

computer
of for than

system

FIG
system
storage will find

block
in

diagram which

of the

computer
information invention 35

such

shown
access

in

F1G
mechanism

The software
20

FIG
simple

software arrangement and use shows procedure
linear general in retrieval

comprises
personal ing the

an

which
no more

system

of the

present

computers system

may comprise
In larger

turn

on

systems and

providing password
in

service

FIG
trieval

flow

chart

for

record re

to

larger

number

of users login

dynamically
external

reorganizable
storage

com
re
40

dures would nism 20
login

typically access the

be implemented mechanism
user
is

access

proce mecha
the

bined
trieval

probing
in

chaining

and

Once

20 has placed
in

completed
the

system

accordance
general in the

with the present
for

invention

procedure

operating

FIG
tion storage

shows

flow chart

record inser
dual

system
nates the 45 the

environment
activities of

21
all

procedure

dynamically and

reorganizable system
in

Operating system 21 coordi of the hardware of components
in

technique with the shows
in

storage

retrieval

accor

computer of

system shown programs

FIG
of for

and

provides
use to the

dance

present

invention flow

and
for

number computer
assemblers
file

utility

22

general

FIG
tion storage

general the

chart

record dele
dual

user Utilities 22 might and compilers and

example

comprise
basic

procedure

dynamically and

reorganizable system
in

mathematical

routines

technique with the
facilitate

storage

retrieval

accor

handling routines computer

system maintenance system of

facilities typically

dance

present reader are

invention understanding
to designate identical

The
refer
50 also

software

FIG
programs

To
ence
to the

includes

plurality

of application

such

as

numerals
figures

used

elements

common

application

software 23 24
for

25 Application software
comprise package an editor
data

2325
sheet

might

example
graphics

spread

DETAILED DESCRIPTION
Referring

program
and
so

base

man
23 of
is

ager more
is

forth Each
or

of the

application to

programs
plurality
It

particularly general

to

FIG
Central

of the of

draw

55

through

25 includes

provides access

ings there
puter

shown
10 and

block

diagram

com

programmed
the ally

processes

26

27
26

28
through
to

respectively

hardware

system comprising

Processing

Unit
unit

CPU
by by

Random
programs

Access
stored

Memory
in the

RAM
11 are
at

programmed
perform of
the the

processes tasks

28

which
out the

actu

necessary

carry

11 Computer

RAM

pur
In

pose
60

corresponding
effective use able
in

application

program
application the

accessed

time

CPU 10 and CPU 10 Data
are

executed
stored
in

one instruction
other portions

order to ages
the
at

make
user the

of these
to

pack
processes to

of

must time

be and

execute sequence

RAM
tions

11

operated by

upon
10

by

the

program

instruc
in

2628 The
65 storage

the

accessed

CPU
course

from
data

RAM

necessary

11

all

accor

accomplish

the

users goals
invention
is

dance

with
10

well-known
of

processing multiple units
all

techniques
processors

present

concerned Such

with

information

CPU
and caches

may
data the

comprise

and

retrieval

systems

system

would

interact for
in

with multiple and/or

memory
art

11 as
is

by way
also

of

form one

of the

application

software packages
processes storage

23 24
which system

instructions

well-

25

of

FIG
the

The

various

262728
retrieval

known

data

processing

implement

information

and

DEF00004056

5287499
are herein disclosed as
It

as

flow charts
in

and

shown
of the

pseudocode
is

the the

in FIGS APPENDIX

and
to this

storing but

records

randomly
in

in

any available
pointer

storage to the

space
location

maintaining next to to

each

record chain

specification tion these the

believed

that

creation to

and execu
carry skilled out
in

of the hashed
is

record in the
the

When
pointer If the

search
located

key
there

is

computer
are

programs
readily

necessary
to

hash

table
first

entry

the

processes

apparent
present

those

used

locate
this

the

record

search

key does
is

programming

art

from the

disclosure retrieving data

not

match
to

record
the

the

pointer

therein In

contained

Many fast techniques are known in the prior
space
is

for storing art In

and

used

locate

second
is

record

this

way
until chain

the the
is

situations to

where

storage

chain
desired 10

of records record
is

traversed or until next adjusting

sequentially the

considered
called

cheap
is

relative often

retrieval In

time
hash-

located to

end

of the

technique ing each

hashing
in

used

classic

reached cords
the

no

pointer

record
the

Deletion
to

of re bypass

record
particular for

the
field

information called the

storage

system in
is

simply involves record
chaining

pointers

cludes the basis

key which
the

used

as

delected

storing

and

retrieving

associated

re
15

External

has

numerous

advantages
is

over

cord
function
in

mathematical
translates the

function

or

map

called

hashing
or address

key into
called the

cell

number
table

The delection open addressing does not leave records in place
over
not the
in

procedure which

simple and

must be searched algorithm
the size
is

the

storage

space
is

hash

Taken
circular storage

as
list

future

probes and

if

Knuths
records

deletion

whole
of
called called tion

hash table

logically

contiguous
fixed-size

used hash

The number of
table the

can

exceed

of

consecutively cells

numbered
capable which
of

units

can

be

expanded Indeed

readily storage

without space
as

each

storing function in

single

data

item
20

changing
for

hashing can

function be

record on
or the
less

The hashing

can

be any operaaddresses the

new
to not

records Most

allocated the for

dynamically hashed
in

key

results distributed functions

hash

table

needed
quired

importantly
searches

number of probes
particular increases the the

re
key

more
table

evenly

throughout
include

hash

conduct
rise

Known
of these not

hashing

truncation and combina hashing
funcin

does
load 25

precipitously In

with

table table

folding transposition
tions tions

modulo arithmetic
Unfortunately unique what

factor

an open
the

addressing

system
of

as

operations always
is

loading to locate ing level

grows
the

average

number

probes

necessary

do
table
cell

produce

addresses

the the

particular

record also
operation

grows
of the

At some
retrieval

load sys

hash same

That

many

distinct

keys can
are

map
is

into

successful

number producing
of
all is

called

collisions therefore of 30

Some form
required collision tion
in

collision

resolution

strategy In

tem collapses precipitously On the other hand linear
dressing has distinct

probing over

under
external addition

open

ad

hashing

systems
to find the

every

instance storage

advantages
load factors

chaining
storage

it

necessary

an empty

loca

under

more moderate
fields
is

The

somewhere
alternate

else to store storage

new record Moreover
must be
for readily the

for pointer

avoided
the

along
pointer

with the chains
If

processing the table
is

such
able

locations

reach

overhead

of following
in

during future

probes

searching

displaced 35

implemented page
faults

virtual incurred

memory
to

minimal number of
since the

record

are

during record access be accessed
or

Two
the

forms of collision
art

resolution called

are

well-known Under due

in

portion

of the

hash table
locations

occupies

contig

prior

The

first

is

open

addressing occurs
cell

uous
In

storage

on one

two pages
invention open
in the the

open

addressing
different

whenever hashing
to

collision the
is

to

accordance
of

with the both

present

major and

two

keys

same used

number
linear takes
cell

advantages
40 external

techniques
are these

addressing

technique probing place hashed record
in

called

linear

probing scanning
the the next

Under
cells

chaining
particularly

achieved

same
are

sequential

of storage
cell

More
in

two
on

techniques storage

system combined
selected load table

beginning to
is

with
treating
in

following as
cell

the

one system

and the

actual

strategy current in the

is

and

hash

table

circular

The
45

dynamically
factor using

depending
all

the are

then stored

local

stored

the

first

unoccupied of the
the

encountered
is

Initially the

records

hash

the

linear

probe key
is

Retrieval

record
cell

similar
If

open
the

addressing local load
shifts

with
factor

linear

probing

tech

The
the the until cell

search

hashed found

to there to

initial

number
not

nique

When
the

exceeds
to

preselected the external

record
linear the
is

is

not

the
access

keys do
all

match
cells

threshold
chaining

system

dynamically

probe record

is is

used found

successive If

technique
the local

That
load

is

while inserting
as reflected

or deleting
in the table

the

keys

match
and
the

an

empty
the re50

record
ber

factor
to this

num
cell
is

encountered
is

during
in

this linear base

probing

of records hashed
If this to the in

same

hash

cord

sought
as

not

the

data

process

ter of re

examined cords

number exceeds
this
cell

threshold
are

the

minates cords

an unsuccessful open
cell cell

search

The

deletion either

hashed

address
itself

reorganized organized store
into

re re
an such
the

under
the

addressing as

involves or physically
cell

merely
the 55

moved from
external chain

hash

table

and

marking
contents continuity algorithms
in

deleted
fill

moving

another

part

of the

While

of
of

to

the

deleted

and maintain the
deletion disclosed

reorganization

involves in

considerable searches search

overhead where time
It

the

probe

path

The
of the both

preferred are

payoff comes
chaining

subsequent reduces
the the

the
is

external

called

garbage
applications

collection

greatly that

the

copending 151638
to

present
filed

applicant 1988
as

of course ceeds
60 the

frequency

of retrievals and most

greatly

Ser and Pat 1992

Nos

and

151639

Feb
issued

frequency which systems
holds

of insertions
true for

deletions data

assumed ex an as
and
list

assigned

applicants assignee

now

U.S

sumption
retrieval causes

storage linked

Nos 4996663
respectively

Feb 261991

and

5121495

Jun

When
length to

deletion
fall

from

the

chain the the the

below
that

threshold
triggered the entries

not chain

second
called
cell

general

technique Under

for collision external stores

resolution

is

necessarily

same
chain
is

threshold

external in the

chaining
table
is

chaining
all

each
65

formation sorbed
In into

destroyed

and

reab

hash

effectively

of the

collid table

hash

table

ing

records

This
cell

accomplished of Such

by making
to the are

each head

further

accord

with

the

present addressing

invention and

the

entry linked

each
list

consist

pointer linked

of by

dynamic
chaining

shifting
is

between by

open

external

of

records

lists

formed

facilitated

maintaining

record

count

DEF00004057

5287499
field in

each

occupied each time

hash

table

cell
is

This hashed

count
to

is

search the

key

of the

record to be inserted produced
the
cell at

is

hashed hashing
is

Using opera incre

incremented same
cell

new

record
time

this

hash

table

address
field in is in

by the
that

and

decremented
cell then
is

each
deleted

record
data

which base
for to

tion the mented
tered tents
cell

count by one

location

hashes to this same

from the on
in

box

52

Decision

box
or

53

is

then
the

en con

The

count
or

field

is

consulted the value

each
this

access

where of that
is list

it

determined
is list

whether
If the

not

insertion

deletion

and
the
in

field

used
strategy

cell

pointer 54
is

contents to

of the
the

dynamically
to

determine
entry

collision

resolution
cell

pointer
external chain

box

entered

add

new
by
then the

be used

Each
includes

the

hash table

also

advan
table
10

record to

the the

chain
to
its

This

is

accomplished
is

tageously entry
is

flag

indicating to there for

whether

the

walking
added

end

The new record
pointer but

record or
to

pointer

an external
is

chain flowchart from with reso

at the

end of the
in

chain

by placing
last process

to

Referring then of
data the retrieve storage present

FIG

shown
records

new record
record
terminal
in

the

previously

now penultimate
terminates
in

algorithm and
retrieval

retrieving

the

chain

The

then

system

in

accordance
collision

box

58
to
is

invention

and involving
selected
at start
is

dual

Returning
15

decision

box

53

if

the

contents 55
is

of the
entered

lution

schemes
In

dynamically
starting the search

depending box

on load box
31
is

hashed where
threshold

cell

not

pointer
is

decision to

box

factor
entered

FIG

30

the

cell

count
If 57 the
is

compared count where

numerical upper
not

where hashing

key

hashed
location

using

any

To
box
the to

cell

does
the

exceed

this
is

known
cell ined In to

function
operation

The
is

cell

resulting

threshold added
20

entered using then

new
linear
in

record

from the hashing
decision

used

to access

hash table
cell
is

hash

table

standard terminates the

probing box
in

box 32
if

the

contents
cell

of the

exam
or

techniques

The
cell

process

terminal threshold
all

determine
to flag the

the

contains

record

58

If

the

count

does
is

exceed
entered

Tu

pointer one-bit tively guish

an can

external

chain

As
for

previously

noted Alterna
to distin 25

decision

box hashed

55 box 56
to
this

where
table linked

of the
are

be

reserved

this

purpose be used
or the the

cords

same an

hash

address

re re

length

of the records

contents

can

trieved
pointer

formed
to
is

into chain entered

external
in

chain
cell

and

between
to
list

and

pointers
If

contents

that then

placed
to

the the

hashed

address
at

examined
cell
is

make

this

decision box 33
is

Contents to In

of the
the

Box 54
nal

place

new
the

record
in

the

pointer
list in

entered

search

end of that chain box

The

process

then

terminates linked table

termi
list

external

linked records the

for the

matching
linked
list if

key

decision to
is

box ascer
30

58
no

The

process

of forming
the

in

34
tain to

the
if

are

examined box 37

volves

more than
finding storing that

retrieving free
first in

hash

records
for placing finding the

keys match
the contents

and of

they

do
38

entered

using
first

FIG
to

storage

location

return
is is

the in

matching box
list If

record no
is

The

record

the

record there
the

and
cell

process

then

terminated
in

matching
entered to

pointer

location

hash
for

table the

record
return the

found message

the

linked the
in

box 35 was

another
storing 35 that the

free the

storage

location

second

record
pointer to
If

that

search

unsuccessful

and

second
location
cell

record there
in the originally previous
in first

and

placing

process

terminated to table decision
cell
is

box box

36 32
if

second hash

record

and

so

forth

Returning
initial

the

contents

of the box 39
is

table

stored

record that hashes then
that

hash
to

not the

pointer
cell
is

decision
If

elsewhere

from

probe
to

record
for the

entered

determine 35
is

if

empty
an

the

cell

is

must be relocated pointer
again

the the
is

hash table open

make room
of box 61

empty
search the
cell

box

entered

to

return

unsuccessful
in

using there

addressing

technique record
is

message
is

and the

process

terminated

box 36
to

If

40

In

FIG
where
cell

shown
at
is

flowchart
start

not
if

empty
the

decision of the

box 40
cell
is

is

entered
list

again

deletion tered table
cell

process
the

Starting search In

box 60
to

en
that

determine
is

contents

pointer
logic
is

This path

key

hashed
the
cell

provide
field at

hash

necessary
cell

because does
to then

of later iterations
list cell in

of

the

location
is

box 62

count

If the to

contain the next

pointer
the

box 42
table

entered

location entered
cell is

decremented determine
list

by one whether
If
it

Decision
or not the

box

63

is

advance
is

hash

Decision

45

then

to

contents
is

box 39
If
it

re-entered
itt

of that
decision
list

pointer
table

is

not box 68 algorithm

entered

is

determined
cell is

box

4.0

that

the

contents

to
is

use

any

known

deletion

to

remove
the

of the current
entered the

not

pointer
is

decision to
is

box 41
the

the

record from the

hash table

where

the
If

search

key

compared box 37
process
in

key

in

record can
50 or

merely be marked
deleted

As previously deleted and
by some

noted
left in

place as

current the

cell

match

occurs
the

entered terminated

to

can

by physically algorithm determined
is list

algorithm

such

return in

matching
If

record and does
next not
cell

Knuths
is

The

process

terminates

in terminal

box 38
to

match
the

occur
in

box 41 hash

box 42

box 66
If of 55
it

entered the

access

the

table until

Thus
either

is

in decision

box 63 that the
is

contents the
list in

linear

probe
cell
is

of the

hash

table

continues

the

cell

pointer
is

box 64

entered the the

where
linked pointer to

an empty matching
containing
It

encountered encountered
are the

key
list

is

cell box 39 or box 41 Intervening

with
cells

record This
the the
is

to

be

deleted

removed

from

easily

accomplished
the

by adjusting record to
the

pointers that the

passed retrieve

over

box

40
of
it

chain the

just before

be deleted
to

point

can
to the

be

seen

process

FIG
is

record space
to

following
thus

record

deleted
then

The
be
to

serves

locate

target

record whether
process or

stored 60

storage returned

of the

deleted
space
for

record can
future

under
chaining

open

addressing

under
of

the

external

free storage

assignment

process
that the

The

retrieve

process

FIG
stored

as
using

another

record
the
is

sumes
the cess

record has
storage that

previously strategy
this

been

Following
sion
is

removal where

of

the the

record

in

box 64
cell

deci count count

most of

efficient

The
is

FIG
then

insures to

choice
is

pro properly made
flowchart
out In of the 65

insertion

box 65

entered to

decremented

compared
not equal

another
less

lower threshold
this

TL

If the the

Turning

FIG
process

there

shown

is

to or
in

than

TL threshold
the

process

record insertion
dual storage
at

suitable

for carrying

terminates
is less

terminal equal

box
to the
list

scheme
start

of the present

invention
is

FIG
the

than where

or

If however TL threshold
is

cell

count
is

box

67

en
re

starting

box

50

box

51

entered

where

tered

the

linked

disassembled

and

the

DEF00004058

5287499
10
cords added niques
It

to

the

hash table
then the

using

linear

probing tech box 66 and hashed
is

different

forms of deletion correspondence and here
also are

are

included

in the the

APPEN
and be
further

The

process that

terminates processes collision

in terminal of

DIX
FIGS

The

between and

listings

can

be seen
to

FIGS
resolution

obvious

will

not

cooperate
storage

provide

dual the

described
It

system where

form of collision

resolution

should

be clear

to

those

skilled

in

the

art that

determined
local deleted load

dynamically
factor the
at

on
time

the

fly

depending
are to

on

the

further

embodiments
those skilled

of the
in

present art

invention departing

may be
from

the

records

be added
for for

or

made by
the

the

without

from

system

Pseudo-code

listings

each

teachings

of the

present

invention

of these

processes

together

with pseudo-code

two
10

APPENDIX

Formal Definitions

COfl St table_size

size

of hash

table

const const

upper lower

threshold
thres hold

used by insert for conversion /s
threshold

to to

chain structure
table structire

SI 1/

used

by

delete

for conversion

lower type list_element_type

upper

threshold

record record_type pointer
to

record_contents

next lust_element_type end
type table_element_typerecord

next node in linked

list

count

integer
to

number
this cell

of stored

keys

that

hash

status case

empty occupied deleted
thi
list

stiucture

of

type of data structure
that

currently

storing

records

hash

here

tbl record_contents
list

record_type

list_head

lust_element_type

end
var
Initial state

table

array

table_size-li

of table_element_type

hash

table

of each element of table

count
status

empty
tbl

structure

Retrieve

Algorithm

procedure
var

retrievc

key

key_type

table

size-i

continue

boolean

DEF00004059

5287499
11 begin 12

hash
if

key
list

table
then
else

search linked begin true

list

pointed

to

by table

head

continue while
if

rable
then
if

table
then
else

emply

and continue

do occupied

table
continue
false

tbl and

table
key

mod mod
empty
table

table

size

else

size

if

table
then
else

not

found

found
else

end end

begin

Insert Algorithm

procedure
var
list

insert table

new_record
size-i

record_type

element_type

used

for constructing

chain

begin

hash

new

record

.key

table
if

table
list

table
then
else
list

insert

table
convert

new

record

if

table
begin nil

upper_threshzld
to

then

linked

list

initialize for while loop

ji
while

table

empty

do
to

traverse sequence linked
list

of records

and add
begin
if

tablej.stiucture then
if

hash then

table
tbl and table

occupied

begin

list_insert

table

.record_contents

DEF00004O6O

5287499
13 knuth
delete

14

end
elsej

mod

table

size

elsej
end
list_insert
if

1modtable_size

/while/
new record
occujied
table_insert

table

then

hash

tbleble a ta
contents

else

table
table
end
else table
if

table
list

occupied

head
else
if

then

begin

convert

to linked

list

insert

new_record

end

Delete Algorithm

procedure var

delete

key

key_type

table_size-i iist_element_type used
for traversing

chain

continue begin

boolean

hash

key

table
if

table
list

table

then

begin

delete
list

from linked
to by

list

search linked

pointed

table
list

and remove
if

record

whose key matches key
threshold linked
to table

table lower
then begin

convert

resident entries

table

head
tbl

table
knuth_delete while begin tale_insert
nil

do

hash

p1.record

contents

.key pI.record
of element pointed

contents
to

remove

from linked
to

list dispose
list

byp

and advance

next

element

DEF00004O61

5287499
15 16

end end end
else
If

then then

begin begin

convert

linked

list

to

table

resident entries

delete from linked
table resident

list

begin

delete true

entry

continue

while continue
if

do
tbl

table
then
if

and

table
key

deleted

table
then continue

contents.key false

elsei
else

imodtable

size

mod
mark
else

table

size
delete

invoke

deleted begin

or knuth

end end

/S

delete tablezesident entry

Mark
procedure
begin

Deleted

Algorithm

mark

deleted

table

size-i

table
endR

deleted

Knuth

Delete Algorithm

procedure

knuth

delete

table

size

Delete

cell

from hash

table

procedure

recursive_delete cell

table_size

Delete begin
if

instead

of cellj

if

required

recursive_delete
is

cell

marked
cell

empty empty
hashes
at or before

then
else

mark
if

record then

in cell

position

begin

contentsj
recursive delete

contentsk mod
table size

end

then
delete

elserecursive

mod

table_size

end

recursive

delete

begin

knuth

delete

DEF00004062

5287499
17
recursive delete delete

18

mod

table

size

end

knuth

List Insert

Algorithm
type new_record record
in it

procedure
/S var begin

list

insert

varp

lust_element

type
to

Allocate

list

element

put new_record

and

link to list pointed

byp

list_element_type

new

allocate

list

element

q.record_contents
ql.next

new_record

end

Table

Insert Algorithm

procedure

table_insert in table

table_size-I new_record record_type
at

Store new_record

or ahead of position

begin while

table
table
end
What
is

table

occupied

do
record

mod

table_size

new

occupied

claimed

is storage portion storage

when
and
retrieval data

said to or

collision greater

count

in

said

storage

means

is

An
data generating

information
using

system

for

equal

than said
storage

preselected retrieval

threshold system

records

of each said
address

record for
said

The information
cording to means
claim for

and

ac
said
is

hashed

in said

system

further

comprising of said
data said

system

comprising means of
said for data storing records collision

storing storage

one

records
collision

at

storage
set

count
identical

for

each

so

hashed below

address

when
and

count

having

hashed

said

preselected storage further

threshold
retrieval

storage
first

addresses
responsive to said storage

The
means
for

information

system

ac

means

lo

cording to claim means
55
at

comprising
to

cally said

resolving collision

collisions

by open
storage

addressing

when
is

for storing said
at

pointer

one

of said
address

data

records
said

count

in

said

means

below

said

hashed
is

storage to

when

preselected

threshold
responsive

and
to said storage external

collision

count

equal

or greater

than said

pre

second
locally

means

means

for

selected

threshold

resolving

collisions

by

chaining

60

65

DEF00004063