A.- X._, prétendument originaire de Guinée- Bissau, a présenté le 21 décembre 1998 une demande d'asile.
Le 14 avril 1999, l'Office fédéral des réfugiés a rejeté cette demande et invité le prénommé à quitter la Suisse, sous peine de refoulement. Statuant sur recours le 9 novembre 1999, la Commission suisse de recours en matière d'asile a confirmé le renvoi de X._. Celui-ci a été annoncé disparu le 25 janvier 2000.
Le 2 août 2000, X._ a déposé une nouvelle demande d'asile sur laquelle l'Office fédéral des réfugiés n'est pas entré en matière selon décision du 27 septembre 2000. Cette autorité a de nouveau ordonné le renvoi immédiat de l'intéressé et retiré l'effet suspensif à un éventuel recours.
Le canton du Valais a été chargé de l'exécution du renvoi. Le 23 novembre 2000, la Commission suisse de recours en matière d'asile n'est pas entrée en matière sur le recours formé par l'intéressé faute de paiement de l'avance de frais.
Le 31 octobre 2000, le Service de l'état civil et des étrangers du canton du Valais (ci-après: le Service des étrangers) a présenté à la Division "rapatriements" de l'Office fédéral des réfugiés une demande de soutien à l'exécution du renvoi de X._, en application de l'ordonnance du 11 août 1999 sur l'exécution du renvoi et de l'expulsion d'étrangers (OERE; RS 142. 281).
L'office en question a adressé ensuite des demandes de comparaisons dactyloscopiques aux autorités belges et françaises. Les renseignements (négatifs) ont été reçus par l'office en cause les 2 février et 11 mai 2001. Le Service des étrangers a de son côté soumis l'intéressé à un test linguistique.
Selon un rapport du 14 février 2001, X._ ne serait probablement pas originaire de Guinée Bissau, mais plutôt de Guinée.
Soupçonné d'avoir enfreint la loi fédérale sur les stupéfiants, X._ a été mis en détention préventive du 13 octobre au 13 décembre 2000, à Lausanne, et du 9 avril au 11 octobre 2001, à Orbe.
Par jugement du 11 octobre 2001, le Tribunal correctionnel d'arrondissement de Lausanne a condamné X._ pour infraction à la loi fédérale sur les stupéfiants à la peine de six mois d'emprisonnement, peine entièrement compensée par la détention préventive, et à une expulsion de Suisse pour une durée de trois ans. Le tribunal a ordonné la libération immédiate de X._, à moins que celui-ci ne soit détenu pour une autre cause.
B.- Le 10 octobre 2001, la Police cantonale du Valais a interrogé X._ à la prison d'Orbe en vue d'organiser son départ de Suisse. Le même jour, le Service des étrangers a ordonné la mise en détention de l'intéressé pour une durée maximale de trois mois en vue du refoulement, cette décision prenant effet dès que X._ aurait satisfait aux exigences de la justice vaudoise et serait libéré.
Par arrêt du 12 octobre 2001, le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Juge de la détention) a examiné et confirmé l'ordre de mise en détention, après avoir entendu oralement X._ et une représentante du Service des étrangers. En revanche, l'avocat-stagiaire, qui avait assisté l'intéressé dans la procédure pénale qui s'était déroulée dans le canton de Vaud, n'avait pas été averti de la tenue de cette audience.
Le Juge de la détention lui a toutefois notifié son arrêt du 12 octobre 2001, tout en l'invitant à l'informer sur la façon dont il entendait s'acquitter du mandat qu'il disait avoir reçu de X._ et dont l'existence ne ressortait pas du dossier.
Par lettre du 18 octobre 2001 adressée au Juge de la détention, le conseil de X._ a sollicité la reconsidération de l'arrêt du 12 octobre 2001, l'annulation de l'ordre de mise en détention du 10 octobre 2001 et, enfin, la mise en liberté immédiate de X._. Il a alors renoncé à une nouvelle audience avec débats oraux.
Par arrêt du 2 novembre 2001, le Juge de la détention a rejeté la demande en reconsidération ainsi que la demande de libération.
C.- Agissant seul par la voie du recours de droit administratif, X._ demande au Tribunal fédéral d'annuler l'arrêt du Juge de la détention du 2 novembre 2001, tout en sollicitant un délai supplémentaire pour déposer un mémoire complémentaire rédigé par son avocat.
Le Service des étrangers conclut au rejet du recours.
Le Juge de la détention s'est exprimé sur la question du principe de diligence mais n'a pas pris de conclusions expresses.
Ayant été informé de l'ouverture d'une procédure de recours fédérale, l'avocat-stagiaire, qui était intervenu comme mandataire de l'intéressé dans la procédure cantonale en matière de mesures de contrainte, s'est déterminé sur les observations du Service des étrangers le 24 novembre 2001.
Par ordonnance du 23 novembre 2001, le Président de la IIe Cour de droit public a invité l'Office fédéral des étrangers, d'entente avec l'Office fédéral des réfugiés, à déposer un rapport sur la question du principe de célérité.
Le 28 novembre 2001, l'Office fédéral des étrangers a fait parvenir sa réponse avec un rapport de l'Office fédéral des réfugiés daté du 26 novembre 2001.
L'avocat-stagiaire, qui avait assisté l'intéressé dans la procédure cantonale, a été invité à déposer ses éventuelles observations sur les rapports en question, dans la mesure où il entendait intervenir formellement comme mandataire du recourant, ce qu'il a fait par acte du 3 décembre 2001 en y joignant une procuration justifiant de ses pouvoirs.

