We propose a new chaotic keyed hashing scheme based on the structure of the input message. The structure of the message is identified with maps of the appearances of each character throughout the input message. We use a $$2$$ 2 -dimensional generalized cat map whose chaotic orbits are used to introduce randomness to the computation of the hash value and hence facilitate uniform sensitivity of the hash value to the input message and the secret key. Our proposed hashing scheme is fast, efficient, and flexible. Empirical results verify the high sensitivity of the proposed hash function to the input message and the secret key. Further simulations presented demonstrate the strong capability of the proposed scheme for confusion, diffusion, and collision resistance. Compared with existing schemes, especially those based on chaotic maps, the proposed scheme is shown to have superior performance.