Optimization And Application Of Cuckoo Hash Table

In recent years,the rapid development of the network has put more and more demands on the fast storage,query and processing of big data.Cloud computing servers need to process and analyze large amounts of data in a timely and accurate manner,so an efficient query module is very important for storage systems.Hash table is an efficient data structure that can be stored and accessed immediately.It is widely used in various fields,such as database,network,storage and security.At present,there are many Hash table algorithms such as: Cuckoo Hash,Peacock Hash,Double Hash,Link Hash and d-left Hash.However,there are still some problems in these hash tables,such as too much memory space occupied,too long operation time and insert failure due to an infinite loop in the process of insert,which requires rehashing.In this thesis,the kick mechanism of the Cuckoo Hash table is improved,and the improved hash table is combined with another data structure,Sketch,for data flow measurement and query.This thesis constructs an Odd-Even Hash Table by combining the Hash table with secondary data structure Bloom filters and Bitmaps,and reducing the number of memory accesses by recognizing in advance whether a kick operation in an insert is necessary.The structure is improved on the kicking method of the Cuckoo Hash table,which can realize the operation of storage,search and delete,which effectively reduces the operation time and greatly improves the load factor of the hash table.In the same memory space,the load factor of the Odd-Even Hash Table could be up to1.5 times that of the Link Hash,and the load factor is higher than that of other Hash tables.Memory accesses can be reduced to half of those of the Linear Hash,with the least memory accesses except for the Link Hash.The lookup memory accesses can be reduced to 0.2 times the memory accesses of the d-left Hash,and the Odd-Even Hash table has the least memory accesses except for the Link Hash.In this thesis,Odd-Even Hash Table is combined with CBFSketch to form OEBSA Sketch(Odd-Even-based self-adaption Sketch).This structure could dynamically apply for space according to the size of network traffic to be measured,and Odd-Even Hash Table is used to replace the original Counting Bloom Filter to store the number of Sketches,which improves the accuracy of query.In order to verify the effectiveness and efficiency of the scheme in this thesis,the experiment compares OEBSA Sketch with several typical Sketches and original CBFSketch.The experimental results show that the accuracy of Heavy Hitter is 4 times higher than that of other Sketch,and the accuracy of Heavy Changer is 16 times higher than that of other Sketch.Compared with CBFSketch,the AAE is reduced by about 50%.When the same ARE is achieved,the space used can be reduced by 50%.To sum up,the Odd-Even Hash Table proposed in this thesis can save memory space,reduce the search operation time,and the comprehensive performance is better than other hash tables.OEBSA Sketch improves the accuracy of the original algorithm and saves some memory space,so it is more appropriate for high-speed network measurement.