A storage device includes memory devices and a controller. The controller translates a logical address received from a host to a physical address for the memory devices. The controller manages first correspondence information associated with correspondence relationships between logical addresses and physical addresses. The controller manages translation information that includes information of a minimal perfect hash (MPH) function. The MPH function is generated by using logical addresses indicating a memory region of a reference size as key values, when a size of a memory region indicated by logical addresses managed in the first correspondence information reaches the reference size. The controller manages second correspondence information associated with correspondence relationships between the logical addresses used as the key values and the MPH function of the translation information.