A data storage device comprises an array of data storage elements arranged as multiple partitions each comprising two or more data storage elements, each data storage element being associated with a respective identifier which identifies a data item currently stored by that data storage element; a predictor configured to compare, for each partition, information derived from the identifiers associated with the data storage elements of that partition with information derived from an identifier associated with the required data item, to identify a subset of partitions that do not store the required data item; and a comparator configured to compare identifiers associated with data storage elements of one or more partitions with the identifier associated with the required data item, wherein any partitions in the subset of partitions are excluded from the test group of partitions.