Como mencionado por @ user1934428 , você pode recriar a tabela de hash explicitamente executando rehash . Para evitar fazer isso manualmente, coloque isso no seu zshrc :
zstyle ":completion:*:commands" rehash 1
Você pode descobrir mais sobre zstyle da página zshmodule man e os próprios estilos estão documentados em zshcompsys .