The reason for the error is obviously that map_t capitalized does not correspond to any declaration.
typedef struct map_t* Map;
Additionally warnings are generated, because NULL corresponds to a null pointer, but key and value are defined as char.
I also wonder why the source code was tagged as C++, although pure C is used here.
With C++ I would suggest a class instead of the structure and the function and new() instead of the function malloc().