Considérant en droit :
1.- L'arrêt attaqué du 2 novembre 2001 ne constitue pas à proprement parler une décision contrôlant l'ordre de mise en détention. Il s'agit plutôt en quelque sorte du refus de reconsidérer une décision antérieure. Bien qu'il constate que les conditions d'une reconsidération de l'arrêt du 12 octobre 2001 ne sont pas réunies et donc rejette une telle demande, le Juge de la détention a néanmoins examiné de nouveau le bien-fondé et la légalité de la détention, en tenant compte cette fois des déterminations du mandataire du recourant qui ont été déposées à la suite de la notification de l'arrêt du 12 octobre 2001. Dans ces conditions, le présent recours de droit administratif dirigé contre l'arrêt du 2 novembre 2001 est recevable, l'objet de la procédure fédérale portant sur la légalité de la détention en vue de refoulement.
2.- Selon l'art. 13b de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 142. 20), si une décision de renvoi ou d'expulsion de première instance (donc pas forcément exécutoire ou définitive) a été notifiée, l'autorité cantonale compétente peut, aux fins d'en assurer l'exécution, mettre en détention l'étranger en vue du refoulement (<ref-ruling> consid. 2 p. 61; <ref-ruling> consid. 3a p. 374; <ref-ruling> consid. 1 p. 150). Il est nécessaire que l'exécution du renvoi soit momentanément impossible (p. ex. faute de papiers d'identité), mais possible dans un délai prévisible (ATF <ref-ruling> consid. 3a p. 374, 377 consid. 2a p. 379). Encore faut-il que l'un des motifs de détention prévus à l'art. 13b al. 1 LSEE soit réalisé (ATF <ref-ruling> consid. 3a p. 374, 377 consid. 3a p. 381; <ref-ruling> consid. 1 p. 3) et que l'exécution du renvoi ou de l'expulsion ne s'avère pas d'emblée impossible pour des raisons juridiques ou matérielles (cf. art. 13c al. 5 let. a LSEE; voir <ref-ruling> consid. 2 p. 220, 377 consid. 5 p. 384). Quant aux autorités, elles doivent entreprendre sans tarder les démarches nécessaires (établissement de l'identité et de l'origine, obtention d'un document de voyage, etc.) à l'exécution de la mesure d'éloignement (art. 13b al. 3 LSEE, principe de célérité; cf. <ref-ruling> ss). En outre, la détention (respectivement sa durée) doit respecter le principe de la proportionnalité (<ref-ruling> consid. 4 p. 383; <ref-ruling> consid. 2c p. 198; voir aussi ATF <ref-ruling> consid. 3 p. 152 ss). Il faut aussi respecter les conditions légales d'exécution de la détention (cf. art. 13c al. 3 et 13d LSEE; cf.
ATF 123 I 221; <ref-ruling>; <ref-ruling>). La légalité et l'adéquation de la détention ordonnée par l'autorité cantonale compétente pour l'exécution du renvoi ou d'expulsion (cf.
art. 13c al. 1 LSEE) doivent être examinées dans les 96 heures au plus tard par une autorité judiciaire au terme d'une procédure orale (art. 13c al. 2 LSEE).
Selon l'art. 13d al. 1 LSEE, les cantons veillent à ce qu'une personne, désignée par le détenu et se trouvant en Suisse, soit prévenue et que l'intéressé puisse s'entretenir et correspondre avec son mandataire. L'étranger placé en détention en vue du refoulement a le droit d'être assisté par un mandataire professionnel dans la procédure de mise en détention en vue de refoulement et dans la procédure de contrôle judiciaire subséquente (<ref-ruling> consid. 2c p. 157).
3.- a) Dans la procédure pénale qui s'est déroulée dans le canton de Vaud, le recourant était assisté d'un mandataire professionnel. Ce n'est qu'après l'audition du recourant par le Juge de la détention, audition qui ne pouvait être repoussée puisqu'elle devait avoir lieu dans les 96 heures au plus tard selon l'art. 13c al. 2 LSEE, que le mandataire en question a manifesté son intention de représenter le recourant également dans le cadre de la procédure en vue de refoulement. Cela n'est pas contesté par le recourant lui-même, ni contredit par une pièce du dossier. Vu les circonstances, il n'était en tout cas pas judicieux de surseoir à l'arrêt du Juge de la détention et de fixer immédiatement une nouvelle audience. Les exigences de l'art. 13d al. 1 LSEE peuvent être considérées comme satisfaites lorsque le Juge de la détention s'est prononcé sur la légalité et l'adéquation de la détention après audition du mandataire, sans avoir à attendre l'écoulement du délai de l'art. 13c al. 4 LSEE.
b) En l'espèce, la détention en vue de refoulement vise à garantir l'exécution du renvoi ordonné dans le cadre d'une procédure d'asile, ce qui est conforme au but de la loi. En outre, le motif de détention de l'art. 13b al. 1 let. c LSEE invoqué par les autorités cantonales est réalisé, car il existait suffisamment d'indices concrets faisant craindre que le recourant n'entende se soustraire au refoulement:
il a en effet refusé de retourner dans son pays d'origine, même après la deuxième décision rejetant définitivement sa demande d'asile. Il a fréquenté le milieu de la drogue et il est resté introuvable pendant une assez longue période.
Dans la procédure d'asile, il a en outre fait des déclarations invraisemblables et contradictoires sur son origine et sur son lieu de séjour entre les deux procédures d'asile (cf.
ATF <ref-ruling> consid. 3b/aa p. 375; <ref-ruling> consid. 2a p. 50 ss; voir aussi ATF <ref-ruling> consid. 2b p. 198). En outre, on ne saurait affirmer aujourd'hui que l'exécution de son renvoi ne pourrait pas avoir lieu dans un délai raisonnable.
Le recourant fait uniquement valoir que la détention en vue de refoulement n'est pas justifiée selon le principe de célérité. Il convient donc d'examiner si tel est le cas en l'espèce.
4.- a) Selon l'art. 13b al. 3 LSEE, les démarches nécessaires à l'exécution du renvoi ou de l'expulsion doivent être prises sans tarder (principe de diligence ou de célérité).
Les autorités cantonales doivent donc essayer d'établir l'identité de l'étranger le plus rapidement possible et de se procurer les papiers nécessaires au refoulement de celui-ci.
Toutes les mesures qui semblent propres à accélérer l'exécution du refoulement doivent être prises. Souvent, il peut s'avérer utile de présenter l'intéressé à la représentation de son pays d'origine ou de demander un soutien à l'exécution du renvoi aux autorités fédérales (cf. ordonnance du 11 août 1999 sur l'exécution du renvoi et de l'expulsion d'étrangers; OERE). Inversement, il n'existe aucune obligation pour les autorités de procéder de manière schématique et identique dans chaque cas en prenant des mesures déterminées. Le principe de célérité oblige simplement les autorités à prendre les mesures qui, vu les circonstances concrètes du cas particulier, sont de nature à activer l'exécution du refoulement.
Les mesures à prendre par les autorités responsables doivent être appréciées globalement en fonction des circonstances du cas d'espèce. La question de savoir si le principe de diligence a été violé dépend donc des particularités du cas d'espèce.
Dans ce contexte, il peut être tenu compte d'un manque de coopération de la part de l'étranger. Un tel comportement ne saurait toutefois justifier l'inactivité des autorités.
Elles doivent essayer d'établir l'identité de l'étranger et de se procurer les papiers nécessaires à son refoulement, avec ou sans la collaboration de l'étranger. Il faut en outre prendre en considération le fait que l'aide requise des autorités étrangères peut parfois traîner en longueur. On ne saurait donc reprocher aux autorités une violation du principe de diligence lorsque le retard dans l'obtention des papiers d'identité est imputable exclusivement au manque de collaboration d'une représentation diplomatique étrangère (à propos des critères pour juger si le principe de diligence a été respecté, cf. <ref-ruling> consid. 3a p. 50 ss; voir aussi <ref-ruling>).
Il appartient avant tout aux autorités cantonales, qui sont chargées de l'exécution du renvoi, de prendre toutes les mesures qui s'imposent en vue d'exécuter le refoulement de l'étranger. Il incombe également à l'Office fédéral des réfugiés et plus particulièrement à la Division spécialisée chargée des rapatriements de respecter le principe de diligence (voir implicitement l'arrêt non publié du 27 septembre 2001 dans la cause C._, consid. 2c). Mais les autres autorités qui ont officiellement affaire à un étranger sous le coup d'une décision de renvoi de Suisse sont tenues, selon les circonstances, de prendre en considération sa situation du point de vue de la police des étrangers. Cela vaut tout particulièrement pour les autorités de poursuite pénale et d'exécution des peines.
b) Dans son rapport du 26 novembre 2001 adressé au Tribunal fédéral, l'Office fédéral des réfugiés a indiqué que les autorités compétentes pour l'exécution du renvoi n'ont pas à apporter la preuve du respect du principe de diligence pour la durée de la détention préventive subie par l'étranger, ce principe ne valant que pour la détention en vue de refoulement. Il admet cependant que, entre le 11 mai 2001 et la mi-octobre 2001, aucune démarche concrète n'a été entreprise.
aa) Il est vrai que le principe de diligence s'applique avant tout à la période pendant laquelle l'étranger se trouve en détention en vue du refoulement. Vu le grand nombre d'étrangers en situation illégale qui doivent être refoulés, les autorités doivent prioritairement s'occuper d'établir l'identité et de se procurer les documents de voyage pour ces étrangers. Ne violent en tout cas pas le principe de diligence les autorités qui n'entreprennent rien pendant que l'étranger n'est pas à leur disposition donc, en règle générale, se trouve toujours en liberté. Par contre, l'obligation d'entreprendre des démarches en vue de l'exécution du renvoi commence non seulement au moment où la mise en détention en vue de refoulement est ordonnée, mais déjà auparavant, soit dès que l'étranger est complètement à disposition des autorités, car privé de liberté de mouvement.
Lorsqu'un étranger se trouve en détention préventive ou en exécution de peine, les autorités sont tenues déjà à ce moment-là - en cas de situation de police des étrangers claire - de prendre les dispositions en vue de son refoulement (<ref-ruling> consid. 3a p. 50 et les références citées).
Les autorités pénales et les autorités de police des étrangers doivent, au besoin, collaborer, ce qui implique un échange d'informations. Les autorités de police des étrangers sont en première ligne chargées de la coordination. Pour juger si le principe de diligence a été respecté, il est en principe sans importance de déterminer laquelle de ces autorités est éventuellement responsable du retard dans les préparatifs de départ de l'étranger (<ref-ruling> consid. 3a p. 50). Un devoir de collaboration existe également lorsque ce n'est pas le même canton qui est compétent pour prendre les mesures en matière pénale et les mesures en matière de police des étrangers (arrêt non publié du 3 avril 1997 dans l'affaire K._, consid. 2b/aa).
bb) Sous l'angle du principe de diligence, il y a lieu de prendre des mesures différentes selon que l'étranger se trouve en détention préventive ou en exécution de peine.
La situation d'un étranger qui exécute une peine n'est pas comparable avec celle de l'étranger qui se trouve en détention préventive. Il convient aussi de distinguer entre les démarches à entreprendre pour établir l'identité et celles en vue de se procurer des documents de voyage. Ce qui est important, c'est d'entreprendre tout ce qui est raisonnablement possible pour préparer le départ de manière que le renvoi de l'étranger puisse être exécuté si possible dès sa sortie de prison ou peu de temps après (arrêt du 10 décembre 1996, reproduit in RDAF 1997 I 29 consid. 4a; arrêt non publié du 6 janvier 1997 en l'affaire B._, consid. 3c/aa et arrêt du 30 octobre 1997 dans la cause B._, con-sid. 2a).
Lorsqu'un étranger purge une peine privative de liberté, il y a lieu de tenir compte de la fin de la peine mais aussi d'une possible libération conditionnelle. En pareil cas, tout doit être entrepris pour que l'identité de l'étranger soit établie et que les documents de voyage soient délivrés à la sortie de prison de l'étranger (arrêt précité du 6 janvier 1997 en la cause B._, consid. 3c/bb). Il en va autrement lorsque l'étranger se trouve en détention préventive.
La durée d'une telle détention ne peut souvent pas être appréciée d'emblée. Même lorsque le juge pénal a déjà fixé les débats, il est très difficile de faire un pronostic sur l'issue du procès, soit de déterminer si l'étranger sera acquitté ou reconnu coupable, s'il sera condamné à une courte ou à une longue peine privative de liberté, si celle-ci sera ou non assortie du sursis et, enfin, si la durée de la peine sera compensée par la détention préventive déjà subie. Cela met les autorités compétentes en difficulté pour ce qui concerne l'obtention des papiers: la validité d'un laissez-passer est en principe limitée dans le temps; or, si un tel document est délivré alors que l'étranger se trouve toujours en détention préventive, on peut craindre que la validité du document n'expire avant que l'étranger ne puisse être libéré de la détention préventive ou d'exécution de peine (arrêt non publié du 13 août 1998 dans la cause T._, consid. 3b).
Dans un tel cas, il convient donc plutôt d'attendre avant de se procurer un tel document. Il en va autrement pour ce qui est de l'établissement de l'identité et de l'origine de l'étranger. Il s'agit en effet de la condition nécessaire et préalable à l'exécution d'un renvoi. Les autorités compétentes doivent donc sans tarder rechercher l'identité et l'origine de l'étranger même lorsque celui-ci se trouve en détention préventive. C'est le seul moyen de s'assurer que l'étranger, une fois libéré sur le plan pénal, puisse se voir remettre rapidement les documents de voyage.
c) En l'espèce, le Service des étrangers a demandé vers la fin de l'année 2000 à l'Office fédéral des réfugiés un soutien à l'exécution du renvoi du recourant. Cet office a adressé des demandes de comparaisons dactyloscopiques, dont la dernière réponse remonte au 11 mai 2001. Le Service des étrangers a soumis, en février 2001, le recourant à une analyse linguistique concluant que celui-ci ne provenait vraisemblablement pas de Guinée Bissau, mais plutôt de Guinée.
Par la suite, ni les autorités cantonales ni l'Office fédéral des réfugiés n'ont entrepris des démarches quelconques, bien que le recourant se trouvât en détention préventive, ce dont le Service des étrangers était indubitablement au courant. Ce n'est que le 16 octobre 2001, après la mise en détention en vue du refoulement du recourant, que les autorités fédérales se sont adressées au Consulat suisse en Guinée-Bissau. Il est notamment écrit dans cet acte concernant plusieurs personnes, parmi lesquelles figurait le recourant: "In order to establish their nationality, we kindly ask you for an individual telephonic interview. " Il ressort du dossier que cet acte, destiné uniquement à établir l'identité du recourant, a été établi plus de cinq mois après la précédente démarche des autorités, si l'on fait abstraction de l'audition du recourant par la Police cantonale du Valais qui avait eu lieu quelques jours auparavant, soit le 10 octobre 2001. Le fait que, depuis lors, le Consulat suisse n'a pas répondu n'est en l'espèce pas déterminant pour juger de la lenteur de la procédure en vue de refoulement par les autorités suisses.
L'Office fédéral des réfugiés relève que, malgré le fait que le recourant soit originaire selon toute vraisemblance de Guinée, il n'est pas possible de faire des recherches dans ce pays, aussi longtemps que le recourant déclare provenir de Guinée Bissau. On ne comprend en tout cas pas pourquoi le recourant n'a pas été mis en contact pendant plusieurs mois avec les autorités du soi-disant pays d'origine.
Les autorités auraient dû entreprendre depuis longtemps des démarches auprès des autorités de Guinée Bissau, ne serait-ce que pour exclure, de manière définitive, que le recourant soit originaire de ce pays.
Vu ce qui précède, force est de constater que le principe de diligence a été violé.
5.- La violation du principe de diligence conduit, en règle générale, à la mise en liberté immédiate de l'intéressé, comme l'a déjà relevé le Tribunal fédéral dans de nombreux arrêts en matière d'internement des étrangers fondée sur l'ancien droit. En fait, lorsque les autorités ne s'emploient pas activement à exécuter le renvoi, il ne saurait plus être question d'une procédure d'expulsion "en cours" au sens de l'art. 5 par. 1 let. f CEDH pouvant justifier une privation de liberté de l'étranger (cf. <ref-ruling> consid. 3 p. 206/207, 423 consid. 4 p. 425 ss). La détention ne sert alors plus à atteindre l'unique but prévu par la loi, c'est-à-dire assurer l'exécution du renvoi. La détention en vue du refoulement du recourant ne repose ainsi pas sur une base légale.
Le présent recours doit donc être admis, la décision attaquée annulée et la libération immédiate du recourant ordonnée.
Les autorités cantonales, qui doivent continuer à prendre toutes les mesures nécessaires en vue de refouler le plus rapidement possible l'étranger, peuvent éventuellement prendre les mesures prévues à l'art. 13e LSEE (ordre de ne pas quitter le territoire qui lui est assigné ou de ne pas pénétrer dans une région déterminée). Selon l'art. 23a LSEE, quiconque n'observe pas les mesures ordonnées en vertu de l'art. 13e LSEE, sera puni d'une peine d'emprisonnement d'un an au plus ou des arrêts, s'il s'avère que l'exécution du renvoi ou de l'expulsion est impossible pour des raisons juridiques ou matérielles. Si tel n'est pas le cas, les autorités cantonales peuvent de nouveau ordonner la mise en détention en vue du refoulement de l'étranger, sur la base de l'art. 13b al. 1 let. b LSEE (en relation avec l'art. 13a let. b LSEE).
6.- Vu l'issue de la procédure, il n'y a pas lieu de prélever des frais en émoluments judiciaires (art. 156 al. 2 OJ). Le canton du Valais doit, en revanche, allouer une indemnité de dépens réduite au recourant, dont le mandataire n'est intervenu qu'en cours de procédure, soit après le dépôt du recours de droit administratif (art. 159 OJ). La requête d'assistance judiciaire au sens de l'art. 152 OJ devient ainsi sans objet.

Par ces motifs,
le Tribunal fédéral :
1.- Admet le recours de droit administratif et annule l'arrêt rendu le 2 novembre 2001 par le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais.
2.- Ordonne la libération immédiate du recourant.
3.- Dit qu'il n'est pas perçu d'émolument judiciaire.
4.- Constate que la demande d'assistance judiciaire est devenue sans objet.
5.- Met à la charge du canton du Valais une indemnité de 300 fr. à allouer au recourant à titre de dépens.
6.-Communique le présent arrêt par fax et en copie au recourant et à son mandataire, au Service de l'état civil et des étrangers et à la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral des étrangers.
_
Lausanne, le 4 décembre 2001 LGE/dxc
Au nom de la IIe Cour de droit public
du TRIBUNAL FEDERAL SUISSE:
Le Président, Le Greffier,