1. A cache memory apparatus comprising: a data memory configured to store pieces of cache data corresponding to pieces of data stored in a main memory; a tag memory configured to store pieces of tag data respectively corresponding to the pieces of the cache data, each of the pieces of the tag data comprising N bits; a tag comparator configured to compare upper K bits, wherein 1≦K<N, of each of the pieces of the tag data corresponding to a set address that is received with upper K bits of a tag address that is received, the tag address comprising N bits, compare other (N−K) bits of each of the pieces of the tag data with other (N−K) bits of the tag address, and determine whether there is a cache hit or a cache miss based on results of the comparisons; and an update controller configured to, in response to the cache miss being determined, determine a piece among the pieces of the cache data as an update candidate based on the result of the comparison of the upper K bits of each of the pieces of the tag data and the upper K bits of the tag address, and update the update candidate with new data.