Thanks to the people who gave answers, but I thought I could be more succinct. There are 2 differences:
- immutability of <||>, which makes adding/deleting on an association a little slower.
Immutability is not implemented in Mathematica as naively as copying the entire structure every time we add something to the association, but some extra work needs to be done, and it seems as a result it is still slightly slower (but the convenience outweighs the very small difference in my opinion). Note that immutability is also why using a bunch of AppendTo's on a list is EXTREMELY slow compared to using Table[] to make the list.
- Associations keep the order of items, in addition to their hashes. For example, <|"a"->3|>[[1]] evaluates to 3. I think this makes lookups on average O(log n) for the association, compared to O(1) for the hashtable.
See the given answers/comments for some good info which helped me write the above.