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, wherein the update controller is configured to, in response to the cache memory apparatus receiving data requests, each having a same set address: determine, for each piece of data of the data requests, whether each piece of the cache data is an update candidate based on the result of the comparison of the upper K bits of the tag address that is received for each of the pieces of the data and the upper K bits of each of the pieces of tag data; and update, with new data, a piece among the pieces of the cache data that is determined as an update candidate the most.