Sachverhalt:
A.
A.a. Die Staatsanwaltschaft des Kantons Basel-Stadt führt gegen A._ ein Strafverfahren wegen Delikten gegen die sexuelle Integrität, Brandstiftung, mehrfacher Sachbeschädigung, mehrfacher Irreführung der Rechtspflege, mehrfachen Betrugs, Drohung und weiterer Delikte.
A._ wurde am 26. März 2015 festgenommen und durch das Zwangsmassnahmengericht des Kantons Basel-Stadt mit Verfügung vom 28. März 2015 in Untersuchungshaft versetzt.
A.b. In ihrem Antrag auf Anordnung der Untersuchungshaft hatte die Staatsanwaltschaft Folgendes dargelegt:
Im Gebäude an der G._strasse ... in Basel, wo sich A._ mit seinem Nachtclub "B._" eingemietet habe, sei es 2013 und 2014 zu Sachbeschädigungen mit Säure und Farbe gekommen. Diese beträfen im Wesentlichen jene Geschosse, in welchen die anderen Mieter wohnten. Verschiedene Personen hätten Angaben gemacht, die auf eine Täterschaft von A._ hindeuteten. Dieser habe mit dem Liegenschaftseigentümer Streit und auch mit den anderen Mietern bestünden Probleme, da sie sich über Nachtlärm beklagt hätten.
In der Nacht vom 13. auf den 14. Juli 2014 sei ein Fenster des Personenwagens von C._ eingeschlagen und der Innenraum mit Säure übergossen worden. Dasselbe sei in der Nacht vom 25. auf den 26. Januar 2015 mit dem Personenwagen von D._ geschehen. Beide Geschädigten würden A._ verdächtigen, weil sein Nachtclub ihnen gegenüber unberechtigte finanzielle Forderungen erhoben habe.
Am 19. Mai 2013 sei ein Fahrzeug (Hummer) der E._ AG, welche durch A._ vertreten werde, abgebrannt. Ermittlungen hätten ergeben, dass von Brandstiftung auszugehen sei und dass ein Mobiltelefon, das gemäss den Angaben von A._ gegenüber der Polizei und gegenüber der Hausratsversicherung mitverbrannt sein soll, später immer noch in Betrieb war. F._ habe ausgesagt, dass A._ ihm erzählt habe, vergeblich versucht zu haben, seinen Hummer zu verkaufen. Die Ermittlungen hätten weiter ergeben, dass bei dem Fahrzeug der Kilometerstand um knapp 15'000 km zurückgestellt worden war.
Auf die Anzeige des Liegenschaftseigentümers seien im Gebäude an der G._strasse ... im Korridor des 1. OG sowie im Nachtclub zahlreiche versteckte Kameras entdeckt worden, dies auch in den Séparées des Nachtclubs. Der Beschuldigte sei geständig, Rauchmelder mit Kameras erworben und montiert zu haben.
F._ und D._ hätten ausgesagt, dass A._ in seinem Nachtclub den Gästen Kokain zur Verfügung stelle. Anlässlich einer Hausdurchsuchung vom 26. März 2015 am Wohnort von A._ seien drei Ampullen Anabolika und Munition zum Vorschein gekommen.
Die Tänzerin H._ habe am 13. Januar 2015 gegen A._ Strafanzeige erhoben wegen Nötigung, Förderung der Prostitution sowie Ausnützung sexueller Handlungen. C._ habe zudem zu Protokoll gegeben, dass seine Ehefrau früher als Tänzerin im Nachtclub "B._" gearbeitet habe. Wegen ihrer Liebe zu ihm habe sie ihren Arbeitsvertrag vorzeitig auflösen wollen. A._ habe daraufhin Fr. 30'000.-- pro Monat verlangt. Auch werde den Tänzerinnen, wenn sie mit seinen Methoden nicht einverstanden seien, gedroht, man werde mit ihnen in den Wald fahren, dort würde man dann sehen. Schliesslich habe F._ ausgesagt, eine Tänzerin namens I._ (J._) habe ihm gesagt, dass A._ mit seinen Tänzerinnen gegen ihren Willen Sex habe.
A.c. Am 7. April 2015 stellte A._ ein Haftentlassungsgesuch, das vom Zwangsmassnahmengericht mit Verfügung vom 16. April 2015 abgewiesen wurde. Eine von A._ dagegen erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt mit Entscheid vom 13. Mai 2015 ab.
B.
Mit Beschwerde in Strafsachen vom 29. Mai 2015 ans Bundesgericht beantragt A._, der Entscheid des Appellationsgerichts sei aufzuheben und er selbst sei sofort aus der Untersuchungshaft zu entlassen.
Das Appellationsgericht und die Staatsanwaltschaft beantragen die Abweisung der Beschwerde. Der Beschwerdeführer hält in seiner Stellungnahme dazu an seinen Anträgen und Rechtsauffassungen fest.

