A data processing apparatus is provided having processing logic for performing a sequence of operations, and a cache having a plurality of segments for storing data values for access by the processing logic. The processing logic is arranged, when access to a data value is required, to issue an access request specifying an address in memory associated with that data value, and the cache is responsive to the address to perform a lookup procedure during which it is determined whether the data value is stored in the cache. Indication logic is provided which, in response to an address portion of the address, provides for each of at least a subject of the segments an indication as to whether the data value is stored in that segment. The indication logic has guardian storage for storing guarding data, and hash logic for performing a hash operation on the address portion in order to reference the guarding data to determine each indication. Each indication indicates whether the data value is either definitely not stored in the associated segment or is potentially stored with the associated segment, and the cache is then operable to use the indications produced by the indication logic to affect the lookup procedure performed in respect of any segment whose associated indication indicates that the data value is definitely not stored in that segment. This technique has been found to provide a particularly power efficient mechanism for accessing the cache.