According to an embodiment, a semiconductor memory device includes a first storage unit, a receiving unit, an acquiring unit, and an output control unit. The first storage unit is configured to store a value and address information in which a key address generated on the basis of a key associated with the value and a physical address of the value are associated with each other. The receiving unit is configured to receive a request for acquisition of the value associated with the key. The request contains the key. The acquiring unit is configured to acquire the physical address associated with the key address of the key contained in the request for acquisition on the basis of the address information. The output control unit is configured to acquire the value at the acquired physical address from the first storage unit and output the acquired value in response to the request.