When search on long text on table have 40 milion rows it is very slow

Question

I work on SQL server 2012 I need to search on table partswithcompany that have 40 million rows .

when make select SearchParts, CompanyId from partswithcompany where CompanyId=1234 and SearchParts='A5ghf7598fdmlcpghjk'

it is very slow to re but it take too much long time when make select data from table or when using where condition is also very slow

so i think more then i get idea to use hash byte column so How to do that please ?

if you have any good idea to enhance performance i can accept it

create table #partswithcompany
 (
 SearchParts  nvarchar(200),
 CompanyId  int
 )
 insert into #partswithcompany (SearchParts,CompanyId)
 values
 ('A5ghf7598fdmlcpghjk',1234),
 ('AKLJGSA7598fdmlcpghjk',5870),
 ('KHJLFFS8fdmlcpghjk',123345),
 ('A5ghf7598f7GGHYUTYA',3456),
 ('A5ghfJKKJGHHGghjk',9081818)