A storage device is provided which includes a nonvolatile memory device configured to store a plurality of reference data, a memory configured to store a hash manage table used to manage a plurality of reference hash keys of each of the plurality of reference data, a hash key generator configured to generate a plurality of hash keys based on write requested data, and a memory controller configured to compare the plurality of hash keys and reference hash keys of each reference data to determine whether to store the write requested data in the nonvolatile memory device. The memory controller selects one of the plurality of reference data according to a similarity between the plurality of hash keys and the plurality of reference hash keys of each reference data and stores the write requested data and the selected reference data in the nonvolatile memory device to refer to each other.