Erwägungen:
1.
Der angefochtene Beschluss des Appellationsgerichts betrifft die Anordnung der Untersuchungshaft. Dagegen ist die Beschwerde in Strafsachen nach <ref-law> gegeben. Der Beschwerdeführer nahm vor der Vorinstanz am Verfahren teil und befindet sich nach wie vor in Haft. Er ist deshalb nach <ref-law> zur Beschwerde berechtigt. Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
2.
Nach <ref-law> ist Untersuchungshaft unter anderem zulässig, wenn die beschuldigte Person eines Verbrechens oder Vergehens dringend verdächtig ist und ernsthaft zu befürchten ist, dass sie Personen beeinflusst und auf Beweismittel einwirkt, um so die Wahrheitsfindung zu beeinträchtigen (Abs. 1 lit. b), oder durch schwere Verbrechen oder Vergehen die Sicherheit anderer erheblich gefährdet, nachdem sie bereits früher gleichartige Straftaten verübt hat (Abs. 1 lit. c).
Das Appellationsgericht bejahte sowohl den dringenden Tatverdacht als auch den besonderen Haftgrund der Kollusionsgefahr (<ref-law>). Ob darüber hinaus auch Fortsetzungsgefahr bestehe (<ref-law>), liess es offen.
Der Beschwerdeführer rügt, es bestehe weder Kollusionsgefahr noch Fortsetzungsgefahr. Zudem habe das Appellationsgericht die Begründungspflicht (<ref-law>) und das Beschleunigungsgebot in Haftsachen (<ref-law>) verletzt.
3.
Den dringenden Tatverdacht bestreitet der Beschwerdeführer - wie bereits im vorinstanzlichen Verfahren - nur insoweit, als er im Zusammenhang mit der Kollusionsgefahr beiläufig vorbringt, es lasse sich beim jetzigen Verfahrensstand kein dringender Tatverdacht mehr begründen, der Delikte gegen die Willens- oder Handlungsfreiheit betreffe. Eine hinreichend substanziierte Kritik am angefochtenen Entscheid fehlt in dieser Hinsicht, sodass auf die Beschwerde in diesem Punkt nicht einzutreten ist (<ref-law>). Lediglich der Vollständigkeit halber ist anzufügen, dass die Staatsanwaltschaft zu Recht geltend macht, der ursprüngliche Verdacht auf strafbare Handlungen gegen die sexuelle Integrität habe sich mit der Einvernahme von J._ am 20. April 2015 erhärtet. Die Tänzerin habe ausgesagt, der Beschwerdeführer habe sie zum Sex gezwungen. Ihren Ausführungen sei zu entnehmen, dass er ganz offensichtlich seine Machtposition als Arbeitgeber und die sich daraus ergebende Möglichkeit, seinen aus dem Ausland kommenden Angestellten die Auszahlung des Lohns zu verweigern oder den weiteren Aufenthalt in der Schweiz durch Entlassung zu verunmöglichen, ausgenutzt habe, um sie zum Geschlechtsverkehr zu nötigen. Diese Handlung lasse sich entweder unter den Tatbestand der Vergewaltigung gemäss <ref-law> oder der Ausnützung einer Notlage gemäss <ref-law> subsumieren.
4.
4.1. Nach Ansicht des Beschwerdeführers besteht keine Kollusionsgefahr. Es seien in der Zwischenzeit sämtliche Frauen befragt worden, welche für Delikte gegen die Willens- und Handlungsfreiheit in Frage kämen. Schwerwiegende Delikte dieser Art hätten nicht bestätigt werden können. Vielmehr entlasteten ihn die Frauen. Auch gebe es keine Indizien, wonach sie sich vor ihm fürchteten oder sich scheuen würden, belastende Aussagen zu machen. So habe K._ ausgesagt, dass sie ihm gegenüber nichts zu beanstanden habe. Dass bei ihr schon die Anwesenheit des Verteidigers anlässlich der Einvernahme vom 27. März 2015 grosse Angst hervorzurufen schien, wie die Vorinstanz behaupte, sei falsch und unbelegt. Nicht zutreffend sei auch, dass die Cabaret-Tänzerinnen einen prekären Aufenthaltsstatus hätten. Schliesslich könne man aus dem Umstand, dass sein Nachtclub Teil des Rotlichtmilieus sei, nicht pauschal auf Kollusionsgefahr schliessen, umso weniger, als es sich dabei um ein Etablissement im gehobenen Segment handle. Die Tänzerinnen würden monatlich den Nachtclub wechseln und bestimmt nicht zurückkehren, wenn sie unzufrieden seien. Es sei deshalb lebensfremd anzunehmen, sie liessen sich drangsalieren. Die Tänzerinnen würden oft mehrere Engagements bei ihm annehmen. Schliesslich lasse sich die Kollusionsgefahr auch nicht aus den von der Vorinstanz angeführten Telefongesprächen ableiten. Im Übrigen habe er bereits Wochen vor seiner Festnahme gewusst, dass er überwacht werde. Wenn er hätte kolludieren wollen, hätte er dies somit bereits getan. Massgebend sei im Ergebnis, dass aufgrund des aktuellen Untersuchungsstands eine Kollusion ausgeschlossen sei. Es sei unklar, auf welche Personen er noch Einfluss nehmen könne. Zudem sei schlicht alles beschlagnahmt worden, was als Beweismittel in Frage komme.
Der Beschwerdeführer rügt die Erwägungen des Appellationsgerichts zur Kollusionsgefahr als ungenügend. Es werde nicht dargelegt, welche konkreten Kollusionshandlungen angesichts des fortgeschrittenen Untersuchungsstands überhaupt noch möglich wären. Die Begründung des angefochtenen Entscheids genüge der Begründungspflicht nicht.
Schliesslich macht der Beschwerdeführer eine Verletzung des Beschleunigungsgebots in Haftsachen geltend (<ref-law>). Er ist der Ansicht, das Appellationsgericht hätte zwingend auch den Haftgrund der Fortsetzungsgefahr prüfen müssen, um eine unnötige Verlängerung des Verfahrens auszuschliessen.
4.2. Das Appellationsgericht legte dar, der Beschwerdeführer habe sich am 19. März 2015 bei einer Vermittlungsagentur für Tänzerinnen nach dem aktuellen und den zukünftigen Arbeitsorten von H._ erkundigt. Dies mit der Begründung, sie habe ihn am gleichen Tag vor Zivilgericht auch in strafrechtlich relevanter Weise belastet. Im Folgenden habe er seinem Gesprächspartner vorgehalten, dieser habe ihn zu informieren, wenn Tänzerinnen mit Beschwerden an ihn gelangen würden. Aus dem Gespräch gehe hervor, dass er versucht habe, Schwachstellen von H._ ausfindig zu machen und den Gesprächspartner unter Druck zu setzen. Bei der Interpretation des Gesprächs sei freilich zu berücksichtigen, dass der Beschwerdeführer von der Telefonüberwachung bereits Kenntnis hatte.
Beeinflussungsversuche ergäben sich auch aus dem Abhörprotokoll eines Telefongesprächs vom 2. März 2015 mit einer Person namens "L._". Diesem habe der Beschwerdeführer gesagt: "Ich muss dich wegen dem Gericht ein paar Sachen fragen. Ich muss wissen, ob ich dich als Zeugen brauchen kann."
Hinzu komme die gerichtsnotorische Tatsache, dass im Rotlichtmilieu Druck- und Beeinflussungsversuche häufig vorkämen, besonders in Bezug auf Tänzerinnen und Prostituierte mit prekärem Aufenthaltsstatus.
Was die angebliche Entlastung durch die Tänzerin K._ angehe, illustriere der Verlauf der Einvernahme, unter welchem Druck sie offenbar stehe. Während sie in der Befragung vom 26. März 2015 noch relativ unbefangen Angaben zu ihren Erfahrungen und Beobachtungen im Club "B._" gemacht habe, habe sie in der Einvernahme vom Folgetag ihre belastenden Aussagen weitestgehend zurückgenommen und sich auf ihre schlechte Verfassung am Vortag sowie falsche Übersetzung berufen.
Vor diesem Hintergrund und weil beim derzeitigen Ermittlungsstand weitere Einvernahmen und Konfrontationen durchzuführen seien, sei der besondere Haftgrund der Kollusionsgefahr erfüllt.
4.3. Die Erwägungen des Appellationsgerichts genügen der Begründungspflicht gemäss <ref-law> ohne Weiteres. Die Verfassungsgarantie lässt zu, dass sich die Behörde auf die für den Entscheid wesentlichen Punkte beschränkt. Die Begründung muss so abgefasst sein, dass sich der Betroffene über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann (vgl. <ref-ruling> E. 6.2 S. 274; <ref-ruling> E. 5.2 S. 236; je mit Hinweisen). Die Vorinstanz hat in diesem Sinne aufgezeigt, weshalb sie beim Beschwerdeführer von einer Neigung zur Beeinflussung von Zeugen ausgeht. Dass sie mögliche Kollusionshandlungen im Einzelnen konkret beschreibt, ist dagegen nicht erforderlich. Der Beschwerdeführer wurde durch die vorinstanzliche Begründung durchaus in die Lage versetzt, eine Beschwerde mit gezielten Rügen zu erheben.
4.4. Die strafprozessuale Haft wegen Kollusionsgefahr soll verhindern, dass die beschuldigte Person die Freiheit dazu missbraucht, die wahrheitsgetreue Abklärung des Sachverhalts zu vereiteln oder zu gefährden. Konkrete Anhaltspunkte für Kollusionsgefahr können sich nach der Rechtsprechung des Bundesgerichts namentlich ergeben aus dem bisherigen Verhalten des Beschuldigten im Strafprozess, aus seinen persönlichen Merkmalen, aus seiner Stellung und seinen Tatbeiträgen im Rahmen des untersuchten Sachverhalts sowie aus den persönlichen Beziehungen zwischen ihm und den ihn belastenden Personen. Bei der Frage, ob im konkreten Fall eine massgebliche Beeinträchtigung des Strafverfahrens wegen Verdunkelung droht, ist auch der Art und Bedeutung der von Beeinflussung bedrohten Aussagen bzw. Beweismittel, der Schwere der untersuchten Straftaten sowie dem Stand des Verfahrens Rechnung zu tragen. Nach Abschluss der Strafuntersuchung bedarf der Haftgrund der Kollusionsgefahr einer besonders sorgfältigen Prüfung (<ref-ruling> E. 4.2 S. 127 f. mit Hinweis).
4.5. Nach den Feststellungen der Vorinstanz wie auch den Vorbringen in der Vernehmlassung der Staatsanwaltschaft ist die Untersuchung noch nicht abgeschlossen. Insbesondere sind demnach weitere Cabaret-Tänzerinnen und mutmassliche Abnehmer von Kokain einzuvernehmen. Zudem erhebt das Gericht an der Hauptverhandlung (auch bereits ordnungsgemäss erhobene) Beweise nochmals, sofern die unmittelbare Kenntnis des Beweismittels für die Urteilsfällung notwendig erscheint (<ref-law>; Urteil 1B_388/2012 vom 19. Juli 2012 E. 2.5 mit Hinweis, in: Pra 2012 Nr. 115 S. 801). Selbst wenn also bereits alle erdenklichen Beweise erhoben worden wären, wie der Beschwerdeführer behauptet, stünde dies der Annahme von Kollusionsgefahr nicht entgegen. Eine gerichtliche Einvernahme ist zudem vorliegend nicht unwahrscheinlich, zumal auch Delikte gegen die sexuelle Integrität infrage stehen und davon auszugehen ist, dass das erstinstanzliche Strafgericht einen persönlichen Eindruck von den Betroffenen gewinnen will.
Die erwähnten Tatvorwürfe, die auf Aussagen unterschiedlicher Personen zurückgehen, enthalten zudem Hinweise darauf, dass der Beschwerdeführer gewohnt ist, seine Forderungen mit Druck durchzusetzen. So wird ihm etwa vorgeworfen, die Autos von zwei Personen mit Säure demoliert zu haben, um seinen finanziellen Forderungen Nachdruck zu verleihen. Weiter soll er mit Cabaret-Tänzerinnen gegen deren Willen den Geschlechtsverkehr vollzogen haben. Die Tänzerin J._ sagte diesbezüglich in ihrer Einvernahme vom 20. April 2015 auf die Frage, ob sie sich in diesem Zusammenhang gewehrt habe: "Ich habe mich nicht gewehrt. Er kommt rein und nimmt, was er will. Sonst behandelt er einen wie ein Stück Scheisse. Ich war nicht die Einzige. So behandelt er noch viele Frauen. Wir sahen uns gezwungen, dies mitzumachen. Um die Arbeit nicht zu verlieren. Wir sind alle in einem fremden Land. Wir wissen nicht, wie wir uns hier verhalten sollen."
Die Vorinstanz weist weiter zu Recht darauf hin, dass K._ in ihrer Einvernahme vom 26. März 2015 offen über die Arbeitsbedingungen im Club "B._" berichtete, am Folgetag jedoch zentrale Aussagen wieder zurücknahm oder angab, dies nicht so gesagt zu haben. So gab sie zunächst an, dass sie sich beim "privaten" Tanzen vollständig ausziehen müsse, dass es mal Streit gegeben habe, weil sie ihre Kleider anbehalten wollte, und dass sich andere Tänzerinnen im Club "B._" prostituierten. Tags darauf sagte sie dagegen, selber keinen Striptease getanzt bzw. sich nicht ganz ausgezogen zu haben. Auch die Aussage, dass sich Tänzerinnen prostituieren würden, nahm sie zurück. Zum am Vortag ebenfalls protokollierten Satz "man bekommt dann Drogen im Essen oder im Getränk" meinte sie, so etwas nicht gesagt zu haben.
Mit der Tätigkeit des Beschwerdeführers als Betreiber eines Nachtklubs sind schliesslich regelmässig Kontakte zu kriminellen Milieus verbunden. Insgesamt muss deshalb damit gerechnet werden, dass er in der Lage und angesichts der für den Fall einer Verurteilung drohenden Strafe auch gewillt sein könnte, die gerichtliche Wahrheitsfindung auf diese Weise zu beeinträchtigen. Sexualdelikte, wie sie hier zum Teil zur Diskussion stehen, sind der Kollusion besonders zugänglich. Der Einwand des Beschwerdeführers, er hätte bereits früher Gelegenheit gehabt zu kolludieren, überzeugt nicht. Obwohl er offenbar von der Telefonüberwachung Kenntnis hatte, waren ihm damals die konkreten Tatvorwürfe nicht bekannt, ebensowenig, auf welche Beweise sich diese stützen.
Die Vorinstanz hat aus diesen Gründen kein Bundesrecht verletzt, wenn sie von Kollusionsgefahr ausging. Wie es sich mit den weiteren von ihr angeführten Indizien für Kollusionsgefahr, insbesondere mit den erwähnten abgehörten Telefongesprächen verhält, kann offen bleiben.
Dass die Kollusionsgefahr mit Ersatzmassnahmen gebannt werden könnte, macht der Beschwerdeführer nicht geltend und ist auch nicht ersichtlich.
4.6. Bei diesem Ergebnis drängte es sich für die Vorinstanz nicht auf, zusätzliche Haftgründe zu prüfen (vgl. Urteil 1B_728/2011 vom 13. Januar 2012 E. 2.7). Die Rüge des Beschwerdeführers, das Appellationsgericht habe den Beschleunigungsgrundsatz in Haftsachen verletzt, indem es seine Prüfung auf den besonderen Haftgrund der Kollusionsgefahr beschränkte, ist unbegründet.
5.
Die Beschwerde ist aus den genannten Gründen abzuweisen, soweit darauf einzutreten ist.
Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege. Er hat seine finanziellen Verhältnisse jedoch nicht hinreichend offen gelegt, als dass beurteilt werden könnte, ob er nicht über die erforderlichen Mittel verfügt (<ref-law>). Das Gesuch ist deshalb abzuweisen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4.
Es wird keine Parteientschädigung zugesprochen.
5.
Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft des Kantons Basel-Stadt und dem Appellationsgericht des Kantons Basel-Stadt, Einzelgericht, schriftlich mitgeteilt.
Lausanne, 23. Juni 2015
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold