does using an HMAC protect against hash table DoS attacks?
but if there are N buckets and N is not super large, simply generating random data will still produce a hit approximately once every N tries. 


Changing the hash function won't change this fact. There should be other mitigations to a user adding a bunch of random data, such as rate limiting or changing your data structure.

How do you plan on obtaining the key for the HMAC? If it's the same for everything, then hash collisions in the underlying hash function translate to hmac collisions. If it's derived from the data, then the attacker's job is just marginally more difficult; they have to effectively compute three hashes per calculation (one for the key derivation, two for the hmac) instead of one. If it's random, how will you be able to retrieve data from the table?

As you mention in the comments, we don't care about hash collisions but rather hash collisions mod N. In this scenario, an HMAC would sufficiently stop an attacker from being able to calculate data that would hash to the same bucket. If the HMAC construction is too expensive for your application, you should be able to get away with something lighter weight like H(key||message).