Sachverhalt:
A.
Die Staatsanwaltschaft Zürich-Sihl wirft X._ vor, in den Räumlichkeiten der Z._ AG bzw. der W._ AG an den von V._, U._ und T._ benutzten Computerstationen heimlich und unbefugt einen Keylogger eingesetzt zu haben. Dadurch habe er die Logins und Passwörter dieser Personen erlangt und sich Zugriff auf deren Computerarbeitsbereiche verschafft. Am 8. Februar 2011 habe er diese Tasteninformationen verwendet, Zugriff auf die gesamten Daten (Geschäftsunterlagen, geschäftliche und private Ordner sowie private und geschäftliche E-Mails) von T._ genommen und Informationen aus dessen E-Mail-Konto erlangt.
B.
Das Bezirksgericht Zürich verurteilte X._ am 21. Juni 2012 wegen unbefugten Eindringens in ein Datenverarbeitungssystem zu einer bedingten Geldstrafe von 40 Tagessätzen zu Fr. 1'000.--. Auf das Schadenersatzbegehren der Y._ AG trat es nicht ein. Das Verfahren hinsichtlich der Straf- und Zivilklage von T._ stellte es zufolge Fehlens eines Strafantrags ein. Die Kosten der Untersuchung und des gerichtlichen Verfahrens auferlegte es X._. Es verpflichtete ihn, der Y._ AG für das gesamte Verfahren eine Prozessentschädigung von Fr. 60'253.05 zu bezahlen.
X._ legte gegen dieses Urteil Berufung ein. Das Nichteintreten auf das Schadenersatzbegehren der Y._ AG und die Einstellung des Verfahrens hinsichtlich T._ erwuchsen unangefochten in Rechtskraft. Am 7. Mai 2013 stellte das Obergericht des Kantons Zürich das Strafverfahren gegen X._ wegen unbefugten Eindringens in ein Datenverarbeitungssystem aufgrund der Verletzung des Anklageprinzips ein. Es bestätigte das erstinstanzliche Kosten- und Entschädigungsdispositiv.
C.
X._ beantragt mit Beschwerde in Strafsachen, die Dispositivziffer 3 (Bestätigung der erstinstanzlichen Kosten- und Entschädigungsfolgen) des Beschlusses des Obergerichts sei aufzuheben. Ihm seien keine Gerichtsgebühren aufzuerlegen. Er sei nicht zu verpflichten, der Y._ AG für das erstinstanzliche Verfahren eine Prozessentschädigung zu bezahlen, und ihm sei für das erstinstanzliche Verfahren eine solche zuzusprechen.
D.
Das Obergericht und die Oberstaatsanwaltschaft verzichteten auf eine Stellungnahme. Die Y._ AG beantragt in ihrer Vernehmlassung, die Beschwerde sei vollumfänglich abzuweisen. Mit Eingabe vom 18. März 2014 nahm X._ sein Recht zur Replik wahr.

