Innovations in hash-based block matching facilitate block copy (“BC”) prediction that is more effective in terms of rate-distortion performance and/or computational efficiency of encoding. For example, some of the innovations relate to encoding blocks with hash values determined using hash-based block matching. Other innovations relate to reconstructing blocks using hash values determined with hash-based block matching.