The complexity of hashing with lazy deletion (Q1087334)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3988731
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The complexity of hashing with lazy deletion |
scientific article; zbMATH DE number 3988731 |
Statements
The complexity of hashing with lazy deletion (English)
0 references
1986
0 references
We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork.
0 references
hashing algorithms
0 references
birth-death process
0 references
Laplace's method
0 references
dynamic dictionary problem
0 references
0.8796195983886719
0 references
0.7596092820167542
0 references
0.7500872611999512
0 references
0.7467168569564819
0 references
