hat sich ergeben:
A.- Der am *** 1978 geborene A._, nach eigenen Angaben Staatsangehöriger der Volksrepublik China, wurde am 5. April 2001 beim Versuch, zu Fuss in die Schweiz einzureisen, nach Deutschland zurückgewiesen. Aufgrund seiner Angaben, sich bereits längere Zeit in der Schweiz aufgehalten zu haben, stimmten die Einwohnerdienste Basel-Stadt, Abteilung Internationale Kundschaft als kantonale Fremdenpolizei (im Folgenden: Fremdenpolizei), einer Rückübernahme zu. Am 6. April 2001 nahm ihn die Kantonspolizei Basel-Stadt auf Veranlassung der Fremdenpolizei in Basel fest. Am 9. April 2001 wies ihn die Fremdenpolizei aus der Schweiz weg und verfügte über ihn die Ausschaffungshaft. Am gleichen Tag prüfte und genehmigte die Einzelrichterin für Zwangsmassnahmen im Ausländerrecht des Verwaltungsgerichts des Kantons Basel-Stadt (im Folgenden: Haftrichterin) die Haft für drei Monate bis zum 5. Juli 2001.
B.- Dagegen hat A._ mit in chinesischer Sprache verfasster Eingabe vom 18. April 2001 (beim Bundesgericht eingegangen: 4. Mai 2001) beim Bundesgericht Beschwerde erhoben. Die Eingabe wurde von Amtes wegen übersetzt.
A._ macht geltend, er habe durch einen Schlepper vom schönen Leben in der Schweiz gehört; nun habe er bei diesem hohe Schulden, welche er in Raten zurückzahle. Er ersucht sinngemäss, aus der Haft entlassen zu werden.
Die Fremdenpolizei beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Haftrichterin schliesst auf Abweisung der Beschwerde. Der Beschwerdeführer
hat sich nicht mehr zur Sache geäussert. Das Bundesamt für Ausländerfragen hat sich nicht vernehmen lassen.

Das Bundesgericht zieht in Erwägung:
1.- Die Verwaltungsgerichtsbeschwerde hat die Begehren, deren Begründung mit Angabe der Beweismittel und die Unterschrift des Beschwerdeführers oder seines Vertreters zu enthalten (Art. 108 Abs. 2 OG). Sie muss sich sachbezogen mit dem angefochtenen Entscheid auseinandersetzen (<ref-ruling> ff.). Bei Laienbeschwerden gegen die Genehmigung der Ausschaffungshaft stellt das Bundesgericht indessen keine hohen Anforderungen an die Beschwerdebegründung (vgl. <ref-ruling> E. 3b S. 277). Ist daraus ersichtlich, dass sich der Betroffene - wie hier - (zumindest auch) gegen seine Haft wendet, nimmt es entsprechende Eingaben als Verwaltungsgerichtsbeschwerden entgegen.
2.- Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, wenn die Voraussetzungen von Art. 13b des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) erfüllt sind.
Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger, Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2a S. 61; <ref-ruling> ff.), 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). Weiter muss die Haft verhältnismässig (<ref-ruling> E. 2c S. 198; vgl. auch BGE
<ref-ruling> E. 3 S. 153) und die Ausschaffung rechtlich und tatsächlich möglich sein (Art. 13c Abs. 5 lit. a ANAG; vgl. BGE <ref-ruling> E. 3 S. 152 ff.). Auf Seiten der Behörden ist die Papierbeschaffung sodann mit dem nötigen Nachdruck zu verfolgen (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> ff.).
3.- a) Die Fremdenpolizei hat den Beschwerdeführer am 9. April 2001 formlos aus der Schweiz weggewiesen. Der Vollzug dieser Massnahme ist momentan noch nicht möglich, da die Identität des Beschwerdeführers noch nicht einwandfrei geklärt ist und entsprechend noch keine Reisepapiere vorliegen.
Es bestehen aber keine Hinweise darauf, dass der Vollzug der Wegweisung nicht in absehbarer Zeit durchführbar ist. Die Anordnung der Ausschaffungshaft ist daher rechtmässig, falls einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe besteht.
b) Nach Art. 13b Abs. 1 lit. c ANAG kann Ausschaffungshaft verfügt werden, wenn konkrete Anzeichen befürchten lassen, dass sich der Ausländer der Ausschaffung entziehen will (Gefahr des Untertauchens). Der Vollzug der Wegweisung muss erheblich gefährdet erscheinen. Dass der Betroffene sich illegal in der Schweiz aufhält, genügt hierfür ebensowenig wie die Tatsache, dass er keine Papiere besitzt und nur mangelhaft an deren Beschaffung mitwirkt. Die Gefahr des Untertauchens ist hingegen bei strafrechtlich relevantem Verhalten regelmässig zu bejahen, ist bei einem straffällig gewordenen Ausländer doch eher als bei einem unbescholtenen davon auszugehen, er werde in Zukunft behördliche Anordnungen missachten (vgl. <ref-ruling> E. 2a S. 50 f.).
Der Beschwerdeführer ist aus wirtschaftlichen Gründen mit Hilfe eines Schleppers und unter Verletzung der Ein- reisevorschriften in die Schweiz eingereist, wo er sich gemäss eigenen Angaben seit Juli oder August 2000 nicht nur illegal aufhält - was nach dem Gesagten für die Bejahung der Untertauchensgefahr noch nicht genügt -, sondern überdies schwarz arbeitet; dies unter anderem aufgrund der Verpflichtung, die seinem Schlepper gegenüber bestehenden Schulden abzuzahlen. Angesichts dieses strafrechtlich relevanten Verhaltens bietet er aber kaum Gewähr dafür, dass er sich zu gegebener Zeit, wenn die Reisepapiere vorliegen, für den Vollzug der Ausschaffung zur Verfügung halten wird.
c) Damit erweist sich die Anordnung der Ausschaffungshaft als rechtmässig.
4.- Die Verwaltungsgerichtsbeschwerde ist nach dem Gesagten abzuweisen. Der Beschwerdeführer würde damit grundsätzlich kostenpflichtig (Art. 156 Abs. 1 OG). Angesichts seiner finanziellen Verhältnisse ist jedoch von der Erhebung einer Gerichtsgebühr abzusehen (Art. 153 Abs. 1 OG).
Die kantonale Fremdenpolizei wird ersucht, sicherzustellen, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und verständlich gemacht wird.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Es werden keine Kosten erhoben.
3.- Dieses Urteil wird dem Beschwerdeführer, den Einwohnerdiensten des Kantons Basel-Stadt, Abteilung Internationale Kundschaft als kantonale Fremdenpolizei, dem Verwaltungsgericht des Kantons Basel-Stadt, Einzelrichterin für Zwangsmassnahmen im Ausländerrecht, sowie dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 16. Mai 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Die Gerichtsschreiberin: