Sachverhalt:
A.
A._ (geb. 1982) ist tunesischer Staatsangehöriger und reiste im September 2012 illegal in die Schweiz ein. Am 6. September 2012 stellte er ein Asylgesuch, auf welches das Staatssekretariat für Migration (SEM, damals Bundesamt für Migration BFM) mit Entscheid vom 26. November 2012 nicht eintrat, weil die Zuständigkeit für die Durchführung des Asylverfahrens bei Italien lag.
Mit Urteil vom 1. Oktober 2013 sprach das Strafgericht Basel-Landschaft A._ des gewerbsmässigen und bandenmässigen Diebstahls, der mehrfachen Sachbeschädigung sowie der Geldwäscherei schuldig und verurteilte ihn unter Anrechnung von seit dem 21. November 2012 ausgestandenen 159 Tagen Untersuchungshaft zu einer Freiheitsstrafe von 3 1/2 Jahren mit effektivem Strafende am 20. Mai 2016.
Da A._ nicht fristgerecht nach Italien überstellt wurde, verfügte das SEM am 15. Januar 2014 die Aufhebung des asylrechtlichen Nichteintretensentscheids vom 26. November 2012 und die Wiederaufnahme des Asylverfahrens. Mit Entscheid vom 14. Februar 2014 lehnte es das Asylgesuch von A._ ab und wies ihn aus der Schweiz weg. Mit dem Wegweisungsvollzug beauftragte das SEM den Kanton Basel-Landschaft.
Auf Gesuch von A._ bewilligte die Sicherheitsdirektion des Kantons Basel-Landschaft mit Verfügung vom 9. Februar 2015 seine bedingte Entlassung aus dem Strafvollzug per 20. März 2015, "sofern [...] die Ausschaffung durch das Amt für Migration Basel-Landschaft zu diesem Zeitpunkt vollzogen werden kann. Der Strafrest richtet sich nach dem effektiven Datum der bedingten Entlassung, bzw. dem Ausschaffungsdatum. A._ bleibt bis zum Zeitpunkt der Ausschaffung im Strafvollzug."
B.
Mit Haftbefehl vom 20. Mai 2016 nahm das Amt für Migration des Kantons Basel-Landschaft A._ in Ausschaffungshaft und beantragte dem Kantonsgericht Basel-Landschaft die Anordnung von Ausschaffungshaft zur Sicherstellung der Durchführung des Wegweisungsverfahrens. Am 24. Mai 2016 bestätigte das Kantonsgericht die Anordnung der Ausschaffungshaft bis zum 19. August 2016.
C.
A._ führt mit Eingabe vom 20. Juni 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt die Aufhebung des Urteils vom 24. Mai 2016 und seine sofortige Entlassung aus der Haft. Weiter verlangt er eine Entschädigung für widerrechtlich ausgestandene Ausschaffungshaft zulasten des Kantons Basel-Landschaft.
Während das Kantonsgericht auf eine Stellungnahme verzichtet, verweist das SEM auf die Ausführungen im vorinstanzlichen Urteil. Das Amt für Migration schliesst sinngemäss auf Abweisung der Beschwerde. Mit Eingabe vom 5. Juli 2016 hält der Beschwerdeführer an seinen Anträgen und der Begründung fest.

