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 that uses hash-based block matching during block vector (“By”) estimation. Other innovations relate to data structures that organize candidate blocks for hash-based block matching. Still other innovations relate to hierarchical hash-based block matching.