Provided are a cache memory using a linear hash function and a method of operating the same. The cache memory includes: a first hash function module for converting a main memory address received from a central processing unit (CPU) into a first index value using a first hash function; a second hash function module for converting the main memory address into a second index value using a second hash function; a first comparator for comparing a tag value of a data block located at the first index value in the first bank with a tag value of the main memory address; and a second comparator for comparing a tag value of a data block located at the second index value in the second bank with the tag value of the main memory address. In a pair of linear hash functions according to the present invention, each constructed with a 2m×m binary matrix, even if m is an odd number, each of the linear hash functions has the highest degree of interbank dispersion and avoids conflicts in row, column, diagonal, anti-diagonal, and rectangular patterns, so that a 2-way skewed associative cache can be constructed in relatively wide ranges.