A key-value storage device and method of using the same. In some embodiments, keys are stored in a key store in a first non-volatile memory and corresponding values associated with the keys are stored in a value store of a second non-volatile memory. An input command is received from a host device, the input command having a key associated with a value. Different first and second hash values are generated by applying a hash function to the key. The input command is executed responsive to the first and second hash values.