Erwägungen:
1.
Der Beschwerdeführer wirft der Vorinstanz eine offensichtlich unrichtige Feststellung des Sachverhalts (<ref-law> i.V.m. <ref-law>) und die Verletzung von Art. 426 Abs. 2, Art. 433 Abs. 1 lit. b sowie Art. 429 Abs. 1 lit. a StPO, der Begründungspflicht (<ref-law>, <ref-law> und Art. 6 Ziff. 1 EMRK), des Anspruchs auf rechtliches Gehör (<ref-law> sowie Art. 6 Ziff. 1 EMRK) und der Unschuldsvermutung (<ref-law> sowie Art. 6 Ziff. 2 EMRK) vor (Beschwerde S. 4 ff.).
Das Recht, angehört zu werden, ist formeller Natur. Dessen Verletzung führt ungeachtet der materiellen Begründetheit des Rechtsmittels zur Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Entscheids (<ref-ruling> E. 2.2 mit Hinweis). Die entsprechenden Rügen sind deshalb vorweg zu prüfen.
2.
2.1. Der Beschwerdeführer macht eine Verletzung seines Anspruchs auf rechtliches Gehör geltend. Er sei im vorinstanzlichen Verfahren nicht auf eine mögliche Kosten- und Entschädigungsauflage trotz Einstellung des Verfahrens aufmerksam gemacht worden. Er habe sich weder zu den diesbezüglichen Fakten noch zur rechtlichen Lage äussern können. Die Vorinstanz habe ihre Verhandlung auf die Vorfragen über die Antragsberechtigung und die Verletzung des Anklageprinzips beschränkt (Beschwerde S. 7-9 Ziff. 21-28).
2.2. Das rechtliche Gehör dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen. Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (<ref-ruling> E. 5.1 mit Hinweisen).
2.3. Am 23. Januar 2013 wies die Vorinstanz die Beweisanträge des Beschwerdeführers auf Einvernahme von Zeugen, Edition von EDV-Anlagen-Nutzungsverträgen und Einholung eines Gutachtens über die existenzbedrohende Situation der Z._ AG einstweilen ab. Im Hinblick auf die Berufungsverhandlung vom 7. Mai 2013 reichte der Beschwerdeführer eine kurze Begründung ein. Darin machte er u.a. geltend, die Y._ AG sei nicht strafantragsberechtigt und das Anklageprinzip sei verletzt. Sein Gesuch vom 10. April 2013, das Verfahren auf die Vorfrage der Antragsberechtigung der Y._ AG zu beschränken, wies die Vorinstanz am 24. April 2013 ab (Beschluss S. 2 f. E. 4, Beschwerde S. 7 Ziff. 21; vorinstanzliche Akten, act. 54 und act. 58-60).
Auf Nachfrage erklärte der Rechtsvertreter des Beschwerdeführers zu Beginn der Berufungsverhandlung, er halte an seinem Antrag auf Beschränkung des Verfahrens betreffend Strafantragsberechtigung fest. In der Folge plädierten sowohl er als auch die damalige Rechtsvertreterin der Beschwerdegegnerin 2 ausschliesslich zu den Vorfragen (Verhandlungsprotokoll, vorinstanzliche Akten, act. 66 S. 8 ff., und Plädoyernotizen, vorinstanzliche Akten, act. 63 f.). Den Plädoyernotizen des Verteidigers des Beschwerdeführers kann entnommen werden, dass er sich u.a. auch auf die Kosten- und Entschädigungsfolgen vorbereitet hatte (vorinstanzliche Akten, act. 63 S. 30-32). Nach Replik und Duplik zu den Vorfragen wurde die Verhandlung für eine Zwischenberatung unterbrochen. Nachdem sich die Parteien zu ihren Aufwendungen im Berufungsverfahren äussern konnten, eröffnete die Vorinstanz - nach einer Beratung - mündlich den angefochtenen Beschluss (Protokoll der vorinstanzlichen Verhandlung, vorinstanzliche Akten, act. 66 S. 8-13). Darin bestätigte sie trotz der Einstellung des Verfahrens die erstinstanzlichen Kosten- und Entschädigungsfolgen. Damit verpflichtete sie den Beschwerdeführer zur Bezahlung von Gerichts- und Parteikosten, ohne ihm zuvor die Möglichkeit einer diesbezüglichen Stellungnahme gewährt zu haben. Dieser durfte sich lediglich zu den Vorfragen äussern. Dabei führte er aus, das erstinstanzliche Urteil sei aufgrund des fehlenden gültigen Strafantrags und der Missachtung des Anklageprinzips aufzuheben (Plädoyernotizen, vorinstanzliche Akten, act. 63 S. 6-9 Ziff. 12-18). Er setzte sich somit für die Beendigung des Strafverfahrens ein. Gleichwohl kann ihm vorliegend nicht vorgehalten werden, er hätte sich von sich aus bereits in dieser Stellungnahme zu einer möglichen Kostenauflage und Entschädigungspflicht äussern müssen. Er musste nicht damit rechnen, dass die Vorinstanz die Berufungsverhandlung unterbricht und unmittelbar entscheidet, ohne dass er sein vorbereitetes Plädoyer abschliessen konnte.
Eine Heilung dieser schweren Verletzung des Anspruchs auf rechtliches Gehör des Beschwerdeführers im bundesgerichtlichen Verfahren kommt offensichtlich nicht in Betracht (zum Ganzen <ref-ruling> E. 2.3.2 mit Hinweisen).
3.
Die Beschwerde ist gutzuheissen. Der angefochtene Beschluss ist aufzuheben und die Sache zur neuen Entscheidung (unter Gewährung des rechtlichen Gehörs) an die Vorinstanz zurückzuweisen. Auf die übrigen Rügen und Vorbringen des Beschwerdeführers ist bei dieser Sachlage nicht einzugehen.
Der Vorinstanz und der Beschwerdegegnerin 1 sind keine Kosten aufzuerlegen (<ref-law>). Da die Beschwerdegegnerin 2 mit ihrem Antrag unterliegt, hat sie die hälftigen Gerichtskosten zu tragen (<ref-law>) und dem anwaltlich vertretenen Beschwerdeführer zusammen mit dem Kanton Zürich eine angemessene Parteientschädigung zu entrichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Beschluss des Obergerichts des Kantons Zürich vom 7. Mai 2013 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Die Gerichtskosten werden im Umfang von Fr. 1'000.-- der Beschwerdegegnerin 2 auferlegt.
3.
Die Beschwerdegegnerin 2 und der Kanton Zürich haben dem Beschwerdeführer eine Entschädigung von je Fr. 1'500.-- auszurichten.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 22. April 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Pasquini