Seol mar théacs é seo: Hashing embeddings of optimal dimension, with applications to linear least squares