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.