wird festgestellt und in Erwägung gezogen:
1. a) C._ (alias P._, alias K._) reiste am 6. September 1999 ohne Papiere illegal in die Schweiz ein. Er stellte unter dem Namen "P._" ein Asylgesuch und behauptete, aus Tscherepovjez (Russland) zu stammen. Dort sei er als Mitglied einer Polizeieinheit (OMON) mit Anhängern der lokalen Mafia in Konflikt geraten.
Mit Verfügung vom 17. Januar 2000 trat das Bundesamt für Flüchtlinge (BFF) auf das Asylgesuch nicht ein und wies den Gesuchsteller aus der Schweiz weg. Das Bundesamt begründete seinen Entscheid im Wesentlichen damit, der angeblich aus Russland stammende Mann sei in Deutschland unter dem Namen "K._" aus Parkany (Moldawien) erkennungsdienstlich erfasst. Somit habe er die Behörden über seine Identität getäuscht.
b) Am 1. März 2000 wurde C._ in Zürich angehalten (Verdacht auf Ladendiebstahl/Hehlerei). Tags darauf verfügte die Fremdenpolizei des Kantons Zürich ihm gegenüber die Ausschaffungshaft. Am 3. März 2000 prüfte und bestätigte der Haftrichter des Bezirksgerichts Zürich die Ausschaffungshaft bis zum 1. Juni 2000.
Hiergegen reichte C._ am 28. März 2000 beim Bezirksgericht Zürich eine "Beschwerde" ein mit dem sinngemässen Antrag, er sei aus der Haft zu entlassen. Am 5. April 2000 stellte der Haftrichter fest, ein Haftentlassungsgesuch könne frühestens einen Monat nach der Haftüberprüfung gestellt werden. Deshalb trat er auf die Eingabe nicht ein und überwies sie zur weiteren Behandlung dem Bundesgericht.
c) Mit Verfügung vom 10. April 2000 nahm das präsidierende Mitglied der II. öffentlichrechtlichen Abteilung die Eingabe als Beschwerdeschrift gegen die Verfügung des Haftrichters vom 3. März 2000 entgegen.
Die Fremdenpolizei des Kantons Zürich beantragt, die Beschwerde abzuweisen. Das Eidgenössische Justiz- und Polizeidepartement liess sich nicht vernehmen. Der Beschwerdeführer hat sich nicht mehr zur Sache geäussert.
2.- a) Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen bzw. in dieser belassen, soweit die Voraussetzungen von Art. 13b des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20; in der Fassung des Bundesgesetzes vom 18. März 1994 über Zwangsmassnahmen im Ausländerrecht [AS 1995 146 ff.]) erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2 S. 61; <ref-ruling> E. 1 S. 150), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist. Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (<ref-ruling> E. 1 S. 3), die Ausschaffung rechtlich und tatsächlich möglich sein (Art. 13c Abs. 5 lit. a ANAG; vgl. dazu BGE <ref-ruling> E. 3 S. 152 ff.) und die Papierbeschaffung mit dem nötigen Nachdruck verfolgt werden (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> ff.).
b) Gemäss Art. 105 Abs. 2 OG ist das Bundesgericht an die tatsächlichen Feststellungen des Haftrichters gebunden, sofern dieser den Sachverhalt nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen erhoben hat. In diesem Rahmen können namentlich nachträgliche Veränderungen des Sachverhalts bzw.
neue tatsächliche Vorbringen nicht berücksichtigt werden (<ref-ruling> E. 5d S. 310, mit Hinweisen).
3.- a) Der Beschwerdeführer wurde durch das Bundesamt für Flüchtlinge rechtskräftig aus der Schweiz weggewiesen.
Der Vollzug dieser Massnahme erscheint nicht undurchführbar (vgl. Art. 13c Abs. 5 lit. a ANAG), und die für den Ausschaffungsvollzug notwendigen Vorkehrungen sind umgehend an die Hand genommen worden. Die angeordnete Haft ist daher rechtmässig, wenn einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe besteht.
b) Der Haftrichter hat die Ausschaffungshaft gestützt auf Art. 13b Abs. 1 lit. c ANAG genehmigt. Danach kann ein Ausländer in Ausschaffungshaft genommen werden, wenn konkrete Anzeichen befürchten lassen, dass er sich der Ausschaffung entziehen will, insbesondere weil sein bisheriges Verhalten darauf schliessen lässt, dass er sich behördlichen Anordnungen widersetzt (Untertauchensgefahr).
Dabei muss der Vollzug der Wegweisung erheblich gefährdet erscheinen. Dies trifft namentlich zu, wenn der Ausländer bereits einmal untergetaucht ist, behördlichen Anordnungen keine Folge leistet oder durch erkennbar unglaubwürdige und widersprüchliche Angaben die Vollzugsbemühungen der Behörden erschwert (vgl. <ref-ruling> E. 2a; <ref-ruling> E. 2b S. 198).
Dies war vorliegend der Fall: Im Asylverfahren nannte sich der Beschwerdeführer "P._"; in Deutschland trat er als "K._" bzw. "C._" auf. Über gültige Papiere verfügt der Beschwerdeführer offensichtlich nicht, und seine Identität steht nach wie vor nicht fest. Den deutschen Behörden gegenüber erklärte er, aus Moldawien zu stammen. In der Schweiz gab er sich zuerst als Russe aus und behauptete später, "weder Russe noch Moldawier" zu sein. Der Aufforderung, sich gültige Reisepapiere zu beschaffen, kam er nicht nach. Gegenüber der Kantonspolizei Zürich erklärte er, nicht in sein Heimatland zurückkehren zu wollen, und verweigerte jegliche Kooperation ("Ich verweigere jegliche Kooperation.
Ich werde nur immer antworten - ich erinnere mich nicht, ich weiss es nicht. So kann ich immer hierbleiben"). Nach seiner Inhaftierung war er nicht bereit, die Frage nach seinem richtigen Namen und seinem Geburtsdatum zu beantworten.
Unter diesen Umständen bietet der Beschwerdeführer keine Gewähr dafür, dass er sich ohne Haft zu gegebener Zeit, d.h.
bei Vorliegen der Reisepapiere, für den Ausschaffungsvollzug zur Verfügung halten wird (vgl. <ref-ruling> E. 2a S. 50 f.), und es verletzt Bundesrecht nicht, wenn die Vorinstanzen das Vorliegen einer Untertauchensgefahr bejaht haben.
c) Soweit der Beschwerdeführer seine Begehren mit einer Krankheit (Tuberkulose) begründet, handelt es sich um eine nach Art. 105 Abs. 2 OG unzulässige neue Behauptung (vgl. E. 2b), die vorab gegenüber den Organen der Vollzugsanstalt (ärztlicher Dienst) geltend zu machen wäre und die im Übrigen die Aufrechterhaltung der Ausschaffungshaft nicht ausschliesst (unveröffentlichtes Urteil des Bundesgerichts vom 28. April 1999 i.S. Toth, E. 3c).
4.- a) Die Verwaltungsgerichtsbeschwerde erweist sich als offensichtlich unbegründet und ist deshalb im vereinfachten Verfahren nach Art. 36a OG abzuweisen, soweit darauf eingetreten wird. Das Urteil kann summarisch begründet werden; ergänzend wird auf die Ausführungen im angefochtenen Entscheid und in der Haftverfügung der Fremdenpolizei verwiesen (vgl. Art. 36a Abs. 3 OG).
b) Bei diesem Verfahrensausgang würde der unterliegende Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 OG). Mit Rücksicht auf seine finanziellen Verhältnisse rechtfertigt es sich indessen, keine Gerichtsgebühr zu erheben (vgl. Art. 153a Abs. 1 OG). Parteientschädigungen sind nicht geschuldet.

Demnach erkennt das Bundesgericht
im Verfahren nach Art. 36a OG:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Es werden keine Kosten erhoben.
3.- Dieses Urteil wird dem Beschwerdeführer, der Fremdenpolizei des Kantons Zürich und dem Bezirksgericht Zürich (Haftrichter) sowie dem Eidgenössischen Justiz- und Polizeidepartement schriftlich mitgeteilt.
_
Lausanne, 18. April 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: