In this paper we investigate the functoriality properties of map-graded Hochschild complexes. We show that the category MAP of map-graded categories is naturally a stack over the category of small categories endowed with a certain Grothendieck topology of 3-covers. For a related topology of infinity-covers on the cartesian morphisms in MAP, we prove that taking map-graded Hochschild complexes defines a sheaf. From the functoriality related to injections between map-graded categories, we obtain Hochschild complexes with support. We revisit Kellers arrow category argument from this perspective, and introduce and investigate a general Grothendieck construction which encompasses both the map-graded categories associated to presheaves of algebras and certain generalized arrow categories, which together constitute a pair of complementary tools for deconstructing Hochschild complexes.