Check if value already exists when dealing with data that needs encryption

I have a big fixed list of personal access codes (this array never changes). When users register on the site, I need to check if their personal access code already exists in the array/database, this is to make sure the users registering are authorized to. For many concerns these access codes cannot be stored in plain text so they must be encrypted.

I need a way to quickly check if a provided access code exists in the system but keep everything encrypted stored.

Right now I'm encrypting everything in Bcrypt and storing the hashes only.

I've found to solutions but none seem to work in my conditions:

1. I hashed all the access codes using password_hash() in PHP then stored all these hashes in an array. To check if a given access code is in our system I used a for loop on the function password_verify() for every value in the array comparing the user's given data with the hashes. This method is secure but very inefficient, I'm dealing with over 4k sets of hashes, in the future this might increase to around 15k. Hashes near the end of the array can take around 3 minutes for the script to finish executing while testing.
2. Use the same salt each time when encrypting the data, that way I can easily check if the hash generated from the user's input matches with any of the hashes stored in the system's fixed database. This method is fast but insecure.

Are there any ways to properly do this or more efficient setups/languages to #1? I'm assuming there must be a proper way to do this since the same techniques to storing credit cards, SIN or other sensitive data would apply.