HASH表查找效率的討論和驗證

DISCUSSION ABOUT SEARCHING EFFICENCY ON HASH TABLE

摘要: HASH造表、查表方法廣泛而有效地應用于計算機基本軟件和應用軟件的設計中,尤其在計算機的數據處理和數據庫技術中,更為如此。本文使用初等的數學方法對這種先進的查找技術的效率—表平均查找長度A進行了理論上的討論,同樣得到了前人已經得到的兩個理論計算公式。此外,我們還在M—150計算機上做了隨機模擬試驗,得到了一系列試驗結果,支持和驗證了理論的正確性。

Abstract: HASH TABLES are widely and efficentey used for designing a variety of software in Computers, and in special for data processing and data base system.
The efficency of the advenced Searching technology-the average Searching time on the table, A is discussed in theory in this paper. Two theoretic formulas is given and a random on-line test is done using the Computer M-150. The theoretic correctenss is proved by a lot of result obtained.