Information processing apparatus, information processing method, and non-transitory computer-readable storage medium for storing program

A method for information processing in a memory that includes a first memory device and a second memory device, the second memory device being greater in latency than the first memory device, the first memory device being configured to store a plurality of lists each being associated with a respective hash value, the method comprising:

• executing a first process includes
• receiving an entry that includes a key and a value,
• in response to receiving the entry, storing the received entry in the second memory device,
• in response to receiving the entry, selecting a first list from among the plurality of lists in accordance with a first hash value, the first hash value being derived from the key included in the received entry,
• in response to selecting the first list, adding a set of a first identifier and a first pointer to the selected first list, the first identifier being derived from the key included in the received entry such that the first identifier is different from the first hash value, the first pointer directly indicating a memory location at which the received entry is stored or to be stored in the second memory device, each of the plurality of lists including neither the key nor the value included in the received entry even after adding the first identifier and the first pointer;
• and
• executing a second process that includes
• receiving a searching request for a value, the searching request includes a searching key,
• in response to receiving the searching request, selecting the first list from among the plurality of lists in accordance with the first hash value derived from the searching key included in the received searching request,
• obtaining, in accordance with a second identifier derived from the searching key included in the received searching request, the first identifier from the first list selected in the second process, the first identifier matching the second identifier,
• obtaining, from the first list selected in the second process, the first pointer corresponding to the first identifier obtained in the second process,
• obtaining the entry from the memory location directly indicated by the first identifier, and
• outputting the value included in the entry obtained in the second process.

A non-transitory computer-readable storage medium storing a program which causes a processor to perform processing in a memory that includes a first memory device and a second memory device, the second memory device being greater in latency than the first memory device, the first memory device being configured to store a plurality of lists each being associated with a respective hash value, the processing comprising:

• executing a first process includes
• receiving an entry that includes a key and a value,
• in response to receiving the entry, storing the received entry in the second memory device,
• in response to receiving the entry, selecting a first list from among the plurality of lists in accordance with a first hash value, the first hash value being derived from the key included in the received entry,
• in response to selecting the first list, adding a set of a first identifier and a first pointer to the selected first list, the first identifier being derived from the key included in the received entry such that the first identifier is different from the first hash value, the first pointer directly indicating a memory location at which the received entry is stored or to be stored in the second memory device, each of the plurality of lists including neither the key nor the value included in the received entry even after the adding of the first identifier and the first pointer;
• and
• executing a second process that includes
• receiving a searching request for a value, the searching request includes a searching key,
• in response to receiving the searching request, selecting the first list from among the plurality of lists in accordance with the first hash value derived from the searching key included in the received searching request,
• obtaining, in accordance with a second identifier derived from the searching key included in the received searching request, the first identifier from the first list selected in the second process, the first identifier matching the second identifier,
• obtaining, from the first list selected in the second process, the first pointer corresponding to the first identifier obtained in the second process,
• obtaining the entry from the memory location directly indicated by the first identifier, and
• outputting the value included in the entry obtained in the second process.