SELECT * WHERE VarCharColumn IN (...) Optimization

SELECT * will invalidate any optimal use of an index (it isn't covering) even if hash is indexed. Your index scan is most likely on the clustered index because of this.

Personally, I'd start with

• putting the 3000 search values into a table with an index
• Edit: as per Marian's comment, this can be passed in a list or table already
• use this in any of JOIN, IN, EXISTS (same plan usually)
• ensure my index on MasterUrls suits using Hash and covers col1, col2, col3

Something like

CREATE TABLE #foo (Hash ...)
INSERT #foo...
CREATE INDEX IX_FOO ON #foo (hash)

--either
CREATE NONCLUSTERED INDEX IX_Hash ON MasterUrls (hash) INCLUDE (col1, col2, col3)
--or    
CREATE CLUSTERED INDEX IXC_Hash ON MasterUrls (hash)

SELECT col1, col2, col3
FROM [ohb].[dbo].[MasterUrls] M
JOIN
#foo F ON M.Hash = F.Hash

Pass the values in via a table valued paramater. This way they are already in table form. Then copy the values from the TVP into a temp table, which has a clustered index on it. Use this temp table as a JOIN member of your query.

Remove the SELECT * and change it to only the columns that you need, with the additional columns included. If SELECT * is needed then include all additional columns as a included columns within the index.