"I do not have a map."
Translation:Je n'ai pas de carte.
If I am not mistaken you can technically use "une carte," you'd just be emphasizing the fact that you don't even have one. I suppose if it had wanted an emphasis it would have said "I don't even have a map" or "I don't have a single map" but I think "une" could technically work because the original English could mean one of the above. But I do understand what you're saying, just translating directly it would have to be "de."
The example you're giving has nothing to do with having something or quantity though.
There are many ways "ne/n'...pas" can be used, I was only describing the way it's used to talk about unspecified things you don't possess (quantity = 0).
But outside of this, "de" may or may not be required with "ne/n'...pas", it'll vastly depend on what you're talking about. Which can be seen simply by talking about specified things instead for example :
- "Je n'ai pas le stylo rouge." (a specific red pen we know about)
Here "de" isn't required. But if the red pen was unspecified, it would still be:
- "Je n'ai pas de stylo rouge." (any red pen)