本文選題：多維 + Hash表�。� 參考：《清華大學學報(自然科學版)》2017年06期

【摘要】：傳統(tǒng)的Hash表通過對目標數(shù)據(jù)進行Hash計算,可以實現(xiàn)數(shù)據(jù)的快速存取與檢索。為了保持較好的存儲性能,需要使整個Hash表保持疏松的狀態(tài),從而犧牲掉10%~25%的空間。這對于海量數(shù)據(jù)存儲而言,是一種巨大的空間浪費。該文提出一種多維Hash表結(jié)構,通過增加Hash表在邏輯上的維度,大大降低了Hash表的沖突率,實現(xiàn)了在較高的填充率下獲得較滿意的性能。實驗結(jié)果表明:在千萬的數(shù)據(jù)量級上,二維Hash表的沖突率比傳統(tǒng)Hash表的減小2~4個數(shù)量級,總體性能則提升了1個數(shù)量級。該文還在原有填充率的基礎上,提出失效率的概念,進一步完善和統(tǒng)一了Hash表性能評價指標。
[Abstract]:The traditional Hash table can quickly access and retrieve the target data by Hash calculation. In order to maintain good storage performance, it is necessary to keep the whole Hash table loose at the expense of 10 or 25% of the space. This is a huge waste of space for massive data storage. In this paper, a multidimensional Hash table structure is proposed. By increasing the logical dimension of the Hash table, the collision rate of the Hash table is greatly reduced, and the satisfactory performance is achieved at a higher filling rate. The experimental results show that the collision rate of the two-dimensional Hash table is 2 ~ 4 orders of magnitude less than that of the traditional Hash table, and the overall performance of the two-dimensional Hash table is improved by 1 order of magnitude. Based on the original filling rate, the concept of failure rate is put forward, and the performance evaluation index of Hash table is further improved and unified.
【作者單位】： 國防科技大學計算機學院;
【分類號】：TP311.12
，

本文編號：2000297