A hash table construction method and system for non-volatile memory

Abstract

The invention discloses a hash table construction method and system for a nonvolatile memory. The hash table construction method is characterized in that a hash table is constructed and is logically constructed into an inverted complete binary tree, all leaf nodes of the binary tree are addressable units, and all non-leaf nodes are unaddressable units and serve as standby units for the leaf nodes to deal with hash conflicts; all the non-leaf nodes on a path from the leaf nodes to root nodes are used for storing conflict elements of the hash conflicts at the leaf nodes; furthermore, a plurality of layers at the bottom of the binary tree are deleted, and only rest layers at the top are remained; and each element in the hash table corresponds to two different hash positions which are obtained through computation by use of two different hash functions. The invention also provides the hash table construction system for the nonvolatile memory. According to the technical scheme, the constructed hash table cannot cause any additional writing, and high space utilization ratio and low request delay are achieved.

Description

Technical field [0001] The invention belongs to the field of computer data storage, and more specifically, relates to a method and system for constructing a hash table for non-volatile memory. Background technique [0002] Traditional memory technologies DRAM and SRAM have been widely used in the memory level of computer systems as main memory and on-chip cache respectively. However, these traditional memory technologies face problems such as increasing leakage power consumption and limited scalability. New non-volatile memory technology (NVM), such as phase change memory (PCM), resistive change memory (ReRAM) and spin torque memory (STT-RAM), due to its high density, high scalability and close to zero Standby power consumption and other advantages are proposed as a substitute for DRAM and SRAM. However, NVM has certain limitations in write endurance and write performance. The storage unit of NVM can only tolerate a limited number of writes. For example, each storage unit of P...

AI Technical Summary

Problems solved by technology

However, according to empirical analysis and experimental evaluation, most of the existing hash table construction methods will cause many additional memory writes, which is not friendly to the write durability of NVM

Images