The Two-layer Hash Structure: A System Which Supports Dynamic Dictionary

With the rapid development of computer network technology as well as the substantial progress in hardware performance, new market demands, particularly in network, have thus come into being. A company in broadband access services asked us to develop software for quick IP address location in broadband access system, since their own algorithm on the basis of dichotomy could no longer meet the demand. As a result, we began our research on a more efficient locating algorithm. Moreover, a similar request was proposed by another company. All these requests greatly motivated our efforts in the research. In more abstract terms, all these demands require a system which can support dynamic ADT dictionary efficiently. The traditional application of dynamic ADT dictionary can be divided into two categories: the first category supports comparison based on element key words values; the other one supports Hash. Considering that most IP address operation is by locating while there is only low frequency of insertion and deletion, the first category is not applicable. The second category boasts for its high locating efficiency. We respectively tried the traditional Open Hash, Close Hash, Perfect Hash and Extendible Hash, etc, only to find out that the traditional hash technology is far from practical, but the potentiality of quick location can be a project for research. A more complex structure, based on the improvement of traditional hash and a combination of their advantages, can be able to meet market demands. On a further study of documents on Hash technology, we notice the localizing function of Hash itself, that is to say, averagely dividing dictionary elements into some compatible equivalence classes in terms of key word hash values and confining conflicts within the same equivalence class. On the other hand, we also notice that the traditional extendible hash can be potentially improved to quickly rehash the elements in the same equivalence class. There is bound to be a breakthrough on this hypothesis.Therefore, we make an exhaustive research on traditional extendible Hash, and successfully structure a two-layer Hash model, which supports dynamic ADT dictionary, by combining the traditional Hash and the improved version. The fruitful results of the experiment are in accordance with our qualitative analysis. The originality of this article lies as follows:After analyzing the disadvantages of traditional extendible Hash and its progressive expanding system, we find that the expanding process can be a non-stop one from the initial stage to the final phase. Furthermore, we also establish a direct relational formula between parameters in the initial and final stage in the expanding process. In this way, the self-adaptive expanding process of traditional extendible Hash is thus shortened, and efficiency of the algorithm is notably improved. A two-layer Hash structure which supports dynamic ADT dictionary is proposed. The first layer employs the traditional Hash, localizing the conflicts among dictionary elements. The second layer employs the above-mentioned extendible Hash, self-adaptively rehashing the conflicting dictionary elements according to the situation. Compared with the traditional open Hash, this two-layer Hash structure enables average time efficiency of the dynamic ADT dictionary to increase by 2 times.