Abstract: Because time overhead of query is O (1), Cuckoo hash table has been widely used in big data, cloud computing and other fields.However, insertion of the existing Cuckoo hash tables generally uses random replacement strategy to replace existing entries when encountering conflicts.On the one hand, writers are prone to high-latency insertion and infinite loops, especially when the load rate of hash table is relatively high, and even have the risk of reconstructing entire hash table;on the other hand, due to existing random replacement strategies, entries are scattered as much as possible in the buckets of hash table.The lack of good spatial locality among entries reduces the efficiency of positive query.To solve the above problems, this paper proposes a Cuckoo hash table based on smart placement strategy.Specifically, in order to improve efficiency of insertion, a load-balance Cuc-koo hash table (LBCHT) is proposed, which limits the load of each bucket in real time, using breadth-first search to find the best Cuckoo path to ensures load balancing among buckets.Experimental results show that LBCHT can effectively reduce long tail effect of insertion under high load rate.And in order to improve efficiency of lookup, a Cuckoo hash table that makes full use of the locality principle is proposed (LPCHT).By fully exploring the spatial Locality among entries, CPU cache miss rate caused by lookup is reduced and efficiency of positive query is improved.Experiments show that in a high load rate stress test environment, compared with libcuckoo, LBCHT throughput of insertion can be increased by 50%, and LPCHT improves positive query efficiency by 7%.

Key words: Breadth first search, Load balance, Locality principle, Long tail effect, Positive query