Space/Time Trade-offs in Hash Coding with Allowable Errors In this paper trade-offs among certain computational factors a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency. The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods. In such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to "catch" the small fraction of errors associated with new methods. An example is discussed which illustrates possible areas of application for the new methods. Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time. CACM July, 1970 Bloom, B. H. hash coding, hash addressing, scatter storage, searching, storage layout, retrieval trade-offs, retrieval efficiency, storage efficiency 3.73 3.74 3.79 CA700704 JB February 13, 1978 9:18 AM 1676 4 2033 1682 4 2033 1728 4 2033 1860 4 2033 1860 4 2033 1973 4 2033 1973 4 2033 1992 4 2033 2018 4 2033 2018 4 2033 2032 4 2033 2033 4 2033 2033 4 2033 2033 4 2033 2107 4 2033 2107 4 2033 2109 4 2033 2109 4 2033 2203 4 2033 2203 4 2033 2251 4 2033 2251 4 2033 2359 4 2033 2524 4 2033 2543 4 2033 2543 4 2033 2552 4 2033 2559 4 2033 2573 4 2033 2770 4 2033 2991 4 2033 3053 4 2033 1314 5 2033 1785 5 2033 1786 5 2033 2033 5 2033 2033 5 2033 2033 5 2033 3001 5 2033 2033 6 2033 2139 6 2033