A semiconductor memory device includes a memory portion that includes i (i is a natural number) sets each including j (j is a natural number of 2 or larger) arrays each including k (k is a natural number of 2 or larger) lines to each of which a first bit column of an address is assigned in advance; a comparison circuit; and a control circuit. The i×j lines to each of which a first bit column of an objective address is assigned in advance are searched more than once and less than or equal to j times with the use of the control circuit and a cache hit signal or a cache miss signal output from the selection circuit. In such a manner, the line storing the objective data is specified.