redisハッシュでキーパターンを検索する方法は？

HSCANコマンドを使用する必要があります。

例：

redis> HMSET address_book bob_123456 Address1 mary_567894 Address2 john_123456 Address3
OK
redis> HSCAN address_book 0 match *_123456
1) "0"
2) 1) "bob_123456"
   2) "Address1"
   3) "john_123456"
   4) "Address3"

更新

Pythonの実装：

r = Redis(....) #redis url
for address in r.hscan_iter('address_book', match='*_123456'):
  print(address)