Why should I hash keys in the NearProtocol UnorderedMap?

In the Near NFT example, why are keys in the account_gives_access UnorderedMap hashed? https://github.com/near-examples/NFT/blame/master/contracts/rust/src/lib.rs

pub struct NonFungibleTokenBasic {
    pub token_to_account: UnorderedMap<TokenId, AccountId>,
    pub account_gives_access: UnorderedMap<AccountIdHash, UnorderedSet<AccountIdHash>>, 
    pub owner_id: AccountId,
}

Solution

The UnorderedMap type uses a trie. An attacker could unbalance the trie by repeatedly pushing keys onto the trie that push the depth of one side of the trie deep. This would reduce performance of trie lookups on names beneath the attacker's.

A mitigation to the attock is to store hashes of the keys. The hashes would be equally distributed among possible values. The attacker could still perform the attack, but generating specific hashes is hard, so some protocols say.

Another mitigation to the attack is to use a LookupMap, which uses an AVL tree, which automatically rebalances its tree.

The attack isn't significantly threatening. The worst the attacker can do is punish a small range of key values, by repeatedly paying the storage costs to push an extremely limited range of key values farther down the trie. It therefore, probably isn't worth paying the cost to hash the keys.

However, for trees that store a large number of keys, hashing keys, or a LookupMap, may still be worth considering, as an unbalanced trie is very likely to result.

To recap, we reviewed the comparison of cost between:

Hashing each key before storing and retreiving to an UnorderedMap
Allowing the "attack" described above
Using a LookupMap instead of an UnorderedMap

thanks @MikePurvis for explanation.