Erwägungen:
1.
Das Bundesgericht prüft seine Zuständigkeit und die weiteren Eintretensvoraussetzungen von Amtes wegen (Art. 29 Abs. 1 BGG) und mit freier Kognition (<ref-ruling> E. 1 S. 116).
1.1. Die frist- (Art. 100 Abs. 1 BGG) und formgerecht (Art. 42 Abs. 2 BGG) eingereichte Beschwerde betrifft eine Angelegenheit des öffentlichen Rechts (Art. 82 lit. a BGG) und richtet sich gegen den kantonal letztinstanzlichen (Art. 86 Abs. 1 lit. d BGG), verfahrensabschliessenden Entscheid (Art. 90 BGG) eines oberen Gerichts (Art. 86 Abs. 2 BGG; vgl. zu den diesbezüglichen Anforderungen an das kantonale Verfahren <ref-ruling> E. 1.2.2 S. 210; <ref-ruling> E. 3 S. 96 f.). Der Anordnung ausländerrechtlicher Administrativhaft kommt aufgrund ihres schweren Eingriffs in die persönliche Freiheit eigenständiger Charakter zu; sie erscheint nicht als bloss untergeordnete Vollzugsmassnahme zur Wegweisung. Die Beschwerde ist somit auch unter dem Blickwinkel von Art. 83 lit. c Ziff. 4 BGG zulässig (vgl. <ref-ruling> E. 1 S. 24 f.; <ref-ruling> E. 5.5 S. 101; Urteil 2C_207/2016 vom 2. Mai 2016 E. 1.1.3 [zur Publikation vorgesehen]). Auf die Beschwerde des vom angefochtenen Entscheid in schutzwürdigen Interessen unmittelbar betroffenen Beschwerdeführers (Art. 89 Abs. 1 BGG) ist somit unter Vorbehalt der nachstehenden Erwägung einzutreten.
1.2. Vor Bundesgericht ersucht der Beschwerdeführer erstmals darum, ihm bei einer Gutheissung der Beschwerde eine Entschädigung für unzulässige Ausschaffungshaft zuzusprechen. Dieser Antrag geht über den vorinstanzlichen Verfahrensgegenstand hinaus und bildet ein unzulässiges neues rechtliches Begehren (Art. 99 Abs. 2 BGG), zumal Ansprüche auf Haftentschädigung nicht bereits wegen Art. 5 Ziff. 5 EMRK Gegenstand des Haftprüfungsverfahrens bilden (vgl. EGMR-Urteile Jusic gegen Schweiz vom 2. Dezember 2010 [Nr. 4691/06] §§ 103 ff.; <ref-ruling> E. 6 S. 303 f.; <ref-ruling> E. 3 S. 142; Urteile 2C_539/2015 vom 20. Juli 2015 E. 2.3; 2C_168/2013 vom 7. März 2013 E. 1.2). Soweit der Beschwerdeführer mit seinem Rechtsmittel eine Entschädigung für die angeordnete Ausschaffungshaft verlangt, erweist sich die Beschwerde somit als unzulässig und ist auf sie nicht einzutreten.
2.
Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann namentlich die Verletzung von Bundes- und Völkerrecht gerügt werden (Art. 95 lit. a und lit. b BGG). Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 2 BGG), grundsätzlich nur die geltend gemachten Vorbringen, sofern allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.6 S. 280 f. mit Hinweis). Die Verletzung von Grundrechten untersucht das Bundesgericht in jedem Fall nur insoweit, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG; <ref-ruling> E. 3 S. 415; <ref-ruling> E. 2.2 S. 232).
3.
3.1. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Eine Berichtigung oder Ergänzung der vorinstanzlichen Sachverhaltsfeststellungen ist von Amtes wegen (Art. 105 Abs. 2 BGG) oder auf Rüge hin (Art. 97 Abs. 1 BGG) möglich. Von den tatsächlichen Grundlagen des vorinstanzlichen Urteils weicht das Bundesgericht jedoch nur ab, wenn diese offensichtlich unrichtig sind oder sie auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruhen und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (Art. 97 Abs. 1, Art. 105 Abs. 2 BGG; <ref-ruling> E. 1.3.1 S. 17 f.).
3.2. Neue Tatsachen und Beweismittel dürfen im bundesgerichtlichen Verfahren nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG, Urteile 2C_347/2012 vom 26. März 2013 E. 2.5 und 2.6 [nicht publ. in: <ref-ruling>]; 2C_1017/2012 vom 30. Oktober 2012 E. 2).
3.2.1. Zusammen mit der Beschwerde reicht der Beschwerdeführer eine Verfügung vom 9. Februar 2015 ein, mit welcher die Sicherheitsdirektion des Kantons Basel-Landschaft ihm unter Vorbehalt seiner gleichzeitigen Ausschaffung die bedingte Entlassung aus dem Strafvollzug per 20. März 2015 bewilligte (vgl. Sachverhalt lit. A hiervor). Der Beschwerdeführer macht unter Hinweis auf die Verfügung vom 9. Februar 2015 geltend, dass er entgegen der Feststellungen der Vorinstanz, wonach er am 20. Mai 2016 vorzeitig aus dem Strafvollzug entlassen worden sei, an diesem Datum die Strafe im Gegenteil bereits vollständig verbüsst hatte.
3.2.2. Das Amt für Migration ist als Empfänger auf der Verfügung vom 9. Februar 2015 vermerkt. Aus unerfindlichen Gründen ist diese in den Verfahrensakten jedoch nicht vorhanden. Worauf sich die Vorinstanz in ihrer Annahme stützt, wonach der Beschwerdeführer am 20. Mai 2016 vorzeitig und nicht definitiv aus dem Strafvollzug entlassen worden sei, ist sodann nicht ersichtlich. Der Beschwerdeführer war somit erst durch das vorinstanzliche Urteil veranlasst, die Verfügung vom 9. Februar 2015 im bundesgerichtlichen Verfahren vorzubringen. Seine diesbezüglich neuen Ausführungen in tatsächlicher Hinsicht und die Verfügung vom 9. Februar 2015 als neues Beweismittel sind zulässig (Art. 99 Abs. 1 BGG).
3.2.3. Gestützt auf die rechtsgenüglich begründete Rüge des Beschwerdeführers (vgl. zu den Anforderungen bei Sachverhaltsrügen <ref-ruling> E. 9.2.3.6 S. 96; <ref-ruling> E. 1.4.3 S. 254 f.) und die Verfügung vom 9. Februar 2015 ist im Übrigen davon auszugehen, dass seine Darstellung zutrifft und eine bedingte Entlassung bereits am 20. März 2015 möglich gewesen wäre. Die diesbezüglich anders gelagerte Sachverhaltsfeststellung der Vorinstanz erweist sich mangels anders lautender Hinweise in den Akten (Art. 105 Abs. 2 BGG) oder Stellungnahmen der Verfahrensbeteiligten als offensichtlich unrichtig und ist entsprechend zu korrigieren. Auszugehen ist somit vom eingangs dargelegten Sachverhalt (vgl. Sachverhalt lit. A).
4.
4.1. Wurde ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, kann die zuständige Behörde den betroffenen Ausländer zur Sicherstellung des Vollzugs namentlich dann in Ausschaffungshaft nehmen, wenn er wegen eines Verbrechens verurteilt worden ist (Art. 76 Abs. 1 lit. b Ziff. 1 i.V.m. Art. 75 Abs. 1 lit. h AuG; Urteile 2C_112/2016 vom 19. Februar 2016 E. 2.1; 2C_749/2012 vom 28. August 2012 E. 1, 2C_455/2009 vom 5. August 2009 E. 2.1, je mit Hinweisen). Der Wegweisungsentscheid muss dabei nicht bereits rechtskräftig sein; es genügt, dass sein Vollzug (z.B. wegen fehlender Papiere) noch nicht möglich, jedoch absehbar erscheint. Der Vollzug der Weg- oder Ausweisung darf sich nicht aus rechtlichen oder tatsächlichen Gründen als undurchführbar erweisen (vgl. Art. 80 Abs. 6 lit. a AuG) und muss mit dem nötigen Nachdruck verfolgt werden (Art. 76 Abs. 4 AuG: "Beschleunigungsgebot"). Die ausländerrechtliche Festhaltung muss zudem insgesamt verhältnismässig sein (<ref-ruling> E. 2.3.2 S. 97; Urteile 2C_765/2015 vom 18. September 2015 E. 5.3; 2C_334/2015 vom 19. Mai 2015 E. 2.2; 2C_218/2013 vom 26. März 2013 E. 5.1).
4.2. Dass die Haftvoraussetzungen nach Art. 76 Abs. 1 lit. b Ziff. 1 i.V.m. Art. 75 Abs. 1 lit. h AuG (eröffneter Wegweisungsentscheid, Verurteilung zu einem Verbrechen) vorliegend erfüllt sind, wird von keiner Seite bestritten. Der Beschwerdeführer rügt die angeordnete Ausschaffungshaft jedoch als unverhältnismässig und macht zudem eine Verletzung des Beschleunigungsgebots geltend.
Letzteres begründet der Beschwerdeführer damit, dass aus den Akten keinerlei Vorkehrungen ersichtlich seien, die das Amt für Migration seit dem Wegweisungsentscheid des SEM vom 14. Februar 2014 im Hinblick auf den Vollzug der Wegweisung getroffen habe. Obwohl die Sicherheitsdirektion des Kantons Basel-Landschaft grundsätzlich die bedingte Entlassung per 20. März 2015 bewilligt habe, sei er erst am 20. Mai 2016 zum ordentlichen Strafende aus dem Strafvollzug entlassen und sogleich in Ausschaffungshaft versetzt worden. Aus dem angefochtenen Entscheid gehe zudem hervor, dass die Vorbereitungen für den Wegweisungsvollzug erst noch anhand genommen werden müssten. Mit diesem Vorgehen habe das Amt für Migration das Beschleunigungsgebot verletzt.
Das Amt für Migration legt in seiner Stellungnahme vom 1. Juli 2016 dar, dass es das SEM am 15. März 2016 um Unterstützung beim Vollzug der Wegweisung ersucht habe. Der Antrag um Identifizierung des Beschwerdeführers sei vom SEM alsdann zusammen mit weiteren Identifizierungsanträgen am 14. Juni 2016 zuhanden der zuständigen tunesischen Behörde an die schweizerische Vertretung in Tunesien weitergeleitet worden. Die Abklärungen betreffend die Identität des Beschwerdeführers seien somit zwei Monate vor dessen Entlassung aus dem Strafvollzug am 20. Mai 2016 an die Hand genommen worden.
4.3. Die Freiheit darf einer Person nach Art. 31 Abs. 1 BV nur in den vom Gesetz selbst vorgesehenen Fällen und nur auf die im Gesetz vorgeschriebene Weise entzogen werden (vgl. auch Art. 5 Ziff. 1 lit. f EMRK). Im Hinblick auf die Modalitäten der Ausschaffungshaft präzisiert Art. 76 Abs. 4 AuG diese Verfassungsbestimmung dahingehend, dass die für den Vollzug der Weg- oder Ausweisung notwendigen Vorkehren umgehend zu treffen sind. Das so verankerte Beschleunigungsgebot gilt als verletzt, wenn während mehr als zwei Monaten keinerlei Vorkehren mehr im Hinblick auf den Vollzug der Wegweisung getroffen wurden (Untätigkeit der Behörden), ohne dass die Verzögerung in erster Linie auf das Verhalten ausländischer Behörden oder des Betroffenen selber zurückgeht (<ref-ruling> E. 2.1 S. 211; <ref-ruling> E. 3a S. 50 f.; Urteile 2C_1182/2014 vom 20. Januar 2015 E. 3.2.1, je mit Hinweisen).
Befindet sich der weggewiesene Ausländer in Untersuchungshaft oder im Strafvollzug, so ist die für den Vollzug der Entfernungsmassnahme zuständige Behörde verpflichtet, die notwendigen Schritte nach Möglichkeit schon vor der Entlassung einzuleiten, damit der Betroffene nicht mehr unnötig oder nicht unnötig lange in Ausschaffungshaft genommen werden muss (<ref-ruling> E. 4.1 S. 492; <ref-ruling> E. 3a S. 50 f.; Urteil 2C_112/2016 vom 19. Februar 2016 E. 2.2.2). Eine Vorbereitung des Wegweisungsvollzugs bereits während dem Strafvollzug oder der Untersuchungshaft ist nicht nur im Interesse des Schutzes der persönlichen Freiheit der inhaftierten Person (Art. 10 Abs. 2 BV) erforderlich, sondern dient auch der Verringerung der Vollzugskosten und damit dem haushälterischen Umgang mit öffentlichen Mitteln.
4.3.1. Im vorliegenden Fall bewilligte die Sicherheitsdirektion des Kantons Basel-Landschaft mit Verfügung vom 9. Februar 2015 die bedingte Entlassung des Beschwerdeführers per 20. März 2015, "sofern sein Verhalten im Vollzug weiterhin klaglos verläuft und die Ausschaffung durch das Amt für Migration Basel-Landschaft zu diesem Zeitpunkt vollzogen werden kann. Der Strafrest richtet sich nach dem effektiven Datum der bedingten Entlassung, bzw. dem Ausschaffungsdatum". Ob das Vorgehen der Sicherheitsdirektion vor Art. 86 Abs. 1 StGB standhält, zumal sie bei der Bewährungsprognose keine Unterscheidung nach dem Aufenthaltsort des Beschwerdeführers in der Schweiz oder in seiner Heimat traf (vgl. CORNELIA KOLLER, in: Basler Kommentar, Strafrecht I, 3. Aufl. 2013, N. 20 zu Art. 86 StGB) erscheint fraglich, ist jedoch nicht Gegenstand des bundesgerichtlichen Verfahrens.
4.3.2. Aufgrund der Verfügung vom 9. Februar 2015 steht immerhin fest, dass die Haftentlassung des Beschwerdeführers ab dem 20. März 2015 bei gleichzeitiger Ausschaffung unverzüglich oder zu jedem späteren Zeitpunkt hätte erfolgen können. Dennoch gelangte das Amt für Migration ohne nachvollziehbaren Grund erst am 15. März 2016 und damit rund ein Jahr später mit einem Gesuch um Vollzugsunterstützung an das SEM. Dass das Amt für Migration vor dem 15. März 2016 irgendwelche Vorkehrungen im Hinblick auf den Wegweisungsvollzug getroffen hätte, ist nicht ersichtlich. Vielmehr vermerkte das Amt für Migration in seinem Gesuch um Vollzugsunterstützung vom 15. März 2016 an das SEM, dass die kantonalen Behörden bislang noch keine Vollzugsmassnahmen getroffen hätten. Von untergeordneter Bedeutung erscheint dabei, dass der Beschwerdeführer selber offenbar keine Reisedokumente vorlegt oder vorlegen kann: Neben dem Umstand, dass es dem seit mehr als 3 1/2 Jahren inhaftierten Beschwerdeführer bereits aus praktischen Gründen schwer fallen dürfte, selbständig aktuelle Dokumente zu besorgen (vgl. <ref-ruling> E. 2.3.2 S. 97), ist nicht zu erkennen, inwiefern er einen Vollzug der Wegweisung in seine Heimat aktiv zu verhindern suchte. Hinzu kommt, dass die allenfalls fehlende Mitwirkung des Ausländers die Behörden nicht von der Pflicht entbindet, den Wegweisungsvollzug ernsthaft und mit Nachdruck voran zu treiben (vgl. <ref-ruling> E. 2.3 S. 212).
4.3.3. Somit wurde das Beschleunigungsgebot (Art. 76 Abs. 4 AuG) mit der Untätigkeit des Amts für Migration zwischen der verfügten bedingten Entlassung am 9. Februar 2015 und dem Gesuch um Vollzugsunterstützung am 15. März 2016 offenkundig verletzt. Bei dieser Sachlage ist nicht weiter zu prüfen, ob mit Blick auf die zitierte bundesgerichtliche Rechtsprechung (vgl. E. 4.3) eine Verletzung des Beschleunigungsgebots auch darin zu erblicken ist, dass das SEM den Antrag um Identifizierung des Beschwerdeführers an die tunesischen Behörden erst am 14. Juni 2016 und damit rund drei Monate nach dem kantonalen Gesuch um Vollzugsunterstützung an die schweizerische Vertretung in Tunesien weitergeleitet hat.
Die Verletzung des Beschleunigungsgebots führt zur Haftentlassung, zumal gestützt auf die Sachverhaltsfeststellungen der Vorinstanz keine Hinweise auf ein nennenswertes Sicherheitsrisiko bestehen (vgl. <ref-ruling> E. 2.4 S. 212 f.; Urteil 2A.115/2002 vom 19. März 2002 E. 4a). Ob der vorinstanzliche Entscheid, wie vom Beschwerdeführer geltend gemacht, neben dem Beschleunigungsgebot auch das Verhältnismässigkeitsprinzip verletzt, ist bei diesem Verfahrensausgang nicht näher zu prüfen.
4.3.4. Den Behörden bleibt es derweil unbenommen, dem Beschwerdeführer gegenüber eine Ein- oder Ausgrenzung anzuordnen, soweit die gesetzlichen Voraussetzungen dafür erfüllt sind (Art. 74 Abs. 1 lit. a und lit. b AuG). Zweck dieser Massnahme ist es, den Verbleib der ausländischen Person zu kontrollieren sowie ihre Verfügbarkeit für die Vorbereitung des Vollzugs der Wegweisung weiterhin sicherzustellen. Sie ist milderes Mittel zur Administrativhaft und darf analog diesem auch eine gewisse Druckwirkung zur Durchsetzung der Ausreisepflicht enthalten. Die Missachtung einer Ein- oder Ausgrenzung kann mit Freiheitsstrafe bis zu drei Jahren oder Geldstrafe geahndet werden (Art. 119 AuG; vgl. zum Ganzen <ref-ruling> E. 2.4 S. 213).
5.
Nach dem Dargelegten ist die Beschwerde gutzuheissen, soweit auf sie einzutreten ist. Bei diesem Verfahrensausgang wird der Kanton Basel-Landschaft entschädigungspflichtig (Art. 68 Abs. 2 BGG). Gerichtskosten werden nicht erhoben (Art. 66 Abs. 4 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist und das Urteil des Kantonsgerichts Basel-Landschaft, Einzelrichter, vom 24. Mai 2016, wird aufgehoben. Der Beschwerdeführer ist unverzüglich aus der Haft zu entlassen.
2.
2.1. Es werden keine Kosten erhoben.
2.2. Der Kanton Basel-Landschaft hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Kantonsgericht Basel-Landschaft, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 12. Juli 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Zünd
Der Gerichtsschreiber: Fellmann