Q:

Should REST APIs for updating a map allow setting the map to empty?

I have a rest API for managing a simple map of keys to values. 
For example, the GET request could return the following:
 {
    "keyA": "valueA",
    "keyB": "valueB"
 }

There is a PUT endpoint that replaces the map with a new map in the body of the request. For example, the map can be replaced with a new map:
 {
    "keyC": "valueC"
 }

This removes keys "keyA", and "keyB", and adds "keyC". The question that we are debating is whether or not the PUT request should be allowed to send an empty map {} to clear out the map altogether so it has no keys left. Should this be blocked? Does any of this follow REST conventions?

A:

This is less a question targeted towards REST then it is actually targeting HTTP as the default transport protocol used by applications following a REST architecture approach. According to RFC 7231 4.3.4 a server

SHOULD verify that the PUT representation is consistent with any constraints the server has for the target resource that cannot or will not be changed by the PUT. 
...
When a PUT representation is inconsistent with the target resource, the origin server SHOULD either make them consistent, by transforming the representation or changing the resource configuration, or respond with an appropriate error message containing sufficient information to explain why the representation is unsuitable.

I admit that this is a bit vague and leaves plenty of room for interpretation but I feel that it's more or less up to you whether you want an empty body being a valid state of the resource or not. In case you think it shouldn't allow an empty body simply return a 409 Conflict response indicating why the request failed.
A further note needs to be added here: REST puts focus on the usage of media types. A media type is a syntactical and semantical description of the elements forming a valid document. If you compare that with HTML i.e. you will notice that it defines when certain elements are valid to be put into a document or not and which syntactial structure to use. The same should be done for almost any document here either. The media type therefore defines constraints on certain elements and what not. A PUT request here should validate the received payload against the constraints defined in a media type to determine whether a conflict arrose or the representation may be converted to an other media type format.
application/json is a very weak media type in terms of REST as it just defines the syntactical structure. It doesn't even support links to other documents to start with. There are a couple of extensions like application/hal+json that define the semantics on link relations though this will most likely still not define the semantics of elements you require.
This is exactly why Fielding mentioned that 

A REST API should spend almost all of its descriptive effort in defining the media type(s) used for representing resources and driving application state, or in defining extended relation names and/or hypertext-enabled mark-up for existing standard media types. (Source)

