According to one embodiment, a semiconductor memory device includes a memory and a controller. The memory stores data pieces and search information including entries, where each entry is associated with a search key for specifying one data piece and a real address at which the data piece is stored. Upon reception of a first command, the controller, when the first command specifies a search key, outputs one data piece corresponding to one entry which includes the search key, and when the first command specifies one real address, outputs one data piece corresponding to one entry including